Trafik ışıklarının döngüsel olarak değiştiği şehir haritasında en hızlı rotayı bulun.
Yol
Bina
Yeşil Işık
Kırmızı Işık
Başlangıç
Hedef
Bulunan Yol
Algoritma
Adım
Toplam Süre (sn)
Bekleme Süresi (sn)
Ziyaret Edilen Durum
Çalışma Zamanı (ms)
Maks Bellek (durum)
Durum
BFS
-
-
-
-
-
-
-
A*
-
-
-
-
-
-
-
Greedy
-
-
-
-
-
-
-
Problem Tanımı
Bu simülasyonda, şehir haritasında trafik ışıkları döngüsel olarak yeşil ve kırmızı arasında geçiş yapar. Kırmızı ışıkta beklemek gerekir, yeşilde geçilebilir. Amaç, başlangıç noktasından hedefe minimum sürede ulaşmaktır.
Durum Temsili: (x, y, t) şeklinde pozisyon ve zaman adımı.
Işık Mekaniği: Her ışık belirli bir döngüde (örn. 5 sn) yeşil-kırmızı arasında geçiş yapar.
Geçiş: 4 yönlü komşuya ilerlemek; kırmızı ışıkta yerinde beklemek gerekir.
Bekleme Maliyeti: Yerinde beklemek de bir zaman adımı sayılır.
Amaç: En kısa sürede hedefe ulaşmak (toplam zaman = adım sayısı).
Sezgisel Fonksiyonlar
A* ve Greedy yaklaşımları, hedefe olan Manhattan mesafesini kullanır. A* ayrıca şu ana kadar geçen zamanı da dikkate alır.
Manhattan Distance:
h(n) = |x_n - x_goal| + |y_n - y_goal|
A* değerlendirmesi: f(n) = g(n) + h(n), burada g(n) şu ana kadarki geçen zaman.
Greedy yalnızca h(n)'i minimize eder; bu nedenle bazen tuzağa düşebilir.
BFS, tüm olasılıkları sırayla araştırır ve optimal çözümü garanti eder.