¿Por qué la complejidad de A * exponencial en la memoria?

Question

Wikipedia dice en A * complejidad lo siguiente (link here):

más problemática que la complejidad del tiempo es el uso de memoria A *’s. En el peor de los casos, también debe recordar un número exponencial de nodos.

no veo que esto es correcto porque:

decir que exploran el nodo A, con sucesores B, C y D. A continuación, añadir B, C y D a la lista de nodos abiertos, cada uno acompañado por una referencia a A, y movemos A desde los nodos abiertos a los nodos cerrados.

Si en algún momento encontramos otra ruta a B (por ejemplo, a través de Q), es mejor que la ruta a A, entonces todo lo que se necesita es cambiar la referencia de B a A para apuntar a Q y actualizar su real costo, g (y lógicamente f).

Por lo tanto, si almacenamos en un nodo su nombre, su nombre de nodo de referencia y sus puntajes g, h y f, entonces la cantidad máxima de nodos almacenados es la cantidad real de nodos en el gráfico, no es ¿eso? Realmente no puedo ver por qué en algún momento el algoritmo necesitaría almacenar una cantidad de nodos en la memoria que sea exponencial a la longitud de la ruta óptima (más corta).

Podría alguien explicar por favor?

---

edición como lo entiendo ahora la lectura de sus respuestas, que estaba razonando desde el punto de vista equivocado del problema. Yo daba por sentado un gráfico dado , mientras que la complejidad exponencial se refiere a un un gráfico conceptual que se define únicamente por un "factor de ramificación".

Answer 1

A * es sólo una versión guiada de búsqueda en amplitud, que es exponencial en complejidad de memoria con respecto a la longitud de la solución.

Cuando se utiliza una heurística constante, A * se convertirá en una búsqueda de amplitud normal; búsqueda de costos uniformes para ser exactos.

Al usar la heurística óptima, A * será O(n) en complejidad de espacio y tiempo si no se tiene en cuenta la complejidad del cálculo heurístico en sí. De nuevo, n es la longitud de la ruta de la solución.

Answer 2

Creo que la exponencialidad entra en juego cuando retrocede al nodo B para expandirla, pero luego retrocede al nodo C para expandirla, y luego retrocede al nodo D. Ahora tenemos que hacer un seguimiento de todos los niños de nodos A, B, C y D

El retroceso se basa en el costo de los bordes para pasar al siguiente nodo, por lo que esta es una posibilidad real, pero es el peor de los casos.

Si cada nodo tiene exactamente 2 niños fuera de ella, y cada nodo tiene el mismo coste, entonces la ecuación es 2^n, donde n es la profundidad de la búsqueda hasta ahora.

Por ejemplo, comienza con el nodo 0. 0 tiene 2 hijos 00 y 01. 00 tiene 2 hijos 000 y 001. En el peor caso con una profundidad de 4, la ecuación es 2^4, donde 2 es el número de hijos que tiene cada nodo y 4 es la profundidad de la búsqueda.

Answer 3

yo no soy un experto, pero me estudiaron el artículo de Wikipedia por un tiempo y mi explicación sería este (espero haber entendido bien :)

decir, que tiene una matriz 4x4 de nodos.
A, B, C, D son las direcciones que podemos tomar en un momento dado (Norte, Sur, Este, Oeste)
El algoritmo A * empieza a buscar.

A
Queue: B, C, D
AA
Queue: B, C, D, AB, AC, AD
AAA -> Goal
Queue: B, C, D, AB, AC, AD, AAB, AAC, AAD
Se ha alcanzado el objetivo, pero todavía hay otras posibilidades a considerar.

D
Queue: B, C, AB, AC, AD, AAB, AAC, AAD
DC
Queue: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD
DCA
cola: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD
DCAB -> Objetivo
cola: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD, DCAA, DCAC, DCAD
etc etc

Como se puede ver, por cada paso dado, se agregan tres nodos más a la cola.
Como A * sigue solo las rutas acíclicas [1], el número máximo de pasos por ruta es 15.
El número máximo de rutas posibles en este caso es 3^15, o direcciones^nodos.
Como cada ruta tiene 15 pasos, los peores pasos que se pueden dar son 15 * 3^15.
En el peor de los casos, cada paso que se realiza es "incorrecto".
En ese caso, 3 * 15 * 3^15 nodos están en la cola antes de encontrar la respuesta.
Por lo tanto, la cantidad de nodos en el peor de los casos que debe mantenerse en la memoria es una constante, a la potencia de la cantidad de nodos disponibles. En otras palabras, el uso de memoria es exponencial a la cantidad de nodos.

[1] http://www.autonlab.org/tutorials/astar08.pdf, deslice 15