Searching
di dalam AI (Artificial Intelligence) adalah salah satu motode
penyelesaian masalah dengan pencarian solusi pada suatu permasalahan yang
dihadapi.
Teknik searching sendiri terbagi menjadi dua, yaitu:
Teknik searching sendiri terbagi menjadi dua, yaitu:
1.
Blind searching
2.
Heuristic searching
4.1 Metode Pencarian
Buta (Blind Search)
Blind
Searching adalah model pencarian buta atau pencarian yang tidak memiliki
inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
·
Membangkitkan simpul berdasarkan urutan.
·
Kalau ada solusi maka solusi akan ditemukan.
·
Hanya memiliki informasi tentang node yang telah
dibuka (node selanjutnya tidak diketahui).
4.1.1 Breadth First Search
BFS (Breadth
First Search) yaitu model pencarian yang memakai metode melebar. Untuk
mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya
dengan cara membuka node (titik) pada tiap levelnya. Dimulai pada node n,
dan dilanjutkan n+1. Pencarian akan terus dilakukan dari akar kiri ke kanan
hingga hasil ditemukan. Metode ini memiliki keuntungan dan kekurangan, yaitu:
Ø Keuntungan:
·
Tidak akan menemui jalan buntu.
·
Jika ada satu solusi, maka breadth
first akan menemukannya. Dan jika ada lebih dari satu solusi, maka solusi
minimum akan ditemukan.
Ø
Kekurangan:
·
Membutuhkan memori yang cukup banyak,
karena menyimpan semua node dalam satu pohon.
·
Membutuhkan waktu yang cukup lama
karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).
4.1.2 Depth First Search
DFS (Depth-first
Search) sering disebut juga pencarian mendalam. Sesuai dengan
namanya “pencarian mendalam”, DFS tidak mencari solusi per level. Metode ini
melakukan pencarian pada semua node "anaknya" sebelum dilakukan
pencarian ke node-node lain yang selevel. Pencarian dimulai dari node akar ke
level yang lebih tinggi, dan proses terus diulang hingga solusi ditemukan. DFS
memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena
tidak membuka semua node dan jika pencarian tepat, akan menemukan solusi tanpa
harus menguji lebih banyak node. Namun, metode ini tetap memiliki kelemahan,
yaitu memungkinkan hasil tidak ditemukan, dan setiap 1 kali pencarian hanya
akan menghasilkan satu solusi.
4.2 Metode Pencarian Heuristik
Heuristic Search merupakan metode pencarian yang
memperhatikan nilai heuristik (nilai perkiraan). Teknik pencarian
heuristik (heuristic searching) merupakan suatu strategi untuk melakukan
proses pencarian ruang keadaan (state space) suatu problema secara
selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur
yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang
bodoh dan memboroskan waktu. Heuristik adalah sebuah teknik yang mengembangkan
efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan
kelengkapan (completeness).
Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
4.2.1 Generate and Test
Strategi bangkitkan dan uji (generate
and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang
akan dibicarakan. Ini adalah gabungan dari pencarian depth first dengan
pelacakan mundur. Nilai dari pengujian ini berupa "ya" atau
"tidak".
Pendekatan ini meliputi langkah–langkah sebagai berikut :
Pendekatan ini meliputi langkah–langkah sebagai berikut :
- Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.
- Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).
- Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.
Jika
pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan
secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya
(bila ada). Namun, jika ruang problema sangat besar, maka proses ini akan
membutuhkan waktu yang lama.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks.
4.2.2 Hill Climbing
Hill Climbing
(mendaki bukit) merupakan salah satu variasi metode buat dan uji (generate
and test) dimana umpan balik yang berasal dari prosedur uji digunakan untuk
memutuskan arah gerak dalam ruang pencarian (search). Perbedaannya ada
pada feedback dari prosedur test untuk pembangkitan keadaan berikutnya. Tes yang
dilakukan berupa fungsi heuristik akan menunjukkan seberapa baik nilai terkaan
yang diambil terhadap keadaan lain yang memungkinkan.
Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
Dalam prosedur buat dan uji yang murni, respon fungsi uji hanyalah ya atau tidak. Dalam prosedur Hill Climbing, fungsi uji dikombinasikan dengan fungsi heuristik yang menyediakan pengukuran kedekatan suatu keadaan yang diberikan dengan tujuan (goal).
Prosedur Hill Climbing :
- Buatlah solusi usulan pertama dengan cara yang sama seperti yang dilakukan dalam prosedur buat dan uji (generate and test). Periksalah apakah solusi usulan itu merupakan sebuah solusi. Jika ya, berhentilah. Jika tidak, kita lanjutkan ke langkah berikutnya.
- Dari solusi ini, terapkan sejumlah aturan yang dapat diterapkan untuk membuat sekumpulan solusi usulan yang baru.
- Untuk setiap elemen kumpulan solusi tersebut, lakukanlah hal-hal berikut ini :
- Kirimkanlah elemen ini ke fungsi uji. Jika elemen ini merupakan sebuah solusi, berhentilah.
- Jika tidak, periksalah apakah elemen ini merupakan yang terdekat dengan solusi yang telah diuji sejauh ini. Jika tidak, buanglah.
- Ambilah elemen terbaik yang ditemukan di atas dan pakailah sebagai solusi usulan berikutnya. Langkah ini bersesuaian dengan langkah dalam ruang problema dengan arah yang muncul sebagai yang tercepat dalam mencapai tujuan.
- Kembalilah ke langkah 2.
Masalah-masalah yang
mungkin timbul pada prosedur Hill Climbing :
·
Maksimum lokal adalah suatu keadaan
yang lebih baik daripada semua tetangganya namun masih belum lebih baik dari
suatu keadaan lain yang jauh letaknya darinya.
·
Daratan (Plateau) adalah suatu
daerah datar dari ruang pencarian (search) dimana semua himpunan keadaan
tetangganya memiliki nilai yang sama.
·
Punggung (Ridge) adalah suatu daerah
ruang pencarian (search) yang lebih tinggi daripada daerah sekitarnya, namun
tidak dapat dibalikkan oleh langkah–langkah tunggal ke arah manapun.
Solusinya:
·
Melakukan langkah balik (backtracking)
ke simpul yang lebih awal dan mencoba bergerak ke arah yang lain.
·
Melakukan lompatan besar ke suatu arah
untuk mencoba bagian ruang pencarian yang baru.
·
Menerapkan dua atau lebih aturan
sebelum melakukan uji coba. Ini bersesuaian dengan bergerak ke beberapa arah
sekaligus.
Kelemahan pada sistem
ini adalah algoritma akan berhenti ketika mencapai optimum local, urutan
penggunaan operator akan sangat berpengaruh, dan tidak diijinkan untuk melihat
langkah sebelumnya.
Referensi:
http://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik
Tidak ada komentar:
Posting Komentar