Algoritma A* (A-Star)

📌 Definisaun Kompletu

Algoritma A* (A-Star) mak algoritmu pathfinding no graph traversal ne'ebé uza barak iha komputasaun, jogos, no robotika atu buka dalan efisiente liu husi pontu inísiu ba pontu objetivu. Nia kombina vantajen husi Dijkstra (buka kustu mínimu) no Greedy Best-First Search (uza estimativa) atu hetan rezultadu ne'ebé otimál no lalais.

🧠 Fórmula Prinsipál

f(n) = g(n) + h(n)

Fórmula ida-ne'e mak chave ba A* nia inteligénsia.

🔍 Komponente A*
  • g(n) = Actual Cost: Kustu real husi start too node agora. (Ex: Distância ne'ebé viaja tiha ona.)
  • h(n) = Heuristic Function: Estimativa kustu husi node agora too goal. (Ex: Distância di'ak liu se iha estrada mamuk.)
  • f(n) = Total Estimated Cost: Kombinasaun ba prioridade node.
🔮 Heuristic Function (h(n))

Heuristic maka funsaun estimativa ne'ebé nunka boot liu husi kustu real (se ita hakerek heurística admissível). Nia fo ideia ba algoritma kona-ba "se node ida-ne'e besik liu ba objetivu?". Iha mapa, h(n) bele uza distância Euclidiana ka Manhattan. Heurística ne'ebé di'ak ajuda A* atu la buka node hotu-hotu, maibé fokus ba dalan ne'ebé promete.

✈️ Sinples: h(n) = "Perkiraan", la realidade.

🚗 Exemplo Prátiku (Timor-Leste)

Imajina ita iha Dili (Start) no hakarak ba Same (Goal). A* sei kalkula:

Nodeg(n)h(n) (Estimativa)f(n)
Dili0 km80 km (distância bee nian)80 km
Aileu47 km50 km97 km
Same47 + 60 = 107 km0 km107 km

A* sei foti dalan ho f(n) ki'ik liu durante prosesu.

A* Illustration

⚙️ Oinsá A* Servisu?

1
Inísiu

Tau start node iha lista aberta (open list). g(start)=0, h(start) = estimativa.

2
Ekspansaun

Hili node ho f(n) ki'ik liu. Kalkula g, h, f ba nia vizifiu.

3
Avaliasaun

Se vizifiu iha lista taka (closed),忽略. Se foun ka di'ak, atualiza.

4
Objetivu

Repete too hetan goal node. Rekonstrói dalan.

✅ Vantajen A*
  • Optimal (se heurística admissível)
  • Eficiente liu Dijkstra tanba uza heurística
  • Fleksível ba tipu kustu diferente
⚠️ Konsiderasaun
  • Depende ba heurística ne'ebé di'ak
  • Konsumu memória boot se espasu estado boot
  • La otimál se heurística la admissível

📝 Konkluzaun

Algoritma A* nu'udar solusaun inteligente ba problema buka dalan. Nia la'os de'it buka dalan, maibé buka dalan ne'ebé di'ak liu ho kombinasaun husi esperiénsia (g(n)) no intuisaun (h(n)). Iha jogu, GPS, no inteligénsia artifisiál, A* hanesan ferramenta esensiál.