Reduksi Masalah

 Reduksi Masalah

• Kebanyakan solusi menggunakan pohon OR, dimana lintasan dari awal sampai tujuan tidak terletak pada satu cabang.
• Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.

• Graf AND-OR •Graf AO*

Graf AND-OR
• Pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND.
• Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.
• Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi.
Goal : Ingin Memiliki
Membeli TVPunya UangMencuri TV

Algoritma AND-OR
1. Inisialisasi graf ke node awal. 2. Kerjakan langkah2 berikut hingga node
awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY :
a) Telusuri graf mulai dari node awal dan ikuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tsb. dan belum pernah diekspansi atau diberi label SOLVED.
b) Ambil satu node dan ekspansi node tsb. Jika tidak ada successor maka set F_UTILITY sebagai nilai dari node tsb. Bila tidak demikian, tambahkan successor dari node tsb ke graf dan hitung nilai setiap f’ (hanya gunakan h’ dan abaikan g). Jika f’=0 tandai node tsb dengan SOLVED.
c) Ubah f’ harapan dari node baru yang diekspansi. Kirimkan perubahan ini secara backward sepanjang graf. Jika node berisi suatu arc successor yang semua descendant nya berlabel SOLVED maka tandai node itu dengan SOLVED.