prolog clpfd

prolog - ¿cómo puedo determinar que todas las coordenadas dadas de la matriz estén conectadas?



clpfd (2)

Dada una grilla, ¿cómo puedo determinar si los elementos de una grilla están todos en una sola región? En el caso siguiente, es verdadero porque cada elemento en la matriz tiene un vecino.

Ejemplo 1:

gridneighbours([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]). true.

Sin embargo, en mi segundo ejemplo, Ejemplo2:

gridneighbours([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]). false.

Esto es falso porque [3,1], [4,1], [4,2] son ​​disjuntos a los elementos anteriores. Inicialmente traté de usar un subconjunto de Prolog para verificar si había un elemento existente al lado de otro simplemente agregando o restando de X o Y, sin embargo, esto no funciona porque los elementos de una región dividida estarían uno al lado del otro. Además, las diagonales no cuentan como estar una al lado de la otra.

Actualizado, código agregado: Esto es lo que obtuve:

%Check right neighbourcheck([X,Y|_],S) :- X1 is X + 1, subset([[X1,Y]],S). %Check left neighbourcheck([X,Y|_],S) :- X1 is X - 1, subset([[X1,Y]],S). %Check Up neighbourcheck([X,Y|_],S) :- Y1 is Y + 1, subset([[X,Y1]],S). %Check Down neighbourcheck([X,Y|_],S) :- Y1 is Y - 1, subset([[X,Y1]],S). % Iterate through all sublists and check for neighbours gridneighbour(S) :- forall(member(X,S), neighbourcheck(X,S)).

La razón por la que esto no funciona es porque al subconjunto no le importa si tenemos una coincidencia con otro elemento que está desarticulado. es decir, [3,1] coincide con [4,1]. Al ejecutar este código y usar los ejemplos anteriores, se obtiene:

  • Ejemplo1: verdadero
  • Ejemplo 2: verdadero (claramente esto debería ser falso porque [3,1], [4,1] y [4,2] están separados).

Un enfoque ingenuo que funciona puede resumirse de la siguiente manera:

  • Comience con dos conjuntos (¿listas?) De puntos: aquellos que usted sabe que pertenecen a una región, Region y el resto, Rest . Al principio, puede elegir cualquier punto para pertenecer a la Region , y lo que quede está en Rest .
  • Busca en Rest un punto que sea vecino de cualquier punto de la Region .
    • si encuentra un vecino, muévalo de Rest a Region y repita
    • si no encuentra un vecino, deténgase
  • Si hay puntos en Rest al final, entonces esta no es una región.

Aquí hay una forma más simple de definir neighbors/2 :

neighbors([X1,Y1], [X2,Y2]) :- abs(X1-X2) + abs(Y1-Y2) =:= 1.

Puede buscar un punto en una lista que sea vecino de un punto en otra lista simplemente probando cada combinación posible:

% add_to_region(+Region0, +Rest0, -Region, -Rest) %% Look in Rest0 for a neighbor to Region0; %% Region is Region0 with the neighbor, %% Rest is Rest0 without it add_to_region(Region, Rest0, [B|Region], Rest) :- member(A, Region), select(B, Rest0, Rest), neighbors(A, B).

La llamada al miembro / 2 selecciona cada punto en la Región a A, retrocediendo. La llamada para seleccionar / 3 selecciona cada punto en Rest0 a B, con el resto de los puntos en Rest. Si los dos puntos son vecinos, B se agrega al frente de la Región.

Esto fallará si no hay más vecinos en la región actual en Rest , y tendrá éxito al menos una vez si los hay. Es posible que desee llamar a esto once(add_to_region(Region0, Rest0, Region, Rest)) para que no tenga puntos de elección innecesarios. Usando tus ejemplos:

?- once( add_to_region( [[1,1],[1,2],[1,3],[2,1]], [[2,2],[2,3],[3,1],[4,1],[4,2]], Region, Rest)). Region = [[2, 2], [1, 1], [1, 2], [1, 3], [2, 1]], Rest = [[2, 3], [3, 1], [4, 1], [4, 2]].

Vea cómo [2,2] fue seleccionado de Rest y agregado a Region .

?- add_to_region( [[1,1],[1,2],[1,3],[1,4],[1,5],[1,6]], [[3,1],[4,1],[4,2]], Region, Rest). false.

Esto falla porque ninguno de los puntos en Rest es un vecino de ninguno de los puntos en la Region .

Editar

Como se explicó anteriormente es definitivamente factible, pero con una ligera modificación, podemos tener un algoritmo que es mucho más fácil de implementar en Prolog. Dice así:

set_region_rest(+Set, -Region, -Rest)

  • Ordene el conjunto de puntos al orden estándar de los términos; ahora tienes un ordset .
  • Divida este conjunto en una región y un resto que no le pertenece

Para hacer la división, mantendremos una lista extra. Lo llamaremos una lista de nodos abiertos: nodos que aún no hemos explorado. Al principio, el primer elemento de nuestra lista de entrada es el único nodo abierto. El resto de los elementos se pasan como están. Los dos últimos argumentos, la Región y el Resto, son los argumentos de salida.

open_set_closed_rest(Open, Set, Closed, Rest)

  • Si el conjunto abierto está vacío, también lo está el resto del conjunto cerrado (ahora la región); el conjunto restante es el resto.
  • De otra manera:
    • Tome el primer par de coordenadas de la lista Abrir; inmediatamente colóquelo al frente de las coordenadas Cerradas.
    • Intenta encontrar cualquiera de los vecinos de estos primeros pares en el Conjunto de coordenadas; si encuentra alguno, añádalos al frente del conjunto abierto; el resto de Set después de eliminar a los vecinos es el nuevo Conjunto.
    • Pruebe de nuevo con el nuevo conjunto abierto, el resto del conjunto cerrado, el conjunto restante y el resto.

