A* Araması
Dijkstra algoritması bir hedefe giden en kısa yolu bulur, ama aynı anda her yöne, hedeften uzağa bile arar. A* araması tek bir bilgi ekler, hedefin daha ne kadar uzakta olduğuna dair bir tahmin, ve arama birden doğrudan hedefe yönelir.
Fikir
Haritada bir rota ararken, hedefinizden uzaklaşan yollara, ona doğru giden yollar kadar özen göstermezsiniz. A* araması da aynısını yapar. Her düğüm bir puan alır: başlangıçtan şimdiye kadarki uzaklık, g, artı kalan uzaklık için bir tahmin, h. Arama her zaman en düşük puanlı düğümden devam eder, bu yüzden hedef yönündeki düğümler önce gelir.
Adım adım
Başlangıca uzaklık 0 verin ve onu h(start) puanıyla bir kuyruğa ekleyin. Tekrarlayın: en düşük puanlı düğümü alın ve uzaklığını kesinleştirin. Hedefse durun: hatırlanan düğümleri geriye doğru izlemek yolu verir. Değilse, kesinleşmemiş her komşu için bu düğüm üzerinden uzaklığını hesaplayın. Bu, şimdiye kadarki uzaklığından kısaysa onu düşürün, oraya giden yol olarak bu düğümü hatırlayın ve komşuya yeni uzaklığı artı tahmini kadar puan verin. İki puan eşit olduğunda önce tahmini küçük olan düğümü almak genellikle hedefe daha çabuk ulaştırır.
Bir örnek
Başlangıç A, hedef D olsun. A–B 2, B–D 2 uzunluğunda; A–C ise 1, C–D 5. D'ye kuş uçuşu tahminler A'dan 3, B'den 2 ve C'den 3. A, 0 + 3 = 3 puanıyla başlar. A alınınca B 2 + 2 = 4, C de 1 + 3 = 4 puanını alır. Eşitlikte A*, tahmini küçük olan B'yi alır ve B, D'ye 4 + 0 = 4 puanını verir. Artık en düşük puan ve en küçük tahmin D'de olduğundan D alınır: en kısa yol, 4 uzunluğundaki A → B → D'dir ve yanlış yöne giden C hiç kesinleşmez. Dijkstra algoritması ise önce C'yi kesinleştirirdi, çünkü A'ya en yakın düğüm odur.
İyi bir tahmin
Tahmin, hedefe olan gerçek uzaklıktan hiçbir zaman uzun olmamalıdır; böyle bir tahmine kabul edilebilir denir ve onunla A* her zaman en kısa yolu bulur. Düz çizgi kabul edilebilirdir, çünkü hiçbir rota düz çizgiden kısa değildir. Tahmin ayrıca bir düğümden sonrakine bir kenar uzunluğundan fazla düşmüyorsa tutarlıdır ve kesinleşmiş hiçbir düğüme bir daha bakmak gerekmez. Tahmin gerçeğe ne kadar yakınsa A* o kadar az düğüme ihtiyaç duyar. 0 tahmini kabul edilebilir ama işe yaramaz: A* o zaman Dijkstra algoritmasına dönüşür. Fazla büyük bir tahmin A*'ı hızlandırır ama en kısa yolu kaçırabilir.
Tarihçe ve kullanım alanları
Peter Hart, Nils Nilsson ve Bertram Raphael, Stanford Research Institute'ta ilk mobil robotlardan biri olan Shakey üzerinde çalışırken A*'ı 1968'de yayımladı. Önceki sürümlerinin adı A1 ve A2 idi; yıldız, optimal olduğunu kanıtladıkları sürümü gösteriyordu. Bugün A* video oyunlarında karakterleri engellerin etrafından dolaştırır, rotaları ve robot hareketlerini planlar ve 15 bulmacası gibi bulmacaları çözer; orada tahmin, her taşın yerinden ne kadar uzak olduğunu toplar.
Kendiniz keşfedin
Uygulamayı açın ve Adım'a basın. Kenarlardaki sayılar uzunluklarıdır ve burada çizildikleri uzunluğa karşılık gelir; kesikli çizgi ise hedefe olan kuş uçuşu tahmini gösterir. Grafın altındaki kuyruk, düğümleri en düşük puan başta olmak üzere puana göre sıralar. Hedef kesinleştiğinde durum satırı, A*'ın kaç düğümü kesinleştirdiğini Dijkstra algoritmasının kaç düğüme ihtiyaç duyacağıyla karşılaştırır. En büyük farkı görmek için büyük bir grafın uzak bir köşesinde bir hedef deneyin.
Sık sorulan sorular
A*'daki yıldız ne anlama gelir?
Hart, Nilsson ve Raphael önce A1 ve A2 adını verdikleri algoritmaları tanımladı. A* ("A yıldız"), tahmin tutarlı olduğunda, aynı tahmini kullanan benzer algoritmalar arasında en az düğümü genişleterek en kısa yolu bulduğunu kanıtladıkları sürümdü.
A*'ın zaman karmaşıklığı nedir?
En kötü durumda, işe yaramaz bir tahminle A*, Dijkstra algoritmasıyla aynı işi yapar: ikili yığınla O((V + E) log V). İyi bir tahminle düğümlerin yalnızca küçük bir kısmını kesinleştirir; bu yüzden pratikte hızlıdır.
A* için iyi bir sezgisel nasıl olmalı?
Hızlı hesaplanmalı, gerçek uzaklığı asla fazla tahmin etmemeli ve ona olabildiğince yakın olmalı. Yalnızca yukarı, aşağı, sola ve sağa gidilebilen bir ızgarada Manhattan uzaklığı yaygın bir seçimdir; haritada ise kuş uçuşu uzaklık.
Sezgisel fazla tahmin ederse ne olur?
O zaman A* en kısa olmayan bir yol döndürebilir, çünkü daha iyi rotaya bakmadan bitirebilir. Bazı programlar bunu bilerek yapar (ağırlıklı A*): biraz yol kalitesinden vazgeçip çok hız kazanmak için.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
A* aramasını deneyin