<![CDATA[
Abstrak
Menyelesaikan permasalahan dalam
bidang kecerdasan buatan memerlukan beberapa teknik searching atau pencarian.
Pertama adalah mendefinisikan ruang masalah,
ke dua mendefinisikan aturan produksi yang digunakan, dan terakhir adalah
memilih metode pencarian yang tepat sehingga dapat menemukan solusi terbaik
dengan usaha minimal. Setiap metode mempunyai karakteristik yang berbeda-beda
dengan kelebihan dan kekurangannya masing-masing.
Metode Best-First
Search (BFS) ini sesuai dengan
namanya membangkitkan simpul berikutnya dari sebuah simpul (yang sejauh ini)
terbaik diantara semua leaf nodes
(simpul-simpul pada level terdalam) yang pernah dibangkitkan. Algoritma BFS ini digolongkan sebagai heuristic search atau informed search. Terdapat dua jenis BFS,
yaitu algoritma Greedy Best First Search
dan algoritma A*.
Pada penyelesaian kasus pencarian rute terpendek dari
13 kota yang dinyatakan dengan simpul-simpul dalam suatu graph dua arah, setiap
angka pada busur menyatakan biaya sebenarnya antara satu kota dengan kota
lainnya. Dengan menggunakan metode Greedy
Best-First Search penelusuran rute terpendek yang dihasilkan
adalah S-B-K-G dengan jarak 135 kilometer. Sedangkan
dengan menggunakan metode A* (A Bintang) penelusuran menghasilkan rute S-A-G = 120. g(G) = 120 & f(G) = 120.
Rute yang dihasilkan dengan menggunakan metode A* merupakan rute terpendek yang
ada di graph tersebut. Hal ini menunjukkan bahwa Greedy Best-First Search tidak
optimal, sedangkan algoritma A* adalah optimal. Tanpa ada batasan waktu
dan memori, A* adalah complete
(selalu menemukan solusi jika solusinya ada).
]]>
Copyrights © 2010
