algorithm - propiedades - ¿Por qué la complejidad de A*es exponencial en la memoria?

funcion exponencial y logaritmica ejercicios resueltos

Question

Wikipedia dice en A * complejidad lo siguiente ( enlace aquí ):

Más problemático que su complejidad de tiempo es el uso de memoria de A *. En el peor de los casos, también debe recordar un número exponencial de nodos.

No veo que esto sea correcto porque:

Supongamos que exploramos el nodo A, con los sucesores B, C y D. Luego, agregamos B, C y D a la lista de nodos abiertos, cada uno acompañado por una referencia a A, y movemos A de los nodos abiertos a los cerrados. nodos

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

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

¿Podría alguien explicar por favor?

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

Answer 1

A * es solo una versión guiada de la búsqueda de amplitud, que es exponencial en la complejidad de la 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 uniforme para ser exactos.

Cuando se utiliza la heurística óptima, A * será O(n) tanto en la complejidad espacial como temporal si ignoramos la complejidad del cálculo heurístico en sí. Nuevamente n es la longitud de la ruta de la solución.

Answer 2

Creo que la capacidad exponencial entra en juego cuando retrocedes al nodo B para expandirlo, pero luego retrocedes al nodo C para expandirlo, y luego retrocedes al nodo D. Ahora tenemos que seguir la pista de todos los hijos de los 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 hijos fuera de él, y cada nodo tiene el mismo costo, entonces la ecuación es 2 ^ n, donde n es la profundidad de la búsqueda hasta el momento.

Por ejemplo, comienzas con el nodo 0. 0 tiene 2 hijos 00 y 01. 00 tiene 2 hijos 000 y 001. En el peor de los casos con una profundidad de 4, la ecuación es 2 ^ 4, donde 2 es el número de niños cada uno. El nodo tiene y 4 es la profundidad de la búsqueda.

Answer 3

No soy un experto, pero estudié el artículo de Wikipedia por un tiempo y mi explicación sería esta (espero que lo haya entendido bien :)

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

UNA
Cola: B, C, D
Automóvil club británico
Cola: B, C, D, AB, AC, AD
AAA -> Objetivo
Cola: B, C, D, AB, AC, AD, AAB, AAC, AAD
Se ha alcanzado el objetivo, pero todavía hay otras posibilidades a considerar.

re
Cola: B, C, AB, AC, AD, AAB, AAC, AAD
corriente continua
Cola: 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 -> Gol
Cola: B, C, AB, AC, AD, AAB, AAC, AAD, DA, DB, DD, DCB, DCC, DCD, DCAA, DCAC, DCAD
Etcétera etcétera

Como puede ver, por cada paso que se da, se agregan tres nodos más a la cola.
Dado que A * solo sigue 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.
Dado que cada ruta tiene 15 pasos, los pasos más desfavorables son 15 * 3 ^ 15.
En el peor de los casos, cada paso dado 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 del número de nodos disponibles. En otras palabras, el uso de la memoria es exponencial a la cantidad de nodos.

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