algorithm - heuristica - algoritmo heuristico ejemplo

¿Es diferente el primer algoritmo de búsqueda codicioso del primer algoritmo de búsqueda?

Question

¿Es diferente el primer algoritmo de búsqueda codicioso del primer algoritmo de búsqueda?

La página wiki tiene un párrafo separado sobre Greedy BFS, pero no está muy claro.

Tengo entendido que Greedy BFS es solo BFS donde el "mejor nodo de OPEN" en el algoritmo de wikipedia es una función heurística que se calcula para un nodo. Entonces implementando esto:

OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
 1. Remove the best node from OPEN, call it n, add it to CLOSED.
 2. If n is the goal state, backtrace path to n (through recorded parents) and return path.
 3. Create n''s successors.
 4. For each successor do:
   a. If it is not in CLOSED: evaluate it, add it to OPEN, and record its parent.
   b. Otherwise: change recorded parent if this new path is better than previous one.
done

con "el mejor nodo de OPEN" siendo una función heurística que estima qué tan cerca está el nodo del objetivo, es realmente BFS codicioso. Estoy en lo cierto

EDITAR: Comentar sobre la respuesta de Anonymouse:

¿Esencialmente, un BFS codicioso no necesita una "lista ABIERTA" y debería basar sus decisiones solo en el nodo actual? Es este algoritmo GBFS:

1. Set START as CURRENT node
2. Add CURRENT to Path [and optinally, to CLOSED?]
3. If CURRENT is GOAL, exit
4. Evaluate CURRENT''s successors
5. Set BEST successor as CURRENT and go to 2.

Answer 1

"Mejor primero" podría permitir revisar la decisión, mientras que, en un algoritmo codicioso, las decisiones deben ser definitivas y no revisadas.

Por ejemplo, A * -search es la mejor primera búsqueda, pero no es codicioso.

Sin embargo, tenga en cuenta que estos términos no siempre se utilizan con las mismas definiciones. "Codicioso" por lo general significa que la decisión nunca se revisa, y finalmente se aceptan soluciones subóptimas en beneficio de las mejoras en el tiempo de ejecución. Sin embargo, apuesto a que encontrará situaciones en las que se usa "codicioso" para la combinación de "mejor primero + profundidad primero", como en "intentar expandir el mejor paso siguiente hasta que lleguemos a un callejón sin salida, luego volver al paso anterior y continuar con el siguiente mejor allí "(lo que yo llamaría una" profundidad priorizada primero ").

Además, depende de qué nivel de abstracción está hablando. A * no es codicioso en "construir un camino". Está bien mantener un gran conjunto de caminos abiertos alrededor. Sin embargo, es codicioso en "expandir el espacio de búsqueda" hacia el verdadero camino más corto.

Answer 2

BFS es una instancia de búsqueda de árbol y algoritmos de búsqueda gráfica en los que se selecciona un nodo para la expansión en función de la función de evaluación f(n) = g(n) + h(n) , donde g(n) es la longitud de la ruta desde la raíz de n y h(n) es una estimación de la longitud de la ruta desde n hasta el nodo objetivo. En un algoritmo BFS, el nodo con la evaluación más baja (es decir, la f(n) más baja) se selecciona para la expansión.

Greedy BFS utiliza la siguiente función de evaluación f(n) = h(n) , que es solo la función heurística h(n) , que estima la proximidad de n al objetivo. Por lo tanto, BFS codicioso intenta expandir el nodo que se cree que está más cerca del objetivo, sin tener en cuenta el conocimiento previamente recopilado (es decir, g(n) ).

Para resumir, la principal diferencia entre estos métodos de búsqueda (similares) es la función de evaluación.

Como nota al margen, el algoritmo A * es el primer algoritmo de búsqueda en el que la función heurística h es una heurística admisible (es decir, h es siempre una subestimación de la función heurística perfecta h* , para todas las n ). A * no es un algoritmo BFS sucio porque su función de evaluación es f(n) = g(n) + h(n) .

Answer 3

Por lo que yo entiendo, "la mejor primera búsqueda" es solo un nombre colectivo de una técnica de búsqueda particular en la que se utiliza una función de evaluación heurística h (n). Por lo tanto, A * y la mejor búsqueda codiciosa son algoritmos que entran en esta categoría.