Dynamic Weighting A*

Dynamic Weighting A*

Algoritma Weighting A* (DWA*) merupakan salah  jenis  algoritma  yang menerapkan sistem pencarian solusi dengan memperhitungkan nilai heuristik. Metode ini merupakan perkembangan dari Algoritma A*. Namun  perbedaannya adalah algoritma ini memberikan sebuah nilai bobot yang dinamis terhadap fungsi heuristik h. Dengan menggunakan bobot yang dinamis ini, bisa diasumsikan bahwa pada awal iterasi, sebaiknya pencarian  dilakukan ke segala arah, namun begitu akan mencapai goal state, proses  pencarian bisa difokuskan ke arah yang lebih spesifik.

Untuk dapat melakukan  hal ini, diperlukanlah suatu nilai weight yang dinamis, dimana nilai tersebut  akan semakin kecil apabila sudah mendekati goal. Algorima ini juga masih  menggunakan  fungsi heuristik. Suatu fungsi dapat diterima sebagai fungsi heuristik jika biaya perkiraan yang dihasilkan tidak melebihi biaya  sebenarnya (overestimate). Jika fungsi heuristik overestimate, maka proses pencarian bisa tersesat dan tidak optimal. Fungsi heuristik dikatakan baik  jika memberikan biaya perkiraan yang mendekati biaya sebenarnya. Semakin mendekati biaya sebenarnya, fungsi heuristik tersebut semakin baik. Untuk itu digunakan pembobotan yang dinamis terhadap fungsi heuristic

f(n) = g(n) + w(n) * h(n)

Pada perumusan fungsi heuristik diatas, nilai w(n) haruslah lebih besar dari  1. Pada awal iterasi, sebaiknya digunakan nilai w(n) yang sangat besar, dan pada iterasi berikutnya, nilai w(n) dapat diturunkan secara bertahap. Pada  saat proses akan mencapai goal, maka nilai w(n) yang dipakai harus semakin  mendekati nilai 1. Dari sini bisa dilihat bahwa pada awal iterasi nilai h(n) dianggap penting untuk diperhitungkan, sedangkan pada saat akan mencapai goal, proses pencarian lebih banyak dipengaruhi oleh nilai sebenarnya g(n).

Variasi seperti ini akan sangat terasa kegunaannya pada permasalahan  dengan fungsi heuristik menghasilkan nilai yang bervariasi. Dalam kata lain, bisa terdapat biaya perkiraan yang sangat jauh lebih kecil dibandingkan biaya sebenarnya dan ada juga biaya perkiraan yang sudah sangat mendekati biaya sebenarnya. Hal ini lah yang membedakannya dengan algoritma A*, dimana pada algoritma A* masih ada kemungkinan terjadinya kesalahan dalam membangkitkan simpul yang disebabkan bobot yang dipakai semua simpul adalah sama.

Dynamic Weighting A* biasa digunakan dalam memecahkan masalah rute terpendek atau menemukan lokasi terdekat. 

Dynamic Weighting A* dapat memberikan solusi yang tepat dan waktu eksekusi yang cepat dan penggunaan memory yang kecil. Waktu eksekusi Dynamcin Weighting A* dipengaruhi oleh jumlah node yang ada pada ruang masalah. Waktu eksekusi akan bertambah seiring dengan pertambahan jumlah node. Nilai yang dinamis pada Dynamic Weight A* sangat mempengaruhi dalam menemukan Goal State, nilai w yang tepat akan mengarah pada solusi yang tepat, sedangkan jika nilai w yang tidak tepat akan cenderung membuat pencarian menjadi salah arah.