WA*

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)   \begin{equation*} f(x) = g(x) + h(x) \end{equation*}

denkleminin

(2)   \begin{equation*} f(x) = g(x) + W \times h(x), W \ge 1 \end{equation*}

haline getirilmesinden geliyor. Makalede de belirtildiği üzere, W arttıkça sonuca daha çabuk ulaşıyoruz fakat bulduğumuz çözüm en iyi çözümden uzaklaşıyor. Bir ilginç nokta ise, W ile bulacağımız yeni yolun uzunluğu, en iyi yolun uzunluğunun en fazla W katı oluyor.

30 senelik makalede yanlış olacak değil tabii ki ama ben yine de, en azından sonuçları görebilmek için 100 \times 100‘lük uniform bir haritada denemeler yaptım. Örnek harita üzerinde A*’ın bulduğu sonuç aşağıdaki gibi;

a_star

100 x 100’lük haritada A*’ın verdiği sonuç. Uzunluk = 145.279, işlenen düğüm sayısı = 1918.

W=4 verilmiş WA* ise aşağıdaki gibi bir sonuç bulacak.

a_star_hinf_4

100 x 100’lük haritada WA*’ın (W=4) verdiği sonuç. Uzunluk = 147.622, işlenen düğüm sayısı = 113.

Ö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 W ile sınırlaması özelliği ile ömürboyu planlama algoritmaları ve anytime algoritmalarda epey kullanılıyor.

 

One thought on “WA*

  1. Pingback: WA* – Yeni Harita | Orhan Özalp

Comments are closed.