Pertemuan Minggu
ke-4
Hal penting dalam menentukan
keberhasilan sistem berdasarkan kecerdasan adalah dalam pencarian dan pencocokan. Pada dasarnya ada 2 teknik
pencarian danpelacakan yang digunakan, yaitu pencarian buta (blind search) dan pencarianterbimbing
(heuristic search)
4.1 Metode
Pencarian Buta (Blind Search) :
4.1.1 Breadth
First Search
Breadth-First 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).
Semua node pada level n akan
dikunjungi terlebih dahulu sebelum level n+1. Pencarian dimulai dari akar terus
ke level 1 darikiri ke kanan, kemudian ke level selanjutnya hingga solusi
ditemukan
Metode Breadth-First Search
Algoritma
1.Buat suatu variabel Node_List dan tetapkan sebagai keadaan awal.
2. Kerjakan langkah-langkah berikut ini sampai tujuan tercapai atau Node_List dalam keadaan kosong
• Hapus elemen pertama dari Node_List, sebut dengan nama C. Jika Node_Listkosong, keluar.
2. Kerjakan langkah-langkah berikut ini sampai tujuan tercapai atau Node_List dalam keadaan kosong
• Hapus elemen pertama dari Node_List, sebut dengan nama C. Jika Node_Listkosong, keluar.
Pada setiap langkah yang
aturannya cocok dengan C, kerjakan :
(i) Aplikasi aturan tersebut untuk membentuk suatu keadaan baru.
(ii) Jika keadaan awal adalah tujuan yang diharapkan,sukses dan keluar.
(iii) Jika tidak demikian, tambahkan keadaan awal yangbaru tersebut pada akhir Node_List.
(i) Aplikasi aturan tersebut untuk membentuk suatu keadaan baru.
(ii) Jika keadaan awal adalah tujuan yang diharapkan,sukses dan keluar.
(iii) Jika tidak demikian, tambahkan keadaan awal yangbaru tersebut pada akhir Node_List.
Keuntungan
1.Tidak akan menemui jalan buntu.
2.Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.
3. Jika ada satu solusi maka bread-first searchakan menemukannya.
2.Menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti yang paling baik.
3. Jika ada satu solusi maka bread-first searchakan menemukannya.
Kelemahannya
Membutuhkan memori yang cukup
banyak.2. 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.
Proses pencarian dilakukan
pada semua anaknya sebelum dilakukan pencarianke node-node yang selevel.
Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini
diulangi terus hingga ditemukannya solusi.
Algoritma
Algoritma
1. Jika keadaan awal merupakan
tujuan, keluar (sukses).
2. Jika tidak demikian, kerjakan langkah-langkah berikut ini sampai tercapaikeadaan sukses atau gagal.
2. Jika tidak demikian, kerjakan langkah-langkah berikut ini sampai tercapaikeadaan sukses atau gagal.
• Bangkitkan successor C dari
keadaan awal. Jika tidak ada successor,maka akan terjadi kegagalan.
• Panggil depth-first search dengan
C sebagai keadaan awal.
• Jika sukses berikan tanda
sukses. Namun jika tidak, ulangi langkah-2
Keuntungan
·
Memori yang relatif kecil
·
Secara kebetulan, akan menemukan solusi tanpa
harus menguji lebih banyak lagi.
Kelemahan
1. Memungkinkan tidak ditemukannya tujuan
yang diharapkan.
2. Hanya akan mendapatkan 1 solusi pada setiap
pencarian
2 . Pencarian
Heuristik (Heuristic Search)
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 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.
Pencarian buta tidak
selalu dapat diterapkan dengan baik, hal ini disebabkan waktu
aksesnya yang cukup lama serta besarnya memori yang diperlukan. Metodeheuristic search diharapkan bisa menyelesaikan permasalahan yang lebih be-sar.
Metode heuristic search menggunakan suatu fungsi yang menghitung biaya
perkiraan(estimasi) dari suatu simpul tertentu menuju ke simpul tujuan disebut
fungsi heuristic.Sebagai contoh aplikasi yang menggunakan fungsi heuristic :
Google, Deep Blue Chess Machine
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.
Daftar Pustaka :