WA*, Planning as heuristic search makalesinde denk geldiğim, orada da referans olarak Heuristics kitabının verildiği bir A* optimizasyonu. Linkteki makalede ve diğer bir çok kaynakta heuristic inflation yöntemi olarak da geçiyor.
A* en iyi sonucu bulan fakat performans konusunda sıkıntısı olan bir algoritma. En iyi sonucu bulmanın çok da önemli olmadığı gerçek hayat problemleri için ise WA* önerilmiş. WA*’ın adındaki W, klasik
(1)
denkleminin
(2)
haline getirilmesinden geliyor. Makalede de belirtildiği üzere, arttıkça sonuca daha çabuk ulaşıyoruz fakat bulduğumuz çözüm en iyi çözümden uzaklaşıyor. Bir ilginç nokta ise, ile bulacağımız yeni yolun uzunluğu, en iyi yolun uzunluğunun en fazla katı oluyor.
30 senelik makalede yanlış olacak değil tabii ki ama ben yine de, en azından sonuçları görebilmek için ‘lük uniform bir haritada denemeler yaptım. Örnek harita üzerinde A*’ın bulduğu sonuç aşağıdaki gibi;
verilmiş WA* ise aşağıdaki gibi bir sonuç bulacak.
Örnek haritada bulunan yol uzunlukları çok değişmese de işlenen düğüm sayısı çok azaldı.
Bu algoritma, özellikle tutarlı heuristic fonksiyonları ile kullanıldığında yol uzunluğunu ile sınırlaması özelliği ile ömürboyu planlama algoritmaları ve anytime algoritmalarda epey kullanılıyor.