ti-enxame.com

O algoritmo guloso de melhor primeira pesquisa é diferente do algoritmo de melhor primeira pesquisa?

O algoritmo guloso da melhor primeira pesquisa é diferente do algoritmo da melhor primeira pesquisa?

O página wiki tem um parágrafo separado sobre o Greedy BFS, mas é um pouco incerto.

Meu entendimento é que o Greedy BFS é apenas o BFS, onde o "melhor nó do OPEN" no algoritmo da wikipedia é uma função heurística que se calcula para um nó. Então, implementando isso:

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

com o "melhor nó do OPEN" sendo uma função heurística que estima o quão perto o nó está do objetivo, é na verdade o BFS ganancioso. Estou certo?

EDIT: Comente a resposta de Anonymouse:

Então, essencialmente, um BFS ganancioso não precisa de uma "lista ABERTA" e deve basear suas decisões apenas no nó atual? Esse 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.
21
Alex

"Melhor primeiro" pode permitir revisar a decisão, enquanto que, em um algoritmo ganancioso, as decisões devem ser finais e não revisadas.

Por exemplo, a pesquisa A * é a melhor primeira pesquisa, mas não é gananciosa.

No entanto, observe que esses termos nem sempre são usados ​​com as mesmas definições. "Ganancioso" geralmente significa que a decisão nunca é revisada, eventualmente aceitando soluções abaixo do ideal em benefício de melhorias no tempo de execução. No entanto, aposto que você encontrará situações em que "ganancioso" é usado para a combinação de "melhor primeiro + profundidade primeiro", como em "tente expandir o melhor próximo passo até chegarmos a um beco sem saída, depois retorne ao passo anterior e continue com o próximo melhor lá "(que eu chamaria de" profundidade priorizada primeiro ").

Além disso, depende de qual nível de abstração você está falando. A * não é ganancioso em "construir um caminho". É bom manter um grande conjunto de caminhos abertos. No entanto, é ganancioso em "expandir o espaço de pesquisa" em direção ao verdadeiro caminho mais curto.

26
Has QUIT--Anony-Mousse

BFS é uma instância da pesquisa em árvore pesquisa em árvore e pesquisa gráfica algoritmos no qual um nó é selecionado para expansão com base na função de avaliação f(n) = g(n) + h(n), onde g(n) é o comprimento do caminho da raiz até n e h(n) é uma estimativa do comprimento do caminho de n para o nó da meta. Em um algoritmo BFS, o nó com a avaliação mais baixa (ou seja, menor f(n)) é selecionado para expansão.

O BFS ganancioso usa a seguinte função de avaliação f(n) = h(n), que é apenas a função heurística h(n), que estima a proximidade de n ao objetivo. Portanto, o BFS ganancioso tenta expandir o nó que é considerado o mais próximo do objetivo, sem levar em consideração o conhecimento previamente coletado (ou seja, g(n)).

Para resumir, a principal diferença entre esses métodos de pesquisa (semelhantes) é a função de avaliação.

Como observação lateral, o algoritmo A * é o melhor algoritmo de busca em que a função heurística h é uma heurística admissível (ou seja, h é sempre uma subestimação da função heurística perfeita h*, Para todos n). A * não é um algoritmo BFS exigente porque sua função de avaliação é f(n) = g(n) + h(n).

2
Hina Alvi

Até onde eu entendi, "melhor pesquisa inicial" é apenas um nome coletivo de uma técnica de pesquisa específica na qual você usa uma função de avaliação heurística h (n). Portanto, A * e a busca por melhor primeira gananciosa são algoritmos que se enquadram nessa categoria.

0
Dominik Antal