tiempo tarda rompecabezas recomendaciones problema piezas para online manhattan inteligencia heuristica cuanto como bound artificial armar and algoritmo 3x3 algorithm logic puzzle a-star 8-puzzle

algorithm - tarda - ¿Cuál puede ser el enfoque eficiente para resolver el problema de los 8 rompecabezas?



recomendaciones para armar rompecabezas de 1000 piezas (6)

El 8-puzzle es una tabla cuadrada con 9 posiciones, rellenada con 8 fichas numeradas y un espacio. En cualquier punto, una baldosa adyacente al espacio se puede mover al espacio, creando una nueva posición de espacio. En otras palabras, la brecha se puede intercambiar con un mosaico adyacente (horizontal y verticalmente). El objetivo del juego es comenzar con una configuración arbitraria de fichas y moverlas para que las fichas numeradas se ordenen en orden ascendente, ya sea alrededor del perímetro del tablero o ordenadas de izquierda a derecha, con 1 en la parte superior izquierda Posición de la mano.

Me preguntaba qué enfoque será eficiente para resolver este problema?

Donut lo tiene! IDDFS hará el truco, considerando el espacio de búsqueda relativamente limitado de este rompecabezas. Sería eficiente por lo tanto responder a la pregunta del OP. Encontraría la solución óptima, pero no necesariamente en una complejidad óptima.

Implementar IDDFS sería la parte más complicada de este problema, solo quiero sugerir un enfoque simple para administrar el tablero, las reglas de los juegos, etc. Esto en particular aborda una manera de obtener estados iniciales para el rompecabezas que se pueden resolver. Una insinuación en las notas de la pregunta, no todas las asignaciones aleatorias de 9 tites (considerando la ranura vacía como una ficha especial), producirá un rompecabezas que se puede resolver. Es una cuestión de paridad matemática ... Entonces, aquí hay algunas sugerencias para modelar el juego:

Haga la lista de todas las matrices de permutación de 3x3 que representan "movimientos" válidos del juego. Dicha lista es un subconjunto de 3x3s con todos los ceros y dos unos. Cada matriz obtiene una ID que será bastante conveniente para realizar un seguimiento de los movimientos, en el árbol de búsqueda IDDFS. Una alternativa a las matrices, es tener dos tuplas de los números de posición de los azulejos para intercambiar, esto puede llevar a una implementación más rápida.

Dichas matrices se pueden usar para crear el estado inicial del rompecabezas, comenzando con el estado "ganador" y ejecutando un número arbitrario de permutaciones seleccionadas al azar. Además de garantizar que el estado inicial sea solucionable, este enfoque también proporciona un número indicativo de movimientos con los que se puede resolver un rompecabezas determinado.

Ahora simplemente implementemos el IDDFS algo y [broma] devolvemos la asignación para un A + [/ broma] ...

Este es un ejemplo del algoritmo clásico de ruta más corta. Puedes leer más sobre el camino más corto here y here .

En resumen, piense en todos los estados posibles del rompecabezas como en vértices en algún gráfico. Con cada movimiento cambias de estado, entonces, cada movimiento válido representa un borde del gráfico. Dado que los movimientos no tienen ningún costo, puede pensar que el costo de cada movimiento es 1. El siguiente p ++ código de p ++ funciona para este problema:

