Yol Bulma Algoritmaları
Navigasyon uygulaması en kısa yolu nasıl bulur?
Özet
Bir haritada iki nokta arasındaki en iyi yolu bulmak için bilgisayar, başlangıçtan komşu noktalara adım adım yayılır ve nereye baktığını not eder. Genişlik öncelikli arama halka halka yayılır, Dijkstra her adımda en ucuz noktayı seçer, A* ise hedefin yönünü tahmin ederek çok daha az yere bakar. Aynı fikir navigasyon uygulamalarında, oyunlarda ve internetteki veri paketlerinin yolunda kullanılır.
Detay
Yol bulma, bir "graf" üzerinde arama problemidir: noktalar (kavşaklar, ızgara hücreleri) ve aralarındaki bağlantılar (yollar). Genişlik öncelikli arama (BFS) en az adımlı yolu bulur ama her adımı eşit sayar. Edsger Dijkstra'nın 1956'da bulduğu algoritma, bağlantıların farklı maliyetlerini (mesafe, süre, trafik) hesaba katar ve en ucuz yolu garanti eder. 1968'de Hart, Nilsson ve Raphael'in geliştirdiği A*, Dijkstra'ya hedefe kalan mesafenin bir tahminini ekler; tahmin gerçeği aşmadığı sürece yine en ucuz yolu bulur, ama çok daha az noktaya bakar. Derinlik öncelikli ve açgözlü arama ise hızlı olabilir ama en iyi yolu garanti etmez.
Yol Bulma Algoritmaları Değerlendirmesi
Bu içeriği nasıl buldunuz? Yıldızlara tıklayarak puanınızı bırakabilirsiniz.
Yorum ve Değerlendirme Yap
Yorum yazmak ve puan vermek için giriş yapın. Üyelik ücretsizdir.