¿Cuáles son las diferencias entre A * y la búsqueda codiciosa del mejor primero?

Ambos algoritmos entran en la categoría de «la mejor primera búsqueda» algoritmos, que son algoritmos que pueden utilizar tanto el conocimiento adquirido hasta ahora mientras explora el espacio de búsqueda, denotado por $ g (n) $ , y una función heurística, indicada por $ h (n) $ , que estima la distancia al nodo objetivo, para cada nodo $ n $ en el espacio de búsqueda (a menudo representado como un gráfico).

Cada uno de estos algoritmos de búsqueda define una «función de evaluación», para cada nodo $ n $ en el gráfico (o espacio de búsqueda), denotado por $ f (n) $ . Esta función de evaluación se utiliza para determinar qué nodo, durante la búsqueda, se «expande» primero, es decir, qué nodo se elimina primero del «margen» (o «frontera», o «borde») , para «visitar» a sus hijos. En general, la diferencia entre los algoritmos de la categoría «mejor primero» está en la definición de la función de evaluación $ f (n) $ .

En el caso de el codicioso algoritmo BFS , la función de evaluación es $ f (n) = h (n) $ , es decir, el codicioso algoritmo BFS primero expande el nodo cuya distancia estimada al objetivo es la más pequeña. Entonces, el codicioso BFS no usa el «conocimiento pasado», es decir, $ g (n) $ . De ahí su connotación «codicioso». En general, el algoritmo de BST codicioso es no completo , es decir, siempre existe el riesgo de tomar una ruta que no llevar a la meta. En el codicioso algoritmo BFS, todos los nodos en la frontera (o franja o frontera) se mantienen en la memoria, y los nodos que ya se han expandido no necesitan almacenarse en la memoria y, por lo tanto, pueden descartarse. En general, el BFS codicioso tampoco es óptimo , es decir, la ruta encontrada puede no ser la óptima. En general, la complejidad del tiempo es $ \ mathcal {O} (b ^ m) $ , donde $ b $ es el factor de ramificación (máximo) y $ m $ es la profundidad máxima del árbol de búsqueda. La complejidad del espacio es proporcional al número de nodos en el margen y a la longitud de la ruta encontrada.

En el caso de la A * algoritmo , la función de evaluación es $ f (n) = g (n) + h (n) $ , donde $ h $ es una función heurística admisible . La «estrella», a menudo indicada con un asterisco, *, se refiere al hecho de que A * usa una función heurística admisible, lo que esencialmente significa que A * es óptimo , es decir, siempre encuentra la ruta óptima entre el nodo inicial y el nodo objetivo. Un * también es completo (a menos que haya infinitos nodos para explorar en el espacio de búsqueda). La complejidad del tiempo es $ \ mathcal {O} (b ^ m) $ . Sin embargo, A * necesita mantener todos los nodos en la memoria mientras busca, no solo los que están en el margen, porque A *, esencialmente, realiza una «búsqueda exhaustiva» (que está «informada», en el sentido de que usa una función heurística ).

En resumen, BFS codicioso no está completo, no es óptimo, tiene una complejidad de tiempo de $ \ mathcal {O} (b ^ m) $ y una complejidad espacial que puede ser polinomial. A * es completo, óptimo y tiene una complejidad de tiempo y espacio de $ \ mathcal {O} (b ^ m) $ . Entonces, en general, A * usa más memoria que el codicioso BFS. A * se vuelve impráctico cuando el espacio de búsqueda es enorme. Sin embargo, A * también garantiza que la ruta encontrada entre el nodo inicial y el nodo objetivo es la óptima y que el algoritmo finalmente termina. Greedy BFS, por otro lado, usa menos memoria, pero no proporciona las garantías de optimización e integridad de A *. Entonces, qué algoritmo es el «mejor» depende del contexto, pero ambos son «mejores»: las primeras búsquedas.

Nota: en la práctica, no puede utilizar ninguno de estos algoritmos: puede, por ejemplo, utilice, en su lugar, IDA * .

Comentarios

• Los comentarios no son para discusión extensa; esta conversación ha sido movida al chat .

Según el libro Inteligencia artificial: A Modern Approach (3.ª edición), de Stuart Russel y Peter Norvig, específicamente, sección 3.5.1 Búsqueda codiciosa de lo mejor primero (p. 92)

La búsqueda codiciosa de lo mejor primero intenta expandir el nodo más cercano a la meta, con el argumento de que es probable que conduzca a una solución rápidamente. Por lo tanto, evalúa los nodos utilizando solo la función heurística; es decir, $ f (n) = h (n) $ .

En este En la misma sección, los autores dan un ejemplo que muestra que la búsqueda codiciosa de lo mejor primero no es óptima ni completa.

En la sección 3.5.2 Una búsqueda *: Minimizando el costo total estimado de la solución del mismo libro (p. 93), establece

A * la búsqueda evalúa los nodos combinando $ g (n) $ , el costo para llegar al nodo y $ h (n) $ , el costo para ir del nodo al objetivo $$ f (n) = g (n) + h (n). $$

Dado que $ g (n) $ da el costo de la ruta desde el nodo inicial al nodo $ n $ y $ h (n) $ es el costo estimado de la ruta más barata de $ n $ al objetivo, tenemos $ f (n) $ = costo estimado de la solución más barata a través de $ n $ .

Por lo tanto, si estamos tratando de encontrar la solución más barata, una cosa razonable para probar primero es el nodo con el valor más bajo de $ g (n) + h (n) $ . Resulta que esta estrategia es más que razonable: siempre que la función heurística $ h (n) $ satisfaga ciertas condiciones, la búsqueda A * es completa y óptima. El algoritmo es idéntico a la búsqueda de costo uniforme, excepto que A * usa $ g + h $ en lugar de $ g $

Lo que dijiste no es totalmente incorrecto, pero el algoritmo A * se vuelve óptimo y completo si la función heurística h es admisible, lo que significa que esta función nunca sobreestima el costo de alcanzar la meta. En ese caso, el algoritmo A * es mucho mejor que el algoritmo de búsqueda codiciosa.

Comentarios

• querido, ¿puedes elaborar tu respuesta? Siento decirlo, pero no entendí tu punto.
• @IramShah – TemmanRafk está hablando de la prueba de que A * es óptima y completa. Para hacerlo, se muestra debido a la desigualdad del triángulo que la heurística que estima la distancia restante hasta la meta no es una sobreestimación. Para ver una explicación más completa, consulte en.wikipedia.org/wiki/Admissible_heuri stic