A* arama
Yön duygusu olan Dijkstra. Her yerin maliyetine kalan maliyetin tahminini ekler, bu yüzden önce hedefe en yakın görünen yerleri dener.
- süre O((V + E) log V)
- bellek O(V)
- öncelikli kuyruk kullanır
Bunlar ne demek?
- Maliyet: bir hamlenin bedeli. Labirentte toprak 1, çamur 3, su 9 tutar; grafta kenardaki sayıdır.
- Öncelikli kuyruk: ilk gelenin değil, en ucuzun önce geçtiği bir kuyruk.
- Tahmin (h): kalan maliyet hakkında bir tahmin. A* ancak tahmin hiç fazla olmazsa kesin kalır.
- Kenar gevşetme: mevcut yerden geçmenin bir komşuya daha düşük maliyet verip vermediğine bakmak ve veriyorsa onu almak.
- kuyrukta
- şimdiki
- bitti
- en ucuz yol
- toprak · 1
- çamur · 3
- su · 9
- duvar
Yeni: Başlangıç A1, maliyet 0 ve hedefe tahmin 26. Kuyruktaki tek eleman.
Boşluk: oynat veya duraklat. Sol ve sağ oklar: adım adım. Home ve End: atla.
Şunu deneyin: Açık alanı seçin ve Dijkstra ile A* arasında geçiş yapın: ikisi de aynı maliyette bir yol bulur, ama A* kuyruktan çok daha az kare alır.
Nasıl çalışır
A*, Dijkstra gibi çalışır ama kuyruğu f = şimdiye kadarki maliyet + h değerine göre sıralar; h kalan maliyeti tahmin eder. Labirentte h, duvarları ve çamuru yok sayarak M'ye kadar olan hamle sayısıdır; grafta düz çizgi mesafesinin 10'a bölümüdür. h hiçbir zaman fazla tahmin etmedikçe, A*'ın hedefi aldığı andaki yolu en ucuz yoldur, tıpkı Dijkstra'daki gibi. Tahmin ne kadar iyiyse o kadar az yere bakması gerekir.
Ne zaman iyi bir seçimdir
Tek bir hedef aradığınızda ve ne kadar uzakta olduğunu tahmin edebildiğinizde A* kullanın: oyunlarda yol bulma, robotlar, haritada rota planlayıcılar. h = 0 ile tam olarak Dijkstra'dır. Fazla tahmin edebilen bir tahmin A*'ı hızlandırır ama en ucuz yolu kaçırtabilir.