¿Por qué Ida $ ^ * $ más rápido que $ ^ * $?¿Por qué Ida $ ^ * $ visita más nodos que $ ^ * $?

Question

Utilicé IDA $ ^ * $ para resolver de manera óptima el rompecabezas y mis amigos usó un $ ^ * $ para ello también (con la misma heurística de la distancia de Manhattan).

Calculé el tiempo de funcionamiento promedio y el número de nodos de mi algoritmo para 20 ejemplos y el algoritmo de mi amigo.El tiempo promedio para mi algoritmo fue mucho más rápido que el algoritmo de mi amigo, pero mi número promedio de nodos visitados es mucho más que el de mi amigo.

Sé IDA $ ^ * $ visita cada nodo más de una vez, pero ¿por qué es más rápido que un $ ^ * $ ?

Answer 1

Dado que ya implementó IDA $ ^ * $ Ciertamente entiende por qué amplía más nodos que un $ ^ * $ , es decir, comienza desde el estado de inicio con un nuevo recorrido de profundidad primero en cada iteración. Tenga en cuenta que primero, el número total de nodos visitados por IDA $ ^ * $ , aunque necesariamente más grande que un $ ^ * $ no es mucho más grande. La razón es que la cantidad de nodos en cada profundidad progresa de acuerdo con una serie geométrica con factor $ b $ , el factor de ramificación. Como resultado, el número de nodos en profundidad $ d $ , $ b ^ d $ , es mucho más grande que la suma de todos los nodos se expandió en las iteraciones anteriores, es decir, $ b ^ d> \ sum_ {d-1} B ^ i $ . A partir de esta diferencia, resulta que Ida $ ^ * $ requiere $ \ frac {b} {b-1} $ Expansiones adicionales que es asintóticamente óptimo como el límite para un gran $ b $ es 1. Conclusión, para Algoritmo visitando todos los nodos En profundidad $ d $ es mucho más difícil que visitar todos los nodos en las profundidades anteriores.

En caso de que desee profundizar más en este problema, le recomiendo encarecidamente que lee el documento original: Korf, Richard E. Profundidad: primera profundización de iterativas: una búsqueda óptima de árbol admisible. Inteligencia artificial (27), 97-109, 1985. Vea en particular el teorema 4.2:

Profundidad: la profundización de iterativas de la profundidad es asintóticamente óptima entre Búsquedas de árboles de fuerza bruta en términos de tiempo, espacio y duración de solución.

Por supuesto, ofrece soluciones óptimas para que sea admisible y, por lo tanto, asintóticamente óptimo. Solo practica los primeros transversales de profundidad y, por lo tanto, es asintóticamente óptimo en términos de espacio (que requiere una buena implementación solo $ o (d) $ ).

En cuanto al momento, ya describí la razón teórica principal, pero avíseme resaltar tres razones principales por las que es tan rápido en la práctica:

1. En primer lugar, para casi todos los propósitos, el tiempo general de ejecución de cualquier algoritmo está dominado por el tiempo que se necesita para ampliar los nodos (otras operaciones son bastante simples y atómicas). De hecho, está en expansión de los nodos que Ida $ ^ * $ puede ser extraordinariamente rápido porque:

   1.1. Ida $ ^ * $ se implementa recursivamente para que todo lo que necesita es tomar el estado dado como un argumento y generar un niño a la vez (para su caso específico, esto Simplemente significa intercambiar el espacio en blanco con un azulejo adyacente, ¡esa es una sola declaración!). Sin embargo, para un $ ^ * $ La operación de expansión requiere: primero, apareciendo un estado de la cola, y luego genera a todos sus hijos (es decir, moviendo el azulejo en blanco en todos Posibles direcciones).

   1.2. Mientras que la operación anterior hace alguna diferencia, el realmente importante es que un $ ^ * $ requiere nodos de clasificación al abrir. Incluso si lo hace con un bucket de 1 (que tomaría $ o (1) $ ), tenga en cuenta que IDA $ ^ * $ no requiere clasificar los nodos en absoluto, de modo que, si bien un $ ^ * $ lleva tiempo que es lineal en el número de nodos expandidos, Ida $ ^ * $ toma ninguno en absoluto.

2. En tercer lugar, una de las contribuciones de los algoritmos de búsqueda de primera primera (como un $ ^ * $ ) es que evitan que se vuelvan a expandir los nodos por El uso de una lista cerrada (que a pesar de su nombre se implementa generalmente como un conjunto!). Ida $ ^ * $ no tiene Duplicate-Detección Mecanismos y, por lo tanto, nuevamente, un $ ^ * $ realiza una operación adicional que no se realiza en absoluto por IDA $ ^ * $ . Si desea saber más sobre Duplicate-Detection en IDA $ ^ * $ Consulte: Reinefeld, a.; Marsland, T. mejoró la búsqueda de profundización iterativa. IEEE Transacciones en el análisis de patrones y la inteligencia de la máquina (16) 7, 701-710, 1994.

El último punto es verdaderamente relevante. En el caso del rompecabezas de los azulejos deslizantes, no hay muchas transposiciones, y el ciclo más corto consiste en 12 movimientos, de modo que el número de re-expansiones no sea tan grande. Poniendo todos estos juntos, Ida $ ^ * $ es una máquina asesina para todos los tamaños del rompecabezas de baldosas deslizantes.

Sin embargo, a pesar de todas sus ventajas, podría no ser de interés práctico en aquellas aplicaciones que tienen una gran cantidad de transposiciones. Ha habido varios intentos de superar esta dificultad.

Con éxito limitado, vea, por ejemplo:

Dow, P. Alex;Korf, Richard E. Duplicar Evitación en profundidad: primera búsqueda con aplicaciones a Treewidth.Conferencia internacional conjunta sobre Inteligencia Artificial, 480-485, 2009.

Espero que esto ayude,