{ int[][] field = new int[3][3]; // fill the input here map<string, int> path; queue<string> q; put(field, 0); // we can get to the starting position in 0 turns while (!q.empty()) { string v = q.poll(); int[][] take = decode(v); int time = path.get(v); if (isFinalPosition(take)) { return time; } for each valid move from take to int[][] newPosition { put(newPosition, time + 1); } } // no path return -1; } void isFinalPosition(int[][] q) { return encode(q) == "123456780"; // 0 represents empty space } void put(int[][] position, int time) { string s = encode(newPosition); if (!path.contains(s)) { path.put(s, time); } } string encode(int[][] field) { string s = ""; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) s += field[i][j]; return s; } int[][] decode(string s) { int[][] ans = new int[3][3]; for (int i = 0; i < 3; i++) for (int j = 0; j < 3; j++) field[i][j] = s[i * 3 + j]; return ans; }

Intentaré volver a escribir la respuesta anterior con más detalles sobre por qué es óptima.

El algoritmo A * tomado directamente de wikipedia es

function A*(start,goal) closedset := the empty set // The set of nodes already evaluated. openset := set containing the initial node // The set of tentative nodes to be evaluated. came_from := the empty map // The map of navigated nodes. g_score[start] := 0 // Distance from start along optimal path. h_score[start] := heuristic_estimate_of_distance(start, goal) f_score[start] := h_score[start] // Estimated total distance from start to goal through y. while openset is not empty x := the node in openset having the lowest f_score[] value if x = goal return reconstruct_path(came_from, came_from[goal]) remove x from openset add x to closedset foreach y in neighbor_nodes(x) if y in closedset continue tentative_g_score := g_score[x] + dist_between(x,y) if y not in openset add y to openset tentative_is_better := true elseif tentative_g_score < g_score[y] tentative_is_better := true else tentative_is_better := false if tentative_is_better = true came_from[y] := x g_score[y] := tentative_g_score h_score[y] := heuristic_estimate_of_distance(y, goal) f_score[y] := g_score[y] + h_score[y] return failure function reconstruct_path(came_from, current_node) if came_from[current_node] is set p = reconstruct_path(came_from, came_from[current_node]) return (p + current_node) else return current_node

Así que déjame completar todos los detalles aquí.

heuristic_estimate_of_distance es la función Σ d (x i ) donde d (.) es la distancia de Manhattan de cada cuadrado x i desde su estado objetivo.

Así que la configuración

1 2 3 4 7 6 8 5

tendría una distancia heuristic_estimate_of_distance de 1 + 2 + 1 = 4 ya que cada uno de 8,5 está a una distancia de su posición de gol con d (.) = 1 y 7 está a 2 de su estado de meta con d (7) = 2.

El conjunto de nodos en los que A * busca se define como la posición inicial seguida de todas las posiciones legales posibles. Esto es, digamos que la posición inicial x es la anterior:

x = 1 2 3 4 7 6 8 5

entonces la función neighbor_nodes(x) produce los 2 movimientos legales posibles:

1 2 3 4 7 8 5 6 or 1 2 3 4 7 6 8 5

La función dist_between(x,y) se define como el número de movimientos cuadrados que tuvieron lugar para pasar del estado x al y . En general, esto será igual a 1 en A * siempre para los fines de su algoritmo.

closedset y openset son específicos para el algoritmo A * y pueden implementarse utilizando estructuras de datos estándar (creo que las colas de prioridad) came_from es una estructura de datos utilizada para reconstruir la solución encontrada mediante la función reconstruct_path came_from detalles se pueden encontrar en Wikipedia. Si no desea recordar la solución, no necesita implementar esto.

Por último, abordaré el tema de la optimalidad. Considere el extracto del artículo de A * wikipedia:

"Si la función heurística h es admisible, lo que significa que nunca sobreestima el costo mínimo real de alcanzar la meta, entonces A * es en sí mismo admisible (u óptimo) si no usamos un conjunto cerrado. Si se usa un conjunto cerrado, entonces h también debe ser monotónico (o consistente) para que A * sea óptimo. Esto significa que para cualquier par de nodos adyacentes x e y, donde d (x, y) denota la longitud del borde entre ellos, debemos tener: h (x) <= d (x, y) + h (y) "

Por eso, basta con demostrar que nuestra heurística es admisible y monótona. Para la primera (admisibilidad), tenga en cuenta que, dada cualquier configuración, nuestra heurística (suma de todas las distancias) estima que cada casilla no está limitada solo por movimientos legales y puede moverse libremente hacia su posición de meta, que es claramente una estimación optimista, de ahí nuestra heurística es admisible (o nunca sobreestima ya que alcanzar una posición de meta siempre tomará al menos tantos movimientos como las estimaciones heurísticas).

El requisito de monotonicidad expresado en palabras es: "El costo heurístico (distancia estimada al estado objetivo) de cualquier nodo debe ser menor o igual al costo de la transición a cualquier nodo adyacente más el costo heurístico de ese nodo".

Es principalmente para evitar la posibilidad de ciclos negativos, donde la transición a un nodo no relacionado puede disminuir la distancia al nodo objetivo más que el costo de hacer la transición, lo que sugiere una heurística deficiente.

Para mostrar la monotonicidad es bastante simple en nuestro caso. Cualquier nodo adyacente x, y tiene d (x, y) = 1 según nuestra definición de d. Por eso necesitamos mostrar

h (x) <= h (y) + 1

que es equivalente a

h (x) - h (y) <= 1

que es equivalente a

Σ d (x i ) - Σ d (y i ) <= 1

que es equivalente a

Σ d (x i ) - d (y i ) <= 1

Sabemos por nuestra definición de neighbor_nodes(x) que dos nodos vecinos x, y pueden tener a lo sumo la posición de un cuadrado diferente, lo que significa que en nuestras sumas el término

d (x i ) - d (y i ) = 0

para todos menos 1 valor de i. Digamos que sin pérdida de generalidad esto es verdad de i = k. Además, sabemos que para i = k, el nodo se ha movido en un lugar como máximo, por lo que su distancia a un estado objetivo debe ser a lo sumo uno más que en el estado anterior, por lo tanto:

Σ d (x i ) - d (y i ) = d (x k ) - d (y k ) <= 1

mostrando la monotonicidad. Esto muestra lo que se necesita mostrar, lo que demuestra que este algoritmo será óptimo (en una notación de gran O o una forma asintótica).

Tenga en cuenta que he mostrado optimalidad en términos de notación de gran O, pero todavía hay mucho espacio para jugar en términos de ajustar la heurística. Puede agregarle giros adicionales para que sea una estimación más cercana de la distancia real al estado de la meta, sin embargo , debe asegurarse de que la heurística sea siempre una subestimación. De lo contrario, perderá la optimización.

EDITAR MUCHAS LUNAS DESPUÉS

Al leer esto de nuevo (mucho) más tarde, me di cuenta de que la forma en que lo escribí confunde el significado de la optimalidad de este algoritmo.

Hay dos significados distintos de optimalidad a los que intentaba llegar aquí:

1) El algoritmo produce una solución óptima, que es la mejor solución posible según los criterios objetivos.

