05.31
Unknown
Salah satu metode pencarian heuristic adalah Dynamic Weighting A*, algoritma ini merupakan perkembangan dari algoritma A*. Asumsi untuk melakukan pencarian ke segala arah pada awal iterasi dan ketika goal state sudah dekat baru pencarian difokuskan kearah goal state merupakan karakteristik dari algoritma ini. Untuk itu digunakan pembobotan yang dinamis terhadap fungsi heuristic
Persamaan di atas merupakan fungsi heuristic dari algoritma DWA*, dengan g(n) merupakan jarak sebenarnya antara dua state, h(n) merupakan jarak perkiraan antara dua state (jarak garis lurus), dan w(n) merupakan bobot dinamis (w >=1). Nilai w(n) diperoleh dari perbandingan antara kedua jarak tersebut, dengan besar w(n) yang semakin mengecil ketika state semakin mendekati Goal State. Nilai dinamis dari algoritma yang lebih besar dari satu (w >= 1) dan semakin mengecil mendekati satu ketika semakin mendekati goal state. Dalam notasi matematika dapat dituliskan sebagai berikut:
Nilai w(n) diperoleh dari rasio antara jarak sebenarnya dengan jarak perkiraan antara dua node. Bobot dinamis ini nilainya akan semakin kecil ketika state mendekati Goal, pengurangan nilai bobot dinamis dilakukan berdasarkan iterasi yang dilakukan selama proses mencari Goal.
Penerapan Algoruitma Dynamic Weighting Pada Penentuan Lokasi Parkir Pada Smart Parking System
Dynamic Weighting A* (DWA*) merupakan algoritma pencarian rute terpendek yang baik. Dalam penyelesaian masalah rute terpendek, algoritma penyelesaian Shortest Path Solution ini merupakan algoritma yang optimal (menemukan rute terpendek) dan complete (selalu menemukan solusi jika solusi ada) [1], sedangkan varian lain dari A* belum tentu optimal dan complete dalam menenentukan solusi.
0 komentar :
Posting Komentar