Algoritmo para resolver el juego tipo Sokoban en grafos - mover fichas de un conjunto de vértices a otro

Question

La pregunta se acerca a la Sokoban juego (¡gracias a Dima Pasechnik!), pero un poco diferente en los detalles.

Consideremos un grafo dirigido (multigrafos). Considerar un conjunto de fichas marcadas (ficha1, ficha2,..., fichaM). Poner las fichas en un conjunto de vértices 'Init1','Init2','Init3'... Y considera otro conjunto de vértices 'Final1','Final2',..., 'FinalM'.

Pregunta Proponer un algoritmo "eficiente" que determine si es posible "MOVER" fichas de las posiciones "InitNN" a las posiciones 'FinalNN'.

Donde se nos permite "MOVER" la ficha de un vértice a una arista saliente y de la arista entrante al vértice correspondiente. Con la RESTRICCIÓN de que dos fichas NO pueden estar en el mismo lugar. Un movimiento - mueve sólo UNA ficha. La fichaK debe ir a la posición FinalK - la misma "K".

Pregunta Puede haber muchos enfoques para resolver el problema, me interesa en analizar su complejidad. Cualquier idea es bienvenida. Por ejemplo, si el gráfico es "aleatorio" en cierto sentido, ¿cuál puede ser el algoritmo de menor complejidad media?

Donde la complejidad se cuenta en número de operaciones (escriba un código C (en realidad escribí un código Matlab), compile y calcule el número de ciclos - esta es una medida de complejidad bien definida, diferentes compiladores y CPU darán aproximadamente el mismo resultado).

Ejemplo de algoritmo Parece que la forma más sencilla de resolver un problema es la siguiente. Esencialmente puede reducirse a determinar dónde están conectados dos vértices en algún grafo mayor, lo que a su vez puede resolverse mediante la "búsqueda de amplitud" ("algoritmo de onda" en ruso) (quiero decir que enumeremos todas las todas las configuraciones posibles de los chips - esto dará vértices del "nuevo gráfico". Conectemos dos vértices (configuraciones) si hay un "MOVE" que va de uno a otro). Por "búsqueda de amplitud" ("algoritmo de onda" en ruso) me refiero a lo siguiente: tomar un vértice inicial y encontrar todos los conectados a él; en el siguiente paso encontrar todos los vértices conectados a los vértices encontrados en el paso anterior; y así sucesivamente....

Pregunta ¿Qué hay de la eficiencia de este algoritmo? ¿Se puede proponer algo mejor?

Answer 1

He aquí un algoritmo en tiempo polinómico. Asumo que las fichas son idénticas, como en la reformulación de Dima y en Sokoban. (Otra versión sería que la ficha de Init $_i$ tiene que ir a la final $_i$ para cada $i$ .)

1. Descubre que las fichas deben ir a que posiciones de destino:
   1. Establecer un grafo bipartito, con un arco desde Init $_i$ a la final $_j$ si es final $_j$ es alcanzable desde Init $_i$ en el gráfico (ignorando las fichas).
   2. Si algunos Init $_i$ y algunas finales $_j$ coinciden, significa que se puede considerar que alguna ficha ya se encuentra en su posición de destino. Eliminamos estos pares de vértices del gráfico.
   3. Encuentra una coincidencia perfecta. Si no hay ninguna, abortar. El problema no tiene solución.
   4. El emparejamiento da una asignación 1-1 entre las posiciones inicial y final.
2. Ahora realizamos estos movimientos uno por uno. Digamos que queremos mover el chip $A$ de Init $_i$ a la final $_j$ que no está ocupado. Encuentra cualquier camino desde Init $_i$ a la final $_j$ en el gráfico (ignorando las otras fichas). Intenta empujar la ficha a lo largo de este camino. Puede ocurrir que alguna otra ficha $B$ bloquea el camino. En este caso, mueve $B$ un paso a lo largo del camino, y luego dejar que $A$ ocupan el lugar anterior de $B$ . Como las fichas son idénticas, el efecto es el mismo que si $A$ había saltado por encima de $B$ . El mismo truco puede "saltar" sobre varias fichas adyacentes que bloquean el camino.

Answer 2

No es una respuesta, sino una versión mejorada de la pregunta:

Consideremos un grafo dirigido $G=(V,A)$ y un subconjunto $F\subset V$ de final nodos. Sea $m=|F|$ y considerar el siguiente juego: se da una configuración de $m$ fichas en $V$ con no más de una ficha por nodo (o, más formalmente, una función inyectiva $c:[1,2,\dots, m]\to V$ ), y se permiten los siguientes movimientos:

• elegir un arco $vu\in A$ con un chip en $v$ sin chip en $u$ ;
• mover el chip de $v$ en $u$ .

(es decir, con el formalismo de las funciones, modificamos $c$ para que $u$ entra en $c^{-1}(V)$ y $v$ deja $c^{-1}(V)$ .)

El objetivo : portada $F$ con fichas. (es decir, lograr $c([1,2,\dots, m])=F$ ).

Pregunta : cuál es la complejidad de decidir si se puede alcanzar el objetivo.

Answer 3

Editar : Sokoban es un más difícil ¡problema que éste!

No es difícil ver que Sokoban es un caso particular de este problema (los grafos que surgen en Sokoban son no dirigidos y planos, de grado como máximo 4). Sokoban se sabe que es NP-completo . (gracias a mi mujer, que es teórica de la complejidad por formación, y solía jugar al Sokoban :-)).

Así, en general, suponiendo que P no es igual a NP, cualquier procedimiento para resolver este problema se ejecutará en tiempo exponencial en $m$ .

