Seguimiento de los estados visitados en Breadth-First Search

Así que estaba tratando de implementar BFS en un rompecabezas de bloques deslizantes (tipo de número). Ahora, lo principal que noté es que si tienes un 4*4tablero, el número de estados puede ser tan grande como 16!para que no pueda enumerar todos los estados de antemano.

Entonces, mi pregunta es ¿cómo hago un seguimiento de los estados ya visitados? (Estoy usando un tablero de clase cada instancia de clase contiene un patrón de tablero único y se crea enumerando todos los pasos posibles del paso actual).

Busqué en la red y aparentemente no vuelven al paso anterior recién completado, PERO también podemos volver al paso anterior por otra ruta y luego volver a enumerar todos los pasos que se han visitado anteriormente. Entonces, ¿cómo hacer un seguimiento de los estados visitados cuando todos los estados aún no se han enumerado? (comparar los estados ya presentes con el paso actual será costoso).

Puede usar un set(en el sentido matemático de la palabra, es decir, una colección que no puede contener duplicados) para almacenar estados que ya ha visto. Las operaciones que necesitará para poder realizar esto son:

• insertando elementos
• probar si los elementos ya están ahí

Casi todos los lenguajes de programación ya deberían tener soporte para una estructura de datos que pueda realizar ambas operaciones en tiempo constante ( ). Por ejemplo:$O(1)$

• set en Python
• HashSet en Java

A primera vista, puede parecer que agregar todos los estados que ha visto a un conjunto como este será costoso en cuanto a memoria, pero no es tan malo en comparación con la memoria que ya necesita para su frontera; si su factor de ramificación es , su frontera crecerá en b - 1 elementos por nodo que visite (elimine 1 nodo de la frontera para "visitarlo", agregue b nuevos sucesores / hijos), mientras que su conjunto solo crecerá en 1 extra nodo por nodo visitado.$b$$b - 1$$1$$b$$1$

