Algoritmo de Dijkstra e Best-First-Search#
O Algoritmo de Dijkstra funciona visitando os vértices no gráfico começando com o ponto de partida do objeto. Em seguida, ele examina repetidamente o vértice mais próximo ainda não examinado, adicionando seus vértices ao conjunto de vértices a serem examinados. Ele se expande para fora desde o ponto de partida até atingir o objetivo. O Algoritmo de Dijkstra tem a garantia de encontrar um caminho mais curto desde o ponto de partida até à baliza, desde que nenhuma das arestas tenha um custo negativo. (Eu escrevo “um caminho mais curto” porque muitas vezes existem múltiplos caminhos equivalentes a curtos). No diagrama seguinte, o quadrado rosa é o ponto de partida, o quadrado azul é o objetivo, e as áreas de teal mostram quais áreas o Algoritmo de Dijkstra digitalizado. As áreas mais claras do teal são aquelas mais distantes do ponto de partida, e assim formam a “fronteira” da exploração:
O algoritmo Greedy Best-First-Search funciona de forma semelhante, excepto que tem alguma estimativa (chamada heurística) de quão longe do objectivo qualquer vértice está. Ao invés de selecionar o vértice mais próximo do ponto de partida, ele seleciona o vértice mais próximo do objetivo. A melhor-primeira-pesquisa gananciosa não é garantia de encontrar um caminho mais curto. No entanto, ele corre muito mais rápido que o Algoritmo de Dijkstra porque usa a função heurística para guiar o seu caminho em direção ao objetivo muito rapidamente. Por exemplo, se o objetivo for para o sul da posição inicial, o Greedy Best-First-Search tenderá a focar em caminhos que levam para o sul. No diagrama seguinte, amarelo representa os nós com alto valor heurístico (alto custo para chegar ao objetivo) e preto representa os nós com baixo valor heurístico (baixo custo para chegar ao objetivo). Mostra que o Greedy Best-First-Search pode encontrar caminhos muito rapidamente em comparação com o Algoritmo de Dijkstra:
No entanto, ambos os exemplos ilustram o caso mais simples quando o mapa não tem obstáculos, e o caminho mais curto é realmente uma linha reta. Vamos considerar o obstáculo côncavo como descrito na seção anterior. O Algoritmo de Dijkstra trabalha mais, mas é garantido encontrar um caminho mais curto:
Greedy Best-First-Search, por outro lado, funciona menos, mas o seu caminho não é tão bom:
O problema é que o Greedy Best-First-Search é “ganancioso” e tenta avançar em direcção ao objectivo mesmo que não seja o caminho certo. Como só considera o custo para chegar à meta e ignora o custo do caminho até agora, continua mesmo que o caminho se tenha tornado realmente longo.
Não seria bom combinar o melhor de ambos? A* foi desenvolvido em 1968 para combinar abordagens heurísticas como a Greedy Best-First-Search e abordagens formais como o Algoritmo de Dijsktra. É um pouco incomum no sentido em que as abordagens heurísticas geralmente lhe dão uma maneira aproximada de resolver problemas sem garantir que você obtenha a melhor resposta. No entanto, A* é construído sobre a heurística, e embora a heurística em si não lhe dê uma garantia, A* pode garantir um caminho mais curto.