Quando A* garante um caminho ótimo?

Quando a heurística nunca superestima o custo restante verdadeiro (é admissível) e, em implementações eficientes com h consistente, os empates são tratados direito. Manhattan é admissível numa grade uniforme 4-vizinha; a octil convém aos passos diagonais 8-vizinhos.

Em que a busca gulosa pelo melhor primeiro difere de A*?

A gulosa abre nós só segundo h e ignora g, então pode disparar rumo à meta por terreno caro. A* equilibra o custo já gasto g com a estimativa do resto h por meio de f = g + h.

Para que olhar o conjunto aberto e o fechado?

O conjunto aberto é a fronteira de candidatos; o fechado já foi expandido. O crescimento deles mostra que fração do mapa cada algoritmo explora antes de fixar o caminho.

A* e Dijkstra

Grade 40×28: A*, Dijkstra ou busca gulosa; heurísticas, 4- e 8-vizinhança, paredes e células caras; coloração do conjunto aberto e do fechado.

Sobre o modelo

**A* e Dijkstra** buscam um caminho de pouco custo do início à meta numa grade 40×28. Comparam-se o algoritmo de Dijkstra (custo uniforme), A* com f = g + h e a busca gulosa pelo melhor primeiro, com heurísticas de Manhattan / octil / euclidiana e 4- ou 8-vizinhança. Paredes e células caras desenham-se à mão; vê-se crescer o conjunto aberto e o fechado. A* é o mais eficiente entre os algoritmos ótimos se h for admissível; Dijkstra é o caso h = 0; a gulosa segue só h e pode ser rápida, mas subótima. Busca discreta na grade, sem reparo reiterado do caminho, sem busca por pontos de salto e sem grafos de visibilidade contínuos. Mudam-se o algoritmo, a heurística e a vizinhança: o desenho da expansão e o custo do caminho.

Para quem: Algoritmos e planejamento de caminhos: A*, Dijkstra, heurísticas numa grade.

Conceitos-chave

busca A*
algoritmo de Dijkstra
heurística
conjunto aberto
busca de caminho numa grade
heurística admissível

Como funciona

Numa grade 40×28 busca-se um caminho do início à meta. Dijkstra expande pelo custo g, A* por f = g + h, a gulosa só por h. Heurísticas de Manhattan, octil e euclidiana; 4- ou 8-vizinhança. Na tela, o conjunto aberto e o fechado e o caminho achado.

Fórmulas principais

A*: f(n) = g(n) + h(n), open := min-heap by f

Manhattan h = |Δr| + |Δc|; Octile h = max + (√2−1)·min

Perguntas frequentes

Quando A* garante um caminho ótimo?: Quando a heurística nunca superestima o custo restante verdadeiro (é admissível) e, em implementações eficientes com h consistente, os empates são tratados direito. Manhattan é admissível numa grade uniforme 4-vizinha; a octil convém aos passos diagonais 8-vizinhos.
Em que a busca gulosa pelo melhor primeiro difere de A*?: A gulosa abre nós só segundo h e ignora g, então pode disparar rumo à meta por terreno caro. A* equilibra o custo já gasto g com a estimativa do resto h por meio de f = g + h.
Para que olhar o conjunto aberto e o fechado?: O conjunto aberto é a fronteira de candidatos; o fechado já foi expandido. O crescimento deles mostra que fração do mapa cada algoritmo explora antes de fixar o caminho.

Continue com temas próximos desta categoria — ou todos os 48 em «Engenharia».

Toda a categoria →

NovoEscola

Labirintos e A*

Abrir o simulador

Labirintos perfeitos numa grade 40×28: percurso recursivo, Wilson, Eller ou Prim aleatório; resolve-se com A* (Manhattan, 4-vizinhança). Dá para desenhar paredes e mover o início e a meta.

NovoEscola

Árvore geradora mínima (Prim e Kruskal)

Abrir o simulador

Pontos ao acaso no plano, grafo completo com pesos euclidianos: Prim passo a passo a partir da raiz ou Kruskal com conjuntos disjuntos; compara-se o peso total.

NovoEscola

Planejador RRT

Abrir o simulador

O mesmo mapa de paredes 40×28: amostras ao acaso, nó mais próximo, passo com verificação de colisões, viés de amostragem rumo à meta; botão para comparar com A*.

NovoEscola

Deflexão de viga: carga unitária

Abrir o simulador

Viga biapoiada de Euler–Bernoulli com força P e carga w: deflexão analítica contra a integral do trabalho virtual ∫Mm/EI dx.

NovoEscola

Recipiente de paredes finas sob pressão

Abrir o simulador

Tensões de membrana em cilindro e esfera: circunferencial σθ, longitudinal σz, equivalente de von Mises, verificação de r/t e fator de segurança ao escoamento.

NovoEscola

Engrenagens planetárias

Abrir o simulador

Sol, satélites e coroa interna: equação de Willis; fixe a coroa, o sol ou o porta-satélites e compare as relações de transmissão.

A* e Dijkstra

Sobre o modelo

Como funciona

Fórmulas principais

Perguntas frequentes

Simuladores relacionados

Labirintos e A*

Árvore geradora mínima (Prim e Kruskal)

Planejador RRT

Deflexão de viga: carga unitária

Recipiente de paredes finas sob pressão

Engrenagens planetárias

A* e Dijkstra

Sobre o modelo

Como funciona

Fórmulas principais

Perguntas frequentes