Para hacer esto en Prolog, primero limpiaré la representación de coordenadas. Es un poco molesto que aparezcan en listas de dos: es mucho menos escribir si utilizamos, por ejemplo, un par: [X,Y] ---> XY . Para hacer esto, agrego este predicado:

xy(XY) :- coordinates(C), maplist([[X,Y], X-Y]>>true, C, XY). xy([1-1,1-3,1-2]). xy([1-2,2-1,2-2]). xy([1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5]). xy([1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5]). coordinates([[1,1],[1,2],[1,3],[2,1],[2,2],[2,3],[3,1],[4,1],[4,2]]). coordinates([[1,1],[1,2],[1,3],[1,4],[1,5],[1,6],[3,1],[4,1],[4,2]]).

(¡También puse 4 juegos de prueba adicionales!)

Entonces con esto, obtengo:

?- xy(XY). XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, ... - ...] [write] % press ''w'' here XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2] ; XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2] ; XY = [1-1, 1-3, 1-2] ; XY = [1-2, 2-1, 2-2] ; XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5] ; XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5].

Aquí es cómo uno podría intentar escribir los algoritmos anteriores en código:

set_region_rest([A|As], Region, Rest) :- sort([A|As], [B|Bs]), open_set_closed_rest([B], Bs, Region, Rest).

Esto acaba de ordenar la entrada Establecer y dividir el primer elemento de la misma. El primer elemento es el primer par de coordenadas en el conjunto abierto, el resto es el conjunto, luego los argumentos de salida.

Ahora, para dividir el Conjunto en una Región y un Descanso, debemos seguir creciendo en la Región siempre que tengamos pares de coordenadas en el Conjunto abierto. Si el conjunto abierto está vacío, significa que nuestra región está completa y el conjunto restante es el resto:

:- use_module(library(clpfd)). open_set_closed_rest([], Rest, [], Rest).

Para saber qué vecinos de una coordenada están en el Conjunto, usamos ord_intersection/4 , que nos da los vecinos en Conjunto y el resto del Conjunto al mismo tiempo.

NB : ¡Las 4 coordenadas vecinas se enumeran ordenadas!

open_set_closed_rest([X-Y|As], Set, [X-Y|Closed0], Rest) :- X0 #= X-1, X1 #= X + 1, Y0 #= Y-1, Y1 #= Y + 1, ord_intersection([X0-Y,X-Y0,X-Y1,X1-Y], Set, New, Set0), append(New, As, Open), open_set_closed_rest(Open, Set0, Closed0, Rest).

Eso es todo. Con esto, obtengo las siguientes 6 soluciones:

?- xy(XY), set_region_rest(XY, Region, Rest). XY = [1-1, 1-2, 1-3, 2-1, 2-2, 2-3, 3-1, 4-1, 4-2], Region = [1-1, 1-2, 1-3, 2-3, 2-2, 2-1, 3-1, 4-1, 4-2], Rest = [] ; XY = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6, 3-1, 4-1, 4-2], Region = [1-1, 1-2, 1-3, 1-4, 1-5, 1-6], Rest = [3-1, 4-1, 4-2] ; XY = [1-1, 1-3, 1-2], Region = [1-1, 1-2, 1-3], Rest = [] ; XY = [1-2, 2-1, 2-2], Region = [1-2, 2-2, 2-1], Rest = [] ; XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5], Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1], Rest = [] ; XY = [1-1, 1-2, 1-3, 1-4, 1-5, 2-1, 2-5, 3-1, 3-3, 3-5, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5], Region = [1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1], Rest = [3-3].

Por cierto, usando set_region_rest/3 como un bloque de creación, podemos dividir fácilmente un conjunto de coordenadas en regiones:

set_regions([], []). set_regions([X|Xs], [R|Rs]) :- set_region_rest([X|Xs], R, Rest), set_regions(Rest, Rs).

Y ahora:

?- set_regions([1-1, 1-2, 1-3, 1-4, 1-5, 1-7, 2-1, 2-5, 2-7, 3-1, 3-3, 3-5, 3-7, 4-1, 4-5, 5-1, 5-2, 5-3, 5-4, 5-5, 5-7], R). R = [[1-1, 1-2, 1-3, 1-4, 1-5, 2-5, 3-5, 4-5, 5-5, 5-4, 5-3, 5-2, 5-1, 4-1, 3-1, 2-1], [1-7, 2-7, 3-7], [3-3], [5-7]].

Este problema se puede ver como una instancia de algoritmos de búsqueda de unión . Tales algoritmos a menudo hacen uso de una estructura de datos especial, que básicamente sirve para los dos propósitos siguientes:

1) For a point p, find a representant p* in the data structure 2) For two representants p1* and p2* extend the data structure by connecting both

Aquí hay una implementación de Prolog que usa un hilo local de hecho vinculado / 2 como la unión encuentra la estructura de datos. Aquí hay un ejemplo de ejecución para el segundo problema de la grilla:

?- regions(L). L = [(1, 6), (4, 2)].

Nota técnica: la unificación de prólogos también tiene un componente integrado de búsqueda de unión, si menciona una variable X, se eliminará su referencia, que es el paso 1). Si haces la unificación X = Y y X e Y ya están desreferenciados, una variable se vinculará a otra, que es el paso 2).