Macam-Macam
Algoritma Pencarian
Permasalah pencarian adalah merupakan yang
sering dijumpai oleh peneliti bidang Kecerdasan Buatan. Permasalahan ini
merupakan hal penting dalam menentukan keberhasilan system kecerdasan buatan. Menurut
sumber, ada 3 bagian dalam metode pencarian.
Yang pertama adalah metode yang sederhana
yang hanya berusaha mencari kemungkinan penyelesaian. Metode yang termasuk
padabagian ini adalah dept-first search, hill climbing, breadth-first search,
beam search dan best-first search.
Yang kedua yaitu metode yang lebih kompleks
yang akan mencari jarak terpendek. Metode ini adalah British Museum Procedure,
Branch and Bound, Dynamic Programming dan A*. Metode-metode ini digunakan pada
saat harga perjalanan untuk mencari kemungkinan menjadi perhitungan.
Yang ketiga, yaitu beberapa prosedur/metpde
yang kita terapkan saat kita berhadapan dengan musuh. Prosedur ini adalah
minimax search, alpha-beta prunning. Metode ini banyak digunakan pada
program-program permainan seperti catur dsb.
Berikut merupakan bagan untuk Metode Searching:
Begitulah
bagannya.... tapi kali ini saya hanya akan berbagi tentang Beam A* saja..
monggo disimak.
Algoritma ini memberikan sedikit variasi pada A*,
yaitu dengan membatasi simpul yang bisa disimpan di dalam OPEN.
Ketika jumlah simpul di OPEN sudah melebihi batas tertentu,
maka simpul dengan nilai f terbesar akan dihapus. Sedangkan
jumlah simpul yang di dalam CLOSED tetap dibiarkan tanpa batasan
karena simpul yang di dalam CLOSED memang tidak mungkin
dihapus. Dengan membatasi jumlah simpul di OPEN, maka pencarian
menjadi lebih terfokus seperti sinar (beam). Sehingga variasi ini
dinamakan Beam A*.
Implementasi algoritma BA* sama dengan A* tetapi ada
sedikit fungsi tambahan untuk pengecekan dan penghapusan simpul terburuk diOPEN.
Algoritma Beam A* menggunakan dua senarai: OPEN danCLOSED.
OPEN adalah adalah
senarai (list) yang digunakan untuk menyimpan simpul-simpul yang pernah
dibangkitkan dan nilai heuristiknya telah dihitung tetapi belum terpilih
sebagai simpul terbaik (best node). Dengan kata lain, OPEN berisi
simpul-simpul yang masih memiliki peluang (peluangnya masih terbuka)
untuk terpilih sebagai simpul terbaik.
CLOSED adalah senarai untuk menyimpan simpul-simpul yang
sudah pernah dibangkitkan dan sudah pernah terpilih sebagai simpul terbaik.
Artinya, CLOSED berisi simpul-simpul yang tidak mungkin
terpilih sebagai simpul terbaik (peluang untuk terpilih sudah tertutup).
Terdapat tiga kondisi bagi setiap sukseror yang
dibangkitkan, yaitu : sudah berada di OPEN, sudah berada di CLOSED,
dan tidak berada diOPEN maupun CLOSED. Pada ketiga
kondisi tersebut diberikan penanganan yang berbeda-beda.
Jika suksesor sudah pernah berada di OPEN,
maka dilakukan pengecekan apakah perlu pengubahan parent atau
tidak tergantung pada nilai g-nya melalui parent lama
atau parent baru. Jika melalui parent baru
memberikan nilai g yang lebih kecil, maka dilakukan pengubahan parent.
Jika pengubahan parent dilakukan, maka dilakukan pula
perbaruan (update) nilai g dan f pada
suksesor tersebut. Dengan perbaruan ini, suksesor tersebut memiliki kesempatan
yang lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor sudah pernah berada di CLOSED,
maka dilakukan pengecekan apakah perlu pengubahan parent atau
tidak. Jika ya, maka dilakukan perbaruan nilai g dan f pada
suksesor tersebut serta pada semua “anak cucunya” yang sudah pernah berada di OPEN.
Dengan perbaruan ini, maka semua anak cucunya tersebut memiliki kesempatan
lebih besar untuk terpilih sebagai simpul terbaik (best node).
Jika suksesor tidak berada di OPEN maupun CLOSED,
maka suksesor tersebut dimasukkan ke dalam OPEN. Tambahkan suksesor
tersebut sebagai suksesornya best node. Hitung biaya suksesor
tersebut dengan rumus f = g + h..
Reference:
0 komentar:
Posting Komentar