Ev haritasında engeller arasında gezinerek tüm kirli hücreleri temizleyen robotu farklı arama algoritmalarıyla karşılaştırın.
| Algoritma | Temizlenen Hücre | Toplam Adım | Kapsama | Çalışma Zamanı (ms) | Maks Bellek (düğüm) |
|---|---|---|---|---|---|
| BFS | - | - | - | - | - |
| DFS | - | - | - | - | - |
| A* | - | - | - | - | - |
| Çift Yönlü | - | - | - | - | - |
| Greedy | - | - | - | - | - |
Robot süpürge problemi, çok hedefli bir kapsama görevi olarak modellenebilir. Robot, şarj istasyonundan başlayarak engelli bir grid üzerinde dağılmış kirli hücrelerin tamamını temizlemeye çalışır.
Bu sahne, çoklu hedefli arama stratejilerini, sezgisel fonksiyonların etkisini ve farklı önceliklendirme tekniklerinin kapsama yüzdesine nasıl yansıdığını incelemek için tasarlanmıştır.
A* ve Greedy arama, Manhattan distance kullanarak hedefe olan tahmini mesafeyi değerlendirir. Ayrıca robot bir sonraki kirli hedefi seçerken hem uzaklık hem de kir düzeyine göre bir önceliklendirme uygular.
Manhattan Distance (h):
h(n) = |x_{current} - x_{target}| + |y_{current} - y_{target}|
Grid tabanlı hareketlerde diagonal adım olmadığı için Manhattan distance admissible bir sezgisel olup A* algoritmasının optimal rota bulmasına yardımcı olur.
A* Değerlendirme Fonksiyonu:
f(n) = g(n) + h(n)
Greedy Hedef Seçimi: