Quais são as diferenças entre A * e melhor busca gananciosa?

Ambos os algoritmos se enquadram na categoria de “melhor primeira pesquisa” algoritmos, que são algoritmos que podem usar tanto o conhecimento adquirido até agora enquanto explora o espaço de pesquisa, denotados por $ g (n) $ , e uma função heurística, denotada por $ h (n) $ , que estima a distância até o nó objetivo, para cada nó $ n $ no espaço de pesquisa (frequentemente representado como um gráfico).

Cada um desses algoritmos de pesquisa define uma “função de avaliação”, para cada nó $ n $ no gráfico (ou espaço de pesquisa), denotado por $ f (n) $ . Esta função de avaliação é usada para determinar qual nó, durante a pesquisa, é “expandido” primeiro, ou seja, qual nó é removido primeiro da “franja” (ou “fronteira”, ou “fronteira”) , de modo a “visitar” seus filhos. Em geral, a diferença entre os algoritmos na categoria “best-first” está na definição da função de avaliação $ f (n) $ .

No caso de o algoritmo BFS ganancioso , a função de avaliação é $ f (n) = h (n) $ , ou seja, o algoritmo guloso BFS primeiro expande o nó cuja distância estimada até o objetivo é a menor. Portanto, o BFS ganancioso não usa o “conhecimento anterior”, ou seja, $ g (n) $ . Daí sua conotação de “ganancioso”. Em geral, o algoritmo guloso do BST não está completo , ou seja, sempre há o risco de seguir um caminho que não trazer para a meta. No algoritmo guloso do BFS, todos os nós na fronteira (ou franja ou fronteira) são mantidos na memória, e os nós que já foram expandidos não precisam ser armazenados na memória e, portanto, podem ser descartados. Em geral, o BFS ganancioso também não é o ideal , ou seja, o caminho encontrado pode não ser o ideal. Em geral, a complexidade do tempo é $ \ mathcal {O} (b ^ m) $ , onde $ b $ é o fator de ramificação (máximo) e $ m $ é a profundidade máxima da árvore de pesquisa. A complexidade do espaço é proporcional ao número de nós na orla e ao comprimento do caminho encontrado.

No caso de o A * algoritmo , a função de avaliação é $ f (n) = g (n) + h (n) $ , onde $ h $ é uma função heurística admissível . A “estrela”, frequentemente indicada por um asterisco, *, refere-se ao fato de que A * usa uma função heurística admissível, o que essencialmente significa que A * é ótimo , ou seja, sempre encontra o caminho ótimo entre o nó inicial e o nó objetivo. Um * também é completo (a menos que haja infinitos nós para explorar no espaço de pesquisa). A complexidade do tempo é $ \ mathcal {O} (b ^ m) $ . No entanto, A * precisa manter todos os nós na memória durante a pesquisa, não apenas os da periferia, porque A *, essencialmente, realiza uma “pesquisa exaustiva” (que é “informada”, no sentido de que usa uma função heurística ).

Em resumo, o BFS ganancioso não é completo, não é ideal, tem uma complexidade de tempo de $ \ mathcal {O} (b ^ m) $ e uma complexidade de espaço que pode ser polinomial. A * é completo, ótimo e tem uma complexidade de tempo e espaço de $ \ mathcal {O} (b ^ m) $ . Portanto, em geral, A * usa mais memória do que o ganancioso BFS. A * torna-se impraticável quando o espaço de busca é enorme. No entanto, A * também garante que o caminho encontrado entre o nó inicial e o nó objetivo é o ideal e que o algoritmo termina eventualmente. O Greedy BFS, por outro lado, usa menos memória, mas não fornece as garantias de otimização e integridade de A *. Portanto, qual algoritmo é o “melhor” depende do contexto, mas ambos são as “melhores” pesquisas iniciais.

Nota: na prática, você não pode usar nenhum desses algoritmos: você pode, por exemplo, use, em vez disso, IDA * .

Comentários

• Os comentários não são para discussão estendida; esta conversa foi movida para o bate-papo .

De acordo com o livro Inteligência Artificial: A Modern Approach (3ª edição), de Stuart Russel e Peter Norvig, especificamente, seção 3.5.1 Greedy best-first search (p. 92)

A melhor pesquisa inicial gananciosa tenta expandir o nó que está mais próximo da meta, com base em que isso é provável que leve a uma solução rapidamente. Assim, ele avalia os nós usando apenas a função heurística; isto é, $ f (n) = h (n) $ .

Neste mesma seção, os autores dão um exemplo que mostra que a melhor pesquisa gananciosa não é ideal nem completa.

Na seção 3.5.2 Uma pesquisa *: Minimizando o custo total estimado da solução do mesmo livro (p. 93), ele afirma

A * a pesquisa avalia os nós combinando $ g (n) $ , o custo para alcançar o nó e $ h (n) $ , o custo para ir do nó até a meta $$ f (n) = g (n) + h (n). $$

Como $ g (n) $ dá o custo do caminho do nó inicial ao nó $ n $ , e $ h (n) $ é o custo estimado do caminho mais barato de $ n $ para a meta, temos $ f (n) $ = custo estimado da solução mais barata por meio de $ n $ .

Assim, se estivermos tentando encontrar a solução mais barata, uma coisa razoável para tentar primeiro é o nó com o valor mais baixo de $ g (n) + h (n) $ . Acontece que essa estratégia é mais do que apenas razoável: desde que a função heurística $ h (n) $ satisfaça certas condições, A * pesquisa é completa e ótima. O algoritmo é idêntico à pesquisa de custo uniforme, exceto que A * usa $ g + h $ em vez de $ g $

O que você disse não está totalmente errado, mas o algoritmo A * torna-se ótimo e completo se a função heurística h for admissível, o que significa que essa função nunca superestima o custo de atingir a meta. Nesse caso, o algoritmo A * é muito melhor do que o algoritmo de pesquisa ganancioso. p>

Comentários

• querida, você pode elaborar sua resposta. Lamento dizer, mas não entendi.
• @IramShah – TemmanRafk está falando sobre a prova de que A * é ideal e completo. Para fazer isso, devido à desigualdade do triângulo, a heurística que estima a distância restante até a meta não é uma superestimativa. Para ver uma explicação mais completa, consulte en.wikipedia.org/wiki/Admissible_heuri stic