Visualizador de algoritmos de busca de caminho
veja diferentes algoritmos de busca competirem na mesma grade, fronteira por fronteira
por que as heurísticas importam 🖖
A fórmula f(n)=g(n)+h(n) faz o A* preferir nós que são baratos até agora e ainda parecem próximos do objetivo. Se h nunca superestima o custo restante, o A* mantém sua garantia de caminho mais curto; um h admissível mais forte explora menos células desnecessárias. Alterne o menu suspenso de algoritmo para ver o que acontece ao remover a heurística (Dijkstra), o custo até agora (Greedy) ou toda a pontuação (BFS).
Um laço, quatro personalidades 🖖
Os quatro algoritmos executam exatamente o mesmo laço: retiram a célula mais promissora de uma lista de espera (a fronteira âmbar), marcam-na como visitada (índigo) e devolvem as vizinhas livres à lista. Diferem apenas em como decidem qual célula parece mais promissora. Conclusão: o número de nós expandidos é o verdadeiro placar — menos células índigo significam que o algoritmo chegou ao mesmo objetivo com menos trabalho desperdiçado.
As diagonais podem quebrar a garantia 🖖
Ative 'Permitir diagonal' junto com a heurística de Manhattan e o A* pode devolver silenciosamente um caminho que não é o mais curto. Aqui um passo diagonal custa apenas √2 ≈ 1.41, mas a distância de Manhattan o cobra como 2 — então a heurística superestima, torna-se inadmissível e a garantia de otimalidade se perde. Mude para Euclidiana, que nunca ultrapassa a distância em linha reta, e o caminho mais curto retorna.
Problemas de exemplo
- grade aberta - Obstáculos esparsos produzem um caminho A* quase direto, com muito poucas expansões.
- tipo labirinto - Obstáculos densos forçam o A* a fazer desvios mais longos e mais expansões.
- heurística fraca - Uma heurística mais fraca explora muito mais células antes de encontrar o mesmo caminho.
- dijkstra explora - O Dijkstra ignora o objetivo e se espalha em todas as direções.
- armadilha greedy - O Greedy Best-First avança rapidamente em direção ao objetivo e pode ser atraído para becos sem saída.
- bfs + diagonais - O BFS trata passos diagonais e ortogonais como de custo igual, por isso seu caminho pode diferir do A*.