Por otro lado, para cualquier $m$ este problema se puede resolver mediante la aplicación repetida del algoritmo del camino más corto, que necesita iterar sobre todas las posibles asignaciones de fichas en la configuración inicial a los elementos (ordenados) de $F$ (es decir, los nodos finales). Si para ninguna de estas asignaciones se completa el proceso de desplazamiento de las fichas, no hay solución. Por otra parte, el procedimiento se ejecuta en tiempo polinómico para $m$ arreglado.

Answer 4

No es una respuesta, sino una reformulación de Sokoban en términos de grafos orientados: Un problema Sokoban de orden $k$ en un grafo dirigido finito con vértices $V$ y aristas dirigidas $E$ (con $(s,t)$ que denota una arista de $s$ a $t$ ) consta de dos subconjuntos (que quizás se cruzan) $V_I,V_F$ de $k$ vértices (que definen las posiciones inicial y final del $k$ cajas), de un vértice marcado $*$ de $V\setminus V_I$ y de un conjunto $P=\cup_{e\in E}P_e$ de "posibles empujones" donde $P_e$ es un subconjunto de aristas que comienza en el vértice final $t$ de la arista orientada $e=(s,t)$ .

Un problema Sokoban se resuelve si $V_F=V_I$ .

Un movimiento consiste en la elección de un nuevo vértice marcado $*'\in V\setminus V_I$ junto a $*$ por un borde $(*,*')$ o mediante la elección de un nuevo vértice marcado $*'\in V_i$ junto a $*$ por un borde $(*,*')$ junto con un nuevo conjunto $V'_I$ de vértices iniciales de la forma $V'_I=(V_I\setminus\lbrace *'\rbrace)\cup \lbrace v\rbrace$ con $v\in V\setminus V_I$ tal que $(*',v)$ es un elemento del conjunto $P_{(*,*')}$ de posibles empujes asociados a la arista orientada $(*,*')$ . (Los conjuntos $V_F$ de posiciones finales y $P$ de los posibles empujes siguen siendo los mismos).

El gráfico Sokoban $(V,E,V_F,P)$ con posibles movimientos $P$ y $k$ posiciones finales $V_F$ es el grafo dirigido con vértices dados por todos los ${\sharp(V)\choose k}(\sharp(V)-k)$ posibles opciones de $k$ vértices iniciales $V_I$ y de un vértice marcado $*$ en $V\setminus V_I$ . Los movimientos definen las aristas orientadas del gráfico Sokoban. Una solución de un problema Sokoban $(V,E,V_I,V_F,*,P)$ es un camino en el gráfico Sokoban $(V,E,V_F,P)$ a partir del vértice $(V,E,V_I,V_F,*,P)$ y terminando en uno de los $(\sharp(V)-k)$ soluciones $(V,E,V_F,V_I=V_F,*,P)$ (con $*\in V\setminus V_F$ ).

El gráfico Sokoban $(V,E,V_F,P)$ tiene así $<\sharp(V)^{k+1}$ vértices y es de grado $\leq m^2$ donde $m$ es el máximo sobre todos los grados de entrada y salida de $(V,E)$ . Tengo la impresión de que esto implica que un problema concreto de Sokoban dado puede resolverse en tiempo polinómico (ya que $m\leq 4$ para Sokoban).

Answer 5

La mejor analogía cuando los marcadores son distintos no es Sokoban, sino el 15-puzzle . Incluso está en un grafo no dirigido .

Todas mis observaciones a continuación se refieren a la versión no dirigida. ADICIÓN: Al final hay una observación sobre la aplicación al caso dirigido . (En mi breve búsqueda bibliográfica sólo he encontrado un artículo con grafos dirigidos, para un solo guijarro (robot) con obstáculos cuya posición final es irrelevante). El resultado es:

En los grafos no dirigidos, la versión de decisión ("¿Existe una solución?") se puede resolver en tiempo polinómico, pero la minimización del número de movimientos es difícil de resolver.

Hay un breve documento de Oded Goldreich, que data de 1984 pero publicado sólo en 2011, " Encontrar la secuencia de movimientos más corta en el rompecabezas gráfico generalizado de 15 es NP-difícil ". Ratner y Warmuth demostraron ( Journal of Symbolic Computation, 1990 ) que esto es cierto incluso para la extensión del rompecabezas de 15 a cuadrados más grandes.

Richard Wilson ha caracterizado en 1974 los casos en que es posible una solución, en el caso de que haya $n-1$ fichas en una biconexión general $n$ -vértice, como en el puzzle de 15. Según un reciente documento de Gabriele Röger y Malte Helmert , Kornhauser, Miller y Spirakis ( "Movimiento coordinado de guijarros en grafos, el diámetro de los grupos de permutación y aplicaciones", 1984 ) extendieron estos resultados al caso en que se ocupan menos vértices y a grafos más generales, y demostraron que existe una solución con $O(n^3)$ se mueve si hay alguna solución. (No he mirado este documento. De todos modos, Röger y Helmert recomiendan encontrar más detalles en el informe técnico que contiene las tesis de maestría de Daniel Kornhauser).

Para grafos dirigidos que son biconexos y fuertemente conectados se pueden aplicar las caracterizaciones del caso del grafo no dirigido, porque siempre se puede simular un "movimiento hacia atrás": Sea $ab$ sea un arco y supongamos que queremos mover un guijarro $X$ de $b$ a $a$ . Encuentra un ciclo dirigido a través de $ab$ y empujar los vértices en este ciclo a través, pero no hacer el último movimiento de guijarro $X$ de $a$ a $b$ . Esto supone un retroceso por parte de $O(n^2)$ movimientos hacia adelante. Esto da lugar a un algoritmo de decisión en tiempo lineal y a un $O(n^5)$ límite superior del número de movimientos (cuando existe una solución) para esta clase de digrafos.