- Şu anki
- Kuyrukta
- Kesinleşen
- Yol
- Kuş uçuşu tahmin
A* Araması
A* araması, Dijkstra algoritması gibi bir başlangıçtan bir hedefe en kısa yolu bulur, ama hedefin kabaca nerede olduğunu bilir. Her düğüm kalan uzaklık için bir tahmin alır, yani hedefe olan düz çizgiyi; arama da her zaman şimdiye kadarki uzaklık artı bu tahmin en düşük olan düğümden devam eder. Oradan başlamak için bir düğüme tıklayın, bir hedef seçin ve adım adım ilerleyerek aramanın hedefe yöneldiğini ve grafın koca köşelerine hiç dokunmadığını görün. Aramayı izlemek için Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Herhangi bir yere atlamak için adım kaydırıcısını sürükleyin. Bir düğümü başlangıç yapmak için ona tıklayın; tıklamayı Hedef'e çevirip başka bir düğüme tıklayarak onu hedef yapın. Her kenardaki sayı o kenarın uzunluğu, her düğümdeki sayı şimdiye kadarki uzaklığı, kesikli çizgi ise kalan uzaklığın kuş uçuşu tahminidir. Grafın altındaki satır, en düşük puan başta olmak üzere kuyruktur ve her düğümün puanını gösterir: şimdiye kadarki uzaklık artı tahmin. Yeni graf başka bir graf oluşturur; kaç düğüm ve kenar olacağını seçin. Pano seçiliyken ok tuşları adım atar, boşluk tuşu oynatır ve duraklatır, Home ve End başa ve sona atlar.
Nasıl çalışır
- Bir düğümü başlangıç yapmak için ona tıklayın. Tıklamayı Hedef'e çevirin ve başka bir düğüme tıklayarak onu hedef yapın.
- Oynat'a basın ya da adım adım ilerlemek için Adım ve Geri'yi kullanın. Aramada herhangi bir yere atlamak için adım kaydırıcısını sürükleyin.
- Kuyruktaki puanları ve kesikli kuş uçuşu tahmini izleyin. Sonunda A*'ın kullandığı düğümleri Dijkstra algoritmasıyla karşılaştırın.
A* araması nasıl çalışır
Başlangıca uzaklık 0 verin ve onu bir kuyruğa ekleyin. Kuyruktaki her düğümün bir puanı vardır: şimdiye kadarki uzaklığı artı kalan uzaklık için bir tahmin. Tekrarlayın: en düşük puanlı düğümü alın ve uzaklığını kesinleştirin. Hedefse durun. Değilse, kesinleşmemiş her komşu için kenarın uzunluğunu düğümün uzaklığına ekleyin; bu, komşunun şimdiye kadarki uzaklığından kısaysa onu düşürün, oraya giden yol olarak düğümü hatırlayın ve komşuyu yeni puanıyla kuyruğa ekleyin.
Tahmin neden asla fazla uzun olmamalı
A*, tahmin hedefi hiçbir zaman gerçekte olduğundan daha uzak göstermediği sürece en kısa yolu bulur: buna kabul edilebilir tahmin denir. Düz çizgi böyle bir tahmindir, çünkü iki yer arasındaki hiçbir yol düz çizgiden kısa değildir. Fazla uzun bir tahmin A*'ın en iyi rotayı atlamasına yol açabilir; her yerde 0 olan bir tahmin ise A*'ı Dijkstra algoritmasına çevirir; bu güvenlidir ama her yöne bakar. Tahmin ne kadar iyiyse A* o kadar az düğüme ihtiyaç duyar. Uygulamada her kenar çizildiği kadar uzundur, yukarı yuvarlanarak; bu yüzden düz çizgi güvenli bir tahmindir.
Sık sorulan sorular
A* araması nedir?
Bir başlangıçtan bir hedefe en kısa yolu bulan bir yol bulma algoritmasıdır. Dijkstra algoritması gibi çalışır, ama kuyruğunu şimdiye kadarki uzaklık artı kalan uzaklık tahminine göre sıralar; böylece her yöne yayılmak yerine hedefe yönelir.
Kabul edilebilir sezgisel nedir?
Hedefe olan uzaklık için, gerçek en kısa uzaklıktan hiçbir zaman uzun olmayan bir tahmindir. Kabul edilebilir bir tahminle A* her zaman en kısa yolu bulur. Haritadaki kuş uçuşu uzaklık klasik örnektir.
A*, Dijkstra algoritmasından hızlı mı?
Genellikle evet, tek bir hedefe giden yola ihtiyacınız ve iyi bir tahmininiz varsa: A* daha az düğümü kesinleştirir, çünkü hedeften uzakta kalan düğümler yüksek puan alır. Tahmin 0 olduğunda Dijkstra algoritmasının yaptığının aynısını yapar. Tüm düğümlere olan uzaklıklara ihtiyacınız varsa Dijkstra algoritması daha iyi bir seçimdir.
A* nerede kullanılır?
Video oyunlarında karakterleri engellerin etrafından dolaştırmak için, rota planlayıcılarda, robot hareket planlamasında ve 15 bulmacası gibi bulmacaları çözen programlarda; orada tahmin, taşların yerlerinden ne kadar uzak olduğunu sayar.
Grafım bir yere gönderiliyor mu?
Hayır. Graf tarayıcınızda oluşturulur ve aranır, son ayarlarınız da bu tarayıcının yerel depolamasında kalır.
Denemeye hazır mısınız?
PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.
Editöre Git