Algoritma AO*

Algoritma AO*

• Menggunakan struktur graf. Tiap node pada graf memiliki nilai h’ yang merupakan biaya estimasi jalur dari node itu sendiri sampai suatu solusi.
• Algoritma 1. Diketahui graf yang berisi node
awal (sebut saja INIT). Hitung h’(INIT)
 

2. Kerjakan langkah berikut hingga INIT bertanda SOLVED atau sampai nilai h’(INIT) > FUTILITY :
Teknik Pencarian Heuristik 17/25

a) Ekspan INIT dan ambil salah satu node yang belum pernah diekspan (sebut NODE)
 

b) Bangkitkan successor2 NODE. Jika tidak memiliki successor maka set FUTILITY dengan nilai   h’(NODE). Jika ada successor maka untuk setiap successor (sebut SUCC) yang bukan ancestor dari NODE kerjakan :
i. Tambahkan SUCC ke graf ii. Jika SUCC adalah terminal node tandai
dengan SOLVED dan set nilai h’ = 0 iii. Jika SUCC bukan terminal node, hitung nilai h’.
 

c) Kirimkan informasi baru tsb ke graf dengan cara : tetapkan S adalah node yang ditandai dengan SOLVED atau node yang nilai h’-nya baru saja diperbaiki, dan sampaikan nilai ini ke parent-nya. Inisialisasi S = NODE. 

Kerjakan langkah berikut ini hingga S kosong :

i. Jika mungkin, seleksi dari S node yang tidak memiliki descendant dalam graf yang terjadi pada S. Jika tidak ada, seleksi sebarang node dari S (sebut CURRENT) dan hapus dari S.
 

ii. Hitung biaya tiap2 arc yang muncul dari CURRENT. Biaya ini sama dengan jumlah h’ untuk tiap2 node pada akhir arc ditambah dengan biaya arc itu sendiri. Set h’(CURRENT) dengan biaya minimum yang baru saja dihitung dari setiap arc yang muncul tadi.
 

iii. Tandai jalur terbaik yang keluar dari CURRENT dengan menandai arc yang memiliki biaya minimum.
 

iv. Tandai CURRENT dengan SOLVED jika semua node yang dihubungkan dengannya hingga arc yang baru saja ditandai tadi telah ditandai dengan SOLVED.
 

v. Jika CURRENT telah ditandai dengan SOLVED atau jika biaya CURRENT telah berubah maka status baru ini harus disampaikan ke graf. Kemudian tambahkan semua ancestor dari CURRENT ke S.