| Algoritma | Ziyaret Edilen Durumlar | Yol Uzunluğu (Hareket) | Çalışma Zamanı (ms) | Kullanılan Bellek (Düğüm) |
|---|---|---|---|---|
| BFS | - | - | - | - |
| DFS | - | - | - | - |
| A* | - | - | - | - |
| Greedy | - | - | - | - |
Missionaries and Cannibals, yapay zekada klasik bir constraint satisfaction ve state-space search problemidir. 3 misyoner ve 3 yamyam bir nehrin bir kıyısında durmaktadır. Hepsi karşı kıyıya geçmek istiyor.
Kurallar ve Kısıtlamalar:
State Representation: {m, c, b}
Başlangıç Durumu: {3, 3, 1} - Herkes başlangıç kıyısında, tekne de orada
Hedef Durum: {0, 0, 0} - Herkes hedef kıyıda, tekne de orada
Basit Toplam Heuristic:
h(n) = missionaries_left + cannibals_left
Başlangıç kıyısındaki toplam insan sayısı. Her tekne hareketi en az 1, en fazla 2 kişiyi karşıya taşır.
A* Algoritması:
f(n) = g(n) + h(n)
g(n) = Başlangıçtan n'e kadar yapılan hareket sayısı
h(n) = n'den hedefe tahmini hareket sayısı
Greedy Best-First:
f(n) = h(n)
Sadece heuristic değeri kullanılır, hedefe en yakın görünen durumu seçer.
Admissibility (Kabul Edilebilirlik):
Bu heuristic admissible'dır: h(n) ≤ h*(n)
Çünkü tekne her harekette en fazla 2 kişi taşıyabilir, dolayısıyla minimum hareket sayısını asla fazla tahmin etmez.
Bu sayede A* optimal çözümü garanti eder.
Problem Karmaşıklığı:
State space boyutu: 4 × 4 × 2 = 32 olası durum (ama birçoğu invalid)
Valid durumlar: ~16 durum (constraint violation olmayan)
Optimal çözüm uzunluğu: 11 hareket