LogRitmo navegador / ativofase / 02LR / fase 02 · ativaCombine custo percorrido e estimativa até o destino.
Execuções concluídas nesta bancada, medidas durante o playback ativo no navegador e salvas apenas neste dispositivo.
Execute o algoritmo até o fim para transformar esta bancada em uma série de medições reais.
A* Search utiliza relaxamento e uma heurística para priorizar caminhos promissores. Nesta bancada, a estimativa usa a geometria do grafo calibrada pelos pesos para não superestimar o custo restante.
estime o próximo passo
A rota combina distância percorrida e uma heurística admissível, que não pode superestimar o custo restante.
O(E) é um cenário favorável. Nesta bancada, a heurística é calibrada pelos pesos para não superestimar o custo restante, e a fila linear prioriza a compreensão em vez do benchmark.
O algoritmo examina arestas (E) e usa uma fila de prioridade para escolher o próximo vértice. O log V representa os níveis necessários para reorganizar essas escolhas.
Quando V dobra, cada ajuste da fila acrescenta apenas um nível; o trabalho principal ainda acompanha as arestas examinadas.Escolha duas técnicas diferentes. As curvas usam a mesma escala visual para explicar como o custo tende a aumentar.
Use este par para comparar a exploração de um grafo não ponderado com o custo adicional de priorizar caminhos de menor distância. Breadth-First Search tende a crescer mais devagar do que Dijkstra quando aumentam vértices (V) e arestas (E). Isso descreve tendência assintótica, não mede o tempo do seu aparelho.
A* procura um caminho de menor custo priorizando f(n) = g(n) + h(n). O termo g registra o melhor custo já encontrado desde a origem; h estima o que ainda falta. A busca é guiada pela soma dos dois, não apenas pelo nó que parece mais perto do destino.
Para ser admissível, h(n) precisa ser no máximo o custo real restante até a meta. Assim, uma rota ótima ainda mantém uma prioridade compatível com seu custo final e não é descartada por uma previsão otimista demais.
Em busca em grafo, a condição h(n) ≤ c(n, m) + h(m) para cada aresta faz a previsão obedecer ao custo da transição. Com isso, as prioridades não diminuem ao longo de um caminho e um estado fechado não precisa ser reaberto.
Com custos não negativos e heurística admissível e consistente, retirar o destino da min-heap é suficiente para encerrar: nenhum candidato ainda na fronteira pode revelar uma rota mais barata.
f(n) escolhe; g(n) prova; h(n) dirige.Uma implementação conserva uma min-heap, o melhor g por estado e predecessores para recuperar o caminho. É comum inserir uma nova entrada quando surge um custo melhor e ignorar, ao extrair, entradas antigas. A qualidade de h pode reduzir expansões, mas não elimina o custo de memória da fronteira e dos registros.
Dijkstra é a referência quando não há uma estimativa útil; A* acrescenta uma heurística segura para um destino específico. Greedy Best-First Search usa apenas a previsão e pode encontrar uma rota cara. Se houver pesos negativos, essas três escolhas não resolvem o contrato: Bellman-Ford é a alternativa apropriada.
Use A* quando houver um destino claro e uma estimativa barata que respeite o modelo de custo: distância Manhattan em uma grade ortogonal, por exemplo, quando cada movimento custa ao menos uma unidade. Weighted A* aumenta a influência de h e pode encontrar uma rota antes, mas abre mão da optimalidade estrita. Quando a memória for o gargalo, variantes como IDA* trocam espaço por repetição de trabalho.
A mesma rede pode ser explorada com uma fila, uma pilha ou uma função de custo. Os trechos mostram o núcleo da decisão; funções de apoio, como recuperar a rota ou escolher o menor custo, aparecem com nomes descritivos para manter o foco da explicação.
function aStar(graph, start, goal) { // Prioritize cost plus heuristic estimateconst open = [start];const gScore = { [start]: 0 };const closed = new Set();while (open.length) {const node = bestByFScore(open, gScore, goal);if (closed.has(node)) continue;closed.add(node);if (node === goal) return reconstruct(node);for (const edge of graph[node]) {if (closed.has(edge.to)) continue;const score = gScore[node] + edge.weight;if (score < (gScore[edge.to] ?? Infinity)) {gScore[edge.to] = score; if (!open.includes(edge.to)) open.push(edge.to);}}}return null;}