| Algoritma | Dağıtım Sonuçları | Performans Ölçümleri | |||
|---|---|---|---|---|---|
| Ziyaret Edilen Hücreler | Toplam Mesafe | Teslim Edilen Paketler | Çalışma Zamanı (ms) | Bellek Kullanımı | |
| BFS | - | - | - | - | - |
| DFS | - | - | - | - | - |
| A* | - | - | - | - | - |
| Çift Yönlü Arama | - | - | - | - | - |
| Greedy Best-First Arama | - | - | - | - | - |
Bir kurye, şehir haritasında depodaki paketleri toplayıp müşterilere teslim etmeli ve en sonunda tekrar depoya dönmelidir. Amaç, minimum mesafe veya minimum sürede tüm paketleri teslim etmektir.
Bu problem çok hedefli olduğu için, her alt-problem (mevcut konum → hedef paket) için sezgisel fonksiyon kullanılır:
Manhattan Distance (h) - Tek Hedef İçin:
h(n) = |x_current - x_target| + |y_current - y_target|
Mevcut konumdan hedef pakete olan tahmini uzaklık.
Nearest Neighbor Heuristic - Çoklu Hedef İçin:
next_target = argmin( h(current, paket_i) ) for all undelivered paket_i
Her adımda, teslim edilmemiş paketler arasından en yakın olanı seç (greedy stratejisi).
A* Değerlendirme Fonksiyonu - Her Alt-Problem İçin:
f(n) = g(n) + h(n)
• g(n) = mevcut konumdan n'e gerçek maliyet
• h(n) = n'den hedef pakete tahmini maliyet (Manhattan distance)
• Toplam maliyet = Σ (her alt-problemin maliyeti) + depoya dönüş maliyeti
Greedy Best-First Değerlendirme:
f(n) = h(n)
Sadece hedefe uzaklığa bakar, şimdiye kadar kat edilen mesafeyi (g) görmezden gelir.
Traveling Salesman Problem (TSP) Benzerliği:
Bu problem TSP'nin bir varyasyonudur. Optimal çözüm NP-Hard'dır ve tüm olası paket sıralarını (n! permütasyon) denemek gerekir.
Kullanılan Yaklaşım: Greedy Nearest Neighbor (polynomial zaman, yaklaşık çözüm)
Zaman Karmaşıklığı: O(n²) - Her paket için en yakın komşuyu bul
Şehir boyutunu ve paket sayısını seçin, bir algoritma belirleyin ve "Dağıtıma Başla" butonuna tıklayın. Sarı hücreler ziyaret edilenleri, mor hücreler kurye rotasını gösterir. Yeşil hücreler teslim edilmiş paketleri işaret eder.