Seviye Seçimi
Oyun Tahtası
Oyun İstatistikleri
Hamle Sayısı
0
Seviye
1
Optimal Hamle
?
Durum
Oynuyor
Problem Açıklaması
🎯 Hedef:
Kırmızı arabayı (R) sağdaki çıkışa kaydırarak otopark alanından çıkarmak.
📋 Kurallar:
- Arabalar yalnızca kendi yönlerinde (yatay/dikey) hareket edebilir
- Arabalar birbirini geçemez veya üst üste gidemez
- Kırmızı araba her zaman 3. satırda (exit row)
- Her hamle bir aracı boş bir hücreye kaydırmaktır
🔍 State Representation:
State = {vehicle1: (row, col), vehicle2: (row, col), ...}
Her durum, tüm araçların pozisyonlarını içerir. State-space çok büyüktür!
🧮 Algoritma Notları:
- BFS: En kısa çözümü garanti eder (optimal hamle sayısı)
- DFS: Bu problemde uygun değil (döngüler ve çok uzun yollar)
- A*: Heuristic ile daha hızlı (h = kırmızı arabaya olan mesafe + engel sayısı)
- State-space explosion: Ortalama 10,000-50,000 durum ziyaret edilir
Algoritma Çözümü
Heuristic Fonksiyon (A*)
h(state) = blocking_vehicles + distance_to_exit
blocking_vehicles: Kırmızı arabanın önündeki engel sayısı
distance_to_exit: Kırmızı arabanın çıkışa olan Manhattan mesafesi
Bu heuristic admissible'dır çünkü gerçek maliyeti asla aşmaz.
Karmaşıklık Analizi
State Space: O(b^d) - branching factor yüksek
Branching factor (b): Ortalama 4-8 (her durumda kaç araç hareket edebilir)
Solution depth (d): Kolay seviye: 8-15, Zor seviye: 30-50+
Memory: BFS için kritik - her durumu saklamak gerekir