Bina planında aynı senaryo için farklı arama algoritmalarının çıkışa ulaşma performansını keşfedin.
Boş Alan
Duvar
Acil Çıkış
Tahliye Edilecek Kişi
Başlangıç Yangını
Bulunan Yol
Algoritma
Adım
Ziyaret Edilen Durum
Çalışma Zamanı (ms)
Maks Bellek (durum)
Durum
BFS
-
-
-
-
-
DFS
-
-
-
-
-
A*
-
-
-
-
-
Greedy
-
-
-
-
-
Problem Tanımı
Bu simülasyonda, rastgele duvarlara ve çıkışlara sahip tek katlı bir bina içinde bulunan kişinin, yayılmakta olan yangın reach etmeden güvenli bir kapıya ulaşması gerekiyor. Yangının başlangıç noktaları ve yayılma hızı sabitlenirken, farklı arama algoritmaları aynı senaryo üzerinde denenir.
Durum Temsili: (x, y, t) şeklinde kişinin konumu ve zaman adımı.
Güvenlik Bilgisi: Her hücredeki sayı, yangının o hücreye kaç adım sonra ulaşacağını gösterir; 'F' etiketi o hücrenin artık yandığını ifade eder.
Geçiş: 4 yönlü komşuya ilerlemek; A*/Greedy yalnız güvenli hücrelere girer, BFS/DFS tehlikeyi göze alır.
Yangın Modeli: Çok kaynaklı BFS ile önceden hesaplanan yangın varış zamanları (duvarlar yangını durdurur).
Amaç: En yakın güvenli çıkışa, yangın ulaşmadan önce varmak.
Sezgisel Fonksiyonlar
A* ve Greedy yaklaşımları, kişinin çıkışa kalan mesafesini Manhattan distance ile tahmin ederken, aynı zamanda yangın varış zamanını da dikkate alır.
Manhattan Distance:
h(n) = |x_{n} - x_{exit}| + |y_{n} - y_{exit}|
A* değerlendirmesi: f(n) = g(n) + h(n), burada g(n) şu ana kadarki gerçek adım sayısıdır.
Yangın güvenliği: Bir hücreye ancak g(n)+1 < fireTime(hücre) koşulu sağlandığında girilebilir.
Greedy, yalnızca h(n)'i minimize eder; bu nedenle yangından kaçışta tuzağa düşebilir.