Kanca
Bir şehirde hedefine giderken, hangi sokağı deneyeceğine nasıl karar verirsin? Muhtemelen "hedefe daha yakın görünen" sokağı seçersin — tam mesafeyi bilmesen bile kuşbakışı bir tahminle. A* de tam olarak bunu yapar.
Ya şunu denesen? Bir engelin boyutunu iki katına çıkarsan planlayıcılar hâlâ yol bulur mu?
Ne oldu
A*, her hücre için iki sayıyı toplar:
öncelik = g + h
g = başlangıçtan bu hücreye kadar GERÇEKTEN kat edilen mesafe
h = bu hücreden hedefe olan KUŞBAKIŞI (Öklid) mesafe — bu sezgisel (heuristic) fonksiyon
lib/robotics/planners/astar.ts içindeki heuristic() fonksiyonu tam
olarak bunu hesaplar. A*, açık listedeki en düşük g + h değerine sahip
hücreyi önce genişletir — yani "şimdiye kadar en ucuza gelen VE hedefe
en yakın görünen" hücreyi. Bu, hedeften uzaklaşan yönleri gereksiz yere
taramayı büyük ölçüde engeller.
Eğer h fonksiyonu olmasaydı (sadece g kullanılsaydı), algoritma her
yöne eşit şekilde yayılırdı — bu da Dijkstra algoritmasına dönüşürdü,
doğru ama daha yavaş. h fonksiyonu, aramayı hedefe doğru "iter".
Gerçek dünyada
Harita uygulamaları (yürüyüş/araç rotası) da benzer bir mantıkla çalışır: kuşbakışı mesafe veya tahmini süre, aramayı hedefe doğru yönlendiren bir sezgisel olarak kullanılır. Sezgisel gerçek mesafeyi ASLA abartmamalı (fazla iyimser olmamalı) — aksi halde A* yanlış (optimal olmayan) bir yol bulabilir.
Dene
Önce hiç engel koymadan çalıştır, "Genişletilen düğüm" sayısına bak — küçük bir sayı görürsün çünkü sezgisel fonksiyon aramayı doğrudan hedefe iter. Şimdi başlangıçla hedef arasına, robotun büyük bir çevreleme yapmasını gerektirecek geniş bir engel duvarı koy ve tekrar çalıştır. Düğüm sayısı neden birdenbire artıyor?
Şimdi kâğıt üstünde hesapla: açık listede iki aday hücre var. P hücresinin
gsi 3, hsi 5. Q hücresinin gsi 4, hsi 3. A* önceliği g + h
toplamının EN DÜŞÜK olduğu hücreyi seçer — hangisi önce genişler?
Sonraki
A*'ın ızgarada nasıl aradığını gördün. Sıradaki ders, engellerden kaçınmanın altındaki temel mantığı — bir hücrenin ne zaman "kapalı" sayıldığını — ele alıyor.