| Algoritma | Sonuçlar | Performans Ölçümleri | |||
|---|---|---|---|---|---|
| Ziyaret Edilen Kareler | Toplam Maliyet | Yol Uzunluğu | Çalışma Zamanı (ms) | Kullanılan Bellek (Düğümler) | |
| BFS | - | - | - | - | - |
| DFS | - | - | - | - | - |
| A* | - | - | - | - | - |
| Çift Yönlü Arama | - | - | - | - | - |
| Greedy Best-First Arama | - | - | - | - | - |
Farklı geçiş maliyetlerine sahip arazilerden oluşan bir haritada başlangıç noktasından (yeşil) hedef noktasına (kırmızı) en düşük maliyetli yolu bulmak.
A* ve Greedy algoritmaları hedefe olan uzaklığı tahmin etmek için sezgisel fonksiyon kullanır:
Manhattan Distance (h):
h(n) = |x_current - x_goal| + |y_current - y_goal|
Bu heuristic arazi maliyetlerini dikkate almaz, sadece geometrik uzaklığı ölçer. Gerçek maliyet her zaman bu tahminden yüksek veya eşit olur.
A* Değerlendirme Fonksiyonu:
f(n) = g(n) + h(n)
• g(n) = başlangıçtan n'e gerçek toplam maliyet (arazilerin maliyetlerinin toplamı)
• h(n) = n'den hedefe tahmini maliyet (Manhattan distance)
• f(n) = n üzerinden giden toplam tahmini maliyet
Greedy Best-First Değerlendirme:
f(n) = h(n)
Sadece hedefe uzaklığa bakar, şimdiye kadar ödenen maliyeti (g) görmezden gelir. Bu yüzden yüksek maliyetli arazilere düşebilir.
Admissible Heuristic Özelliği:
Manhattan distance admissible (kabul edilebilir) bir heuristic'tir çünkü:
h(n) ≤ gerçek_maliyet(n, hedef)
En düşük arazi maliyeti 1 olduğu için, Manhattan distance her zaman gerçek maliyetten küçük veya eşittir. Bu özellik A*'ın optimal çözümü bulmasını garanti eder.
Grid boyutunu seçin, bir algoritma belirleyin ve "Başlat" butonuna tıklayın. Sarı hücreler ziyaret edilenleri, mavi hücreler bulunan optimal yolu gösterir. Tabloda algoritmaların performansını ve toplam maliyetleri karşılaştırabilirsiniz.