En el pseudocódigo, un conjunto de este tipo (para nombrarlo closed_set, para que sea coherente con el pseudocódigo en la wikipedia se podría usar en Breadth-First Search de la siguiente manera:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
    current = frontier.remove_next()

    if current == goal_state:
        return something

    for each child in current.generate_children()
        if child not in closed_set:    // This operation should be supported in O(1) time regardless of closed_set's current size
            frontier.add(child)

    closed_set.add(current)    // this should also run in O(1) time

(algunas variaciones de este pseudocódigo también podrían funcionar, y serían más o menos eficientes dependiendo de la situación; por ejemplo, también podría tomar closed_setpara contener todos los nodos de los que ya ha agregado hijos a la frontera, y luego evitar por completo la generate_children()llamada si currentya está en el closed_set.)

Lo que describí anteriormente sería la forma estándar de manejar este problema. Intuitivamente, sospecho que una "solución" diferente podría ser aleatorizar siempre el orden de una nueva lista de estados sucesores antes de agregarlos a la frontera. De esta manera, no evita el problema de agregar ocasionalmente estados que ya ha expandido anteriormente a la frontera, pero creo que debería reducir significativamente el riesgo de quedarse atascado en ciclos infinitos.

Tenga cuidado : no conozco ningún análisis formal de esta solución que demuestre que siempre evita ciclos infinitos. Si trato de "ejecutar" esto en mi cabeza, intuitivamente, sospecho que debería funcionar, y no requiere memoria adicional. Sin embargo, puede haber casos extremos en los que no estoy pensando en este momento, por lo que simplemente podría no funcionar, la solución estándar descrita anteriormente será una apuesta más segura (a costa de más memoria).

La respuesta de Dennis Soemers es correcta: debe usar un HashSet o una estructura similar para realizar un seguimiento de los estados visitados en BFS Graph Search.

Sin embargo, no responde a su pregunta. ¡Tienes razón, en el peor de los casos, BFS requerirá que guardes 16! nodos Aunque los tiempos de inserción y verificación en el conjunto serán O (1), aún necesitará una cantidad absurda de memoria.

Para solucionar esto, no use BFS . Es intratable para todos los problemas, excepto el más simple, porque requiere tiempo y memoria que son exponenciales en la distancia al estado objetivo más cercano.

Un algoritmo mucho más eficiente en la memoria es la profundización iterativa . Tiene todas las propiedades deseables de BFS, pero usa solo memoria O (n), donde n es el número de movimientos para llegar a la solución más cercana. Todavía puede llevar un tiempo, pero alcanzará los límites de memoria mucho antes que los límites relacionados con la CPU.

Mejor aún, desarrolle una heurística específica de dominio y use la búsqueda A * . Esto debería requerir que examine solo un número muy pequeño de nodos y permita que la búsqueda se complete en algo mucho más cercano al tiempo lineal.

Si bien las respuestas dadas son generalmente ciertas, un BFS en el rompecabezas de 15 no solo es bastante factible, ¡se hizo en 2005! El documento que describe el enfoque se puede encontrar aquí:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

Algunos puntos clave:

• Para hacer esto, se necesitaba memoria externa, es decir, BFS utilizó el disco duro para el almacenamiento en lugar de RAM.
• En realidad, solo hay 15 estados! / 2, ya que el espacio de estado tiene dos componentes mutuamente inalcanzables.
• Esto funciona en el rompecabezas de fichas deslizantes porque los espacios de estado crecen muy lentamente de un nivel a otro. Esto significa que la memoria total requerida para cualquier nivel es mucho más pequeña que el tamaño completo del espacio de estado. (Esto contrasta con un espacio de estado como el Cubo de Rubik, donde el espacio de estado crece mucho más rápidamente).
• Debido a que el rompecabezas de fichas deslizantes no está dirigido, solo debe preocuparse por los duplicados en la capa actual o anterior. En un espacio dirigido, puede generar duplicados en cualquier capa anterior de la búsqueda, lo que hace las cosas mucho más complicadas.
• En el trabajo original de Korf (vinculado anteriormente) en realidad no almacenaron el resultado de la búsqueda: la búsqueda solo calculó cuántos estados había en cada nivel. Si desea almacenar los primeros resultados, necesita algo como WMBFS ( http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf )
• Existen tres enfoques principales para comparar estados de las capas anteriores cuando los estados se almacenan en el disco.
  • El primero está basado en la clasificación. Si ordena dos archivos de sucesores, puede escanearlos en orden lineal para encontrar duplicados.
  • El segundo está basado en hash. Si usa una función hash para agrupar sucesores en archivos, puede cargar archivos que son más pequeños que el espacio de estado completo para verificar si hay duplicados. (Tenga en cuenta que aquí hay dos funciones hash: una para enviar un estado a un archivo y otra para diferenciar los estados dentro de ese archivo).
  • El tercero es la detección duplicada estructurada. Esta es una forma de detección basada en hash, pero se realiza de manera que los duplicados se pueden verificar inmediatamente cuando se generan en lugar de después de que se hayan generado todos.

Hay mucho más que decir aquí, pero los documentos anteriores brindan muchos más detalles.

Irónicamente, la respuesta es "usa el sistema que quieras". Un hashSet es una buena idea. Sin embargo, resulta que sus preocupaciones sobre el uso de la memoria son infundadas. BFS es tan malo en este tipo de problemas que resuelve este problema por usted.

Tenga en cuenta que su BFS requiere que mantenga una pila de estados sin procesar. A medida que avanzas en el rompecabezas, los estados con los que te enfrentas se vuelven cada vez más diferentes, por lo que es probable que veas que cada capa de tu BFS multiplica el número de estados a mirar por aproximadamente 3.

Esto significa que, cuando está procesando la última capa de su BFS, debe tener al menos 16! / 3 estados en la memoria. Cualquiera que sea el enfoque que utilizó para asegurarse de que el ajuste en la memoria será suficiente para garantizar que su lista visitada anteriormente también encaje en la memoria.

Como otros han señalado, este no es el mejor algoritmo para usar. Use un algoritmo que se ajuste mejor al problema.

El problema de los 15 acertijos se juega en un tablero 4x4. La implementación de esto en el código fuente se realiza paso a paso. Al principio, el motor del juego en sí tiene que ser programado. Esto permite jugar el juego por un operador humano. El juego de 15 rompecabezas tiene solo un elemento libre y en este elemento se ejecutan las acciones. El motor del juego acepta cuatro comandos posibles: izquierda, derecha, arriba y abajo. No se permiten otras acciones, y es posible controlar el juego solo con estas instrucciones.

La siguiente capa para jugar es una GUI. Esto es muy importante, ya que permite probar el motor del juego e intentar resolver el juego a mano. Además, una GUI es importante porque tenemos que descubrir posibles heurísticas. Y ahora podemos hablar sobre la IA en sí. La IA tiene que enviar comandos al motor del juego (izquierda, derecha, arriba y abajo). Un enfoque ingenuo para un solucionador sería un algoritmo de búsqueda de fuerza bruta, lo que significa que la IA está enviando comandos aleatorios hasta que se alcanza el estado objetivo. Una idea más avanzada es implementar algún tipo de base de datos de patrones que reduzca el espacio de estado. La primera búsqueda de amplitud no es directamente una heurística, pero es un comienzo. Es igual crear un gráfico para probar posibles movimientos de forma cronológica.

El seguimiento de los estados existentes se puede hacer con un gráfico. Cada estado es un nodo, tiene una identificación y una identificación principal. La IA puede agregar y eliminar nodos en el gráfico, y el planificador puede resolver el gráfico para encontrar una ruta hacia el objetivo. Desde una perspectiva de programación, el motor del juego del rompecabezas 15 es el objeto y la lista de muchos objetos es una lista de arrays. Se almacenan en una clase de gráfico. Darse cuenta de esto en el código fuente es un poco complicado, por lo general, la primera prueba fallará y el proyecto producirá muchos errores. Para gestionar la complejidad, dicho proyecto generalmente se realiza en un proyecto académico, es decir, es un tema para escribir un documento sobre el mismo que puede tener 100 páginas y más.

Enfoques del juego

Es cierto que el tablero tiene $16!$posibles estados También es cierto que el uso de un conjunto de hash es lo que los estudiantes aprenden en los cursos de algoritmos de primer año para evitar la redundancia y el bucle sin fin al buscar un gráfico que puede contener ciclos de gráficos.

Sin embargo, esos hechos triviales no son pertinentes si el objetivo es completar el rompecabezas en la menor cantidad de ciclos de computación. La primera búsqueda de amplitud no es una forma práctica de completar un rompecabezas de movimiento ortogonal. El costo muy alto de una primera búsqueda amplia solo sería necesario si el número de movimientos es de suma importancia por alguna razón.

Descenso de subsecuencia

La mayoría de los vértices que representan estados nunca serán visitados, y cada estado visitado puede tener entre dos y cuatro bordes salientes. Cada bloque tiene una posición inicial y una posición final y el tablero es simétrico. La mayor libertad de elección existe cuando el espacio abierto es una de las cuatro posiciones intermedias. Lo menos es cuando el espacio abierto es una de las cuatro posiciones de las esquinas.

Una función de disparidad razonable (error) es simplemente la suma de todas las disparidades x más la suma de todas las disparidades y y un número que representa heurísticamente cuál de los tres niveles de libertad de movimiento existe debido a la colocación resultante del espacio abierto (medio, borde esquina)

Aunque los bloques pueden alejarse temporalmente de sus destinos para apoyar una estrategia hacia la finalización que requiera una secuencia de movimientos, rara vez hay un caso en el que dicha estrategia supere los ocho movimientos, generando, en promedio, 5.184 permutaciones para las cuales se pueden comparar los estados finales utilizando la función de disparidad anterior.

Si el espacio vacío y las posiciones del bloque 1 al 15 están codificados como una matriz de nibbles, solo se necesitan operaciones de suma, resta y de bits, lo que hace que el algoritmo sea rápido. La repetición de las estrategias de fuerza bruta de ocho movimientos se puede repetir hasta que la disparidad caiga a cero.

Resumen

Este algoritmo no puede circular porque siempre hay al menos una de las permutaciones de ocho movimientos que disminuye la disparidad, independientemente del estado inicial, con la excepción de un estado inicial que ya está completo.