2) El algoritmo expande el menor número de nodos de estado de todos los algoritmos posibles utilizando la misma heurística.

La forma más sencilla de comprender por qué necesita la admisibilidad y la monotonicidad de la heurística para obtener 1) es ver A * como una aplicación del algoritmo de la ruta más corta de Dijkstra en un gráfico donde los pesos de los bordes están dados por la distancia del nodo recorrida hasta el momento más la heurística distancia. Sin estas dos propiedades, tendríamos bordes negativos en el gráfico, por lo que los ciclos negativos serían posibles y el algoritmo de ruta más corto de Dijkstra ya no devolvería la respuesta correcta. (Construye un ejemplo simple de esto para convencerte).

2) En realidad es bastante confuso entender. Para entender completamente el significado de esto, hay muchos cuantificadores en esta declaración, como cuando se habla de otros algoritmos, uno se refiere a algoritmos similar como A * que expanden los nodos y buscan sin información a priori (que no sea la heurística). ) Obviamente, uno puede construir un contra-ejemplo trivial de lo contrario, como un oráculo o genio que le dice la respuesta en cada paso del camino. Para comprender en profundidad esta afirmación, sugiero encarecidamente leer el último párrafo de la sección de Historia en Wikipedia , así como examinar todas las citas y notas al pie de la oración.

Espero que esto aclare cualquier confusión restante entre los lectores potenciales.

Puede utilizar la heurística basada en las posiciones de los números, es decir, cuanto más alta sea la suma global de todas las distancias de cada letra desde su estado objetivo, mayor será el valor heurístico. Luego puede implementar la búsqueda A *, que puede demostrarse como la búsqueda óptima en términos de complejidad de tiempo y espacio (siempre que la heurística sea monotónica y admisible). wikipedia