WA* – Yeni Harita

Bir önceki WA* denemesini uniform oluşturulmuş bir harita üzerinde yapmıştım. Yaşar Safkan haritamın tipini beğenmeyince oturdum haritaya elle 1-2 engel koydum :) . Ne kadar karmaşık oldu bilmiyorum ama harita ve A*’ın haritada bulduğu yol aşağıdaki gibi oldu;

A* algoritması. Yol uzunluğu = 33.89, node sayısı = 246.

A* algoritması. Yol uzunluğu = 33.89, node sayısı = 246.

    \[W = 8\]

verilmiş WA* ise aşağıdaki gibi çalıştı;

WA* (W = 8) algoritması. Uzunluk 36.87, node sayısı = 34.

WA* (W = 8) algoritması. Uzunluk 36.87, node sayısı = 34.

Son olarak

    \[W = 2\]

WA* ise aşağıdaki gibi sonuç verdi.

WA* (W = 2) algoritması. Yol uzunluğu = 34.04, node sayısı = 39.

WA* (W = 2) algoritması. Yol uzunluğu = 34.04, node sayısı = 39.

Yine çok büyük fark çıkmadı ama en azından WA*’ı en kısa yoldan saptırabildim.

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.