V-Class (3) SISTEM KECERDASAN BUATAN
SOAL :
1. Jelaskan perbedaan metode Best First Search dengan Problem Reduction dan berikan contohya ?
JAWAB :
1. Jelaskan perbedaan metode Best First Search dengan Problem Reduction dan berikan contohya ?
JAWAB :
1. - Best-First Search merupakan sebuah metode yang membangkitkan simpul dari simpul sebelumnya. Best-first search memilih simpul baru yang memiliki biaya terkecil diantara semua leaf nodes (simpul-simpul pada level terdalam) yang pernah dibangkitkan.
Contoh : Misalkan kita memiliki ruang pencarian
seperti pada gambar berikut. Node M
merupakan keadaan awal dan node T
merupakan tujuannya. Biaya edge yang
menghubungkan node M dengan node A
adalah biaya yang dikeluarkan untuk
bergerak dari kota M ke kota A. Nilai g
diperoleh berdasarkan biaya edge minimal.
Sedangkan nilai h’ di node A merupakan
hasil perkiraan terhadap biaya yang
diperlukan dari node A untuk sampai ke
tujuan. h’(n) bernilai ~ jika sudah jelas tidak
ada hubungan antara node n dengan node
tujuan (jalan buntu). Kita bisa merunut nilai
untuk setiap node.
- Problem Reduction atau yang biasa dikenal dengan constraint, intinya adalah berusaha mengurangi masalah dengan harapan masalah yang bersangkutan menjadi lebih mudah diselesaikan.
Contoh : Anggap A < B
adalah constraint antara variabel A dengan domain DA = { 3..7} dan variabel B dengan domain
DB = { 1..5}. dengan jelas tampak bahwa
bahwa untuk sebagian nilai pada DA tidak ada nilai yang konsisten di DB yang memenuhi constraint A < B dan
sebaliknya. Niai yang demikian dapat dibuang dari domain yang
berkaitan tanpa kehilangan solusi apapun. Reduksi itu aman. Didapatkan domain yang
tereduksi DA = {3,4} dan DB = {4,5}.
Perhatikan bahwa reduksi
ini tidak membuang semua pasangan yang tidak konsisten. Sebagai contoh kumpulan
label (<A, 4>, <B, 4>) masihh dapat dihasilkan dari domain,
tetapi untuk setiap nilai A dari DA adalah mungkin untuk
mencari nilai B yang konsisten dan sebaliknya.
Komentar
Posting Komentar