Lição
A teoria — Visualizador de algoritmos de busca de caminho
Três dos quatro algoritmos no menu suspenso são o mesmo algoritmo. Todos eles ordenam as células que aguardam para serem exploradas com uma única expressão, f(n) = g(n) + h(n) — custo até agora mais custo estimado restante — e diferem apenas em qual dos dois termos mantêm. Descarte h e você tem o Dijkstra. Ignore g e você tem o Greedy Best-First. O quarto, a busca em largura, é aquilo em que o Dijkstra se reduz quando todos os passos custam o mesmo.
O que significa cada símbolo
g(n)- o custo da rota mais barata encontrada até agora do início até a célula n. Um passo lateral ou vertical custa
1; uma diagonal custa√2, porque o passo é medido como um comprimento em vez de ser contado como um único movimento. h(n)- a estimativa do custo que ainda está por vir. Para o Dijkstra e a busca em largura, ela não é meramente não utilizada — ela é zero, e é precisamente isso que os torna a mesma expressão com um termo faltando.
f(n)- a chave de ordenação: a célula com o menor
fé a próxima a ser explorada. Ela é exibida acima da grade com os próprios números da célula atual substituídos, para que a escolha que o algoritmo acabou de fazer seja visível em vez de apenas declarada. frontier- as células âmbar — descobertas, mas ainda não exploradas. Nós expandidos conta o que saiu deste conjunto, tornando-o uma medida do trabalho realizado, e não da qualidade da resposta.
De onde vem a fórmula
- Defina o que "mais curto" significa antes de escolher um algoritmo. O custo de um caminho é a soma dos comprimentos de seus passos:
1para um movimento lateral ou vertical,√2para uma diagonal. As células não são contadas; as distâncias são somadas. - Agora o laço, que é idêntico para todos os quatro: retire uma célula da fronteira, marque-a como explorada e ofereça cada vizinho passável de volta à fronteira com um
gatualizado. Observe o que este laço nunca menciona — uma heurística, a direção do objetivo ou qual algoritmo você escolheu. - Assim, a única decisão que resta é qual célula retirar, e trata-se de uma única expressão. Ordene por
g + he você tem o A*. Definah = 0e a ordenação é feita apenas pelo custo até agora — esse é o Dijkstra, expandindo-se para fora em anéis porque não tem ideia de onde está o objetivo. Em vez disso, ignorege a ordenação é feita apenas pela estimativa — o Greedy Best-First, correndo em direção ao objetivo e aceitando qualquer rota pela qual tenha chegado. - A busca em largura não ordena de forma alguma: primeiro a entrar, primeiro a sair. Com Permitir diagonais desativado, cada passo custa exatamente
1, portanto a ordem em que as células chegam é a ordem de aumento deg— e a busca em largura, portanto, explora precisamente o mesmo que o Dijkstra explora. Você pode confirmar isso sem gerar a grade novamente: alterne entre os dois e Nós expandidos não se move. Ative as diagonais e o argumento morre com isso, porque uma diagonal custa√2em vez de1e a ordem de chegada deixa de acompanhar o custo.
Como ler o que vê
A pontuação de prioridade fica acima da grade com os próprios g e h da célula atual preenchidos, para que você possa ler a ordenação que produziu a última escolha. Abaixo dela estão duas contagens: Nós expandidos e Comprimento do caminho. Âmbar é a fronteira, índigo é o já explorado. Alterar o algoritmo não gera uma nova grade, e é isso que faz a comparação valer a pena — na mesma disposição para os quatro algoritmos, os Nós expandidos do Dijkstra nunca são menores que os do A*, e os do Greedy Best-First são uma pequena fração de qualquer um deles.
- Pressupõe
- Custos de passo que nunca são negativos e uma grade que não muda enquanto a busca é executada. O início é sempre a célula superior esquerda e o objetivo é a inferior direita. O fechamento de uma célula é definitivo — o laço nunca reavalia uma célula — e isso só é seguro porque nenhuma rota posterior pode chegar com menor custo quando cada passo adiciona uma quantidade não negativa.
- Falha quando
- Nós expandidos é o número que muda mais drasticamente e não é uma medida de qualidade. Escolha o Greedy Best-First: na mesma grade ele explora uma pequena fração do que o A* explora e, na maioria dos layouts, retorna um Comprimento do caminho mais longo. Gere algumas grades novas e observe as duas contagens se moverem em direções opostas. Examinar menos células é uma afirmação sobre o quão duro o algoritmo trabalhou, nunca sobre quão boa foi sua resposta.
Percurso de aprendizagem
Contar trabalho, não segundos
Referências (3)
- Where A*, the f = g + h scoring and the admissibility condition were introduced: P. E. Hart, N. J. Nilsson & B. Raphael, "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4, 100–107, 1968.
- And the algorithm A* generalises, for comparison in the dropdown: E. W. Dijkstra, "A note on two problems in connexion with graphs." Numerische Mathematik 1, 269–271, 1959.
- The fourth option in the dropdown, and the wavefront it spreads: E. F. Moore, "The shortest path through a maze." Proceedings of an International Symposium on the Theory of Switching, Part II, 285–292. Harvard University Press, 1959.