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.

One thought on “WA* – Yeni Harita

  1. Çok güzel. Burada ilginç durumlar var:

    A* kullanılınca, burada 246 node ziyaret etmiş, ve yol uzunluğu olarak 33.89 bulmuş (kök ikinin bir katından geliyor sanırım küsurat).

    W=2 iken, yol uzunluğu 34.04 (ne harita çizdiysen neredeyse aynı mesafede alternatif yol var) ama sadece 39 node kontrol etmiş!

    W=8 yapınca, yol biraz daha uzamış ama, node kontrolü 34 olmuş. Yani alt tarafı beş node daha az. Halbuki W=1 (ki bu A* oluyor) ile W=2 arasında incelenen node sayısı altıda birine inmiş. Bu ciddi bir processing power saving durumu.

    Diyesim odur ki, ilginç olan W aralığı, 1 <= W <= 2 aralığında yatıyor gibi. Bu aralıkta, x eksenine W'yu koyup, y ekseninde hem bulunan yol uzunluğunu, hem de ziyaret edilen node sayısını çizsek, bu trade-off durumunun nereye kadar anlamlı olduğunu görebiliriz sanıyorum.

    Tabi, bu W'nun hangi aralıkta mantıklı olduğu, kullanılan graf'ın (harita grafın özel durumu) özelliklerine bağlı. Basit bir kaç engelden kaçılacaksa (senin yaptığın gibi) W=2 6:1 daha az node ziyaret ettirirken, yolda çok az bir artışa sebebiyet veriyor. Yani problem basitse, o kadar ince eleyip sık dokumaya gerek yok, "abi şurdan da gitsek" oluyor…

    Yer buldum ukalalık yapayım dedim :-).

Comments are closed.