Navigasyon en iyi rotayı nasıl bulur? Dijkstra ve A* | Meraklı Mühendislik #03

Eğitmen: Dr. Süleyman Burak ÇELİK

Navigasyonun önerdiği daha uzun yol neden daha hızlı olabilir? İki köprülü temsili bir 3D şehirden başlayarak en iyi rota hesabını adım adım kuruyoruz. Önce yolculuğun maliyetini tanımlıyor, sonra kavşakları düğümlere ve yolları ağırlıklı bağlantılara dönüştürüyoruz. Altı düğümlük yönlü örnekte Dijkstra'nın öncelik kuyruğunu, gevşetmeyi ve önceki düğümlerden rotanın geri kurulmasını izliyoruz. A* bölümünde f = g + h önceliğini, kuş uçuşu mesafe / en yüksek hız ile kurulan zaman alt sınırını, kabul edilebilirlik ve tutarlılık koşullarını inceliyoruz. Fazla tahminin en iyi yolu nasıl kaçırabildiğini, bir köprü kapandığında hesabın nasıl değiştiğini ve negatif ağırlıkta neden Bellman–Ford gibi başka bir yönteme ihtiyaç duyulduğunu ayrı örneklerle görüyoruz. Son bölümde dönüş kısıtları, veri yapıları ve büyük yol ağlarına geçiyoruz. Şehir örneğindeki 100 ve 72 düğüm karşılaştırması yalnız incelenen düğüm sayısıdır; gerçek trafik verisi veya belirli bir navigasyon uygulamasının hız ölçümü değildir.