Metode Pencarian Dan Pelacakan I

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.

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.

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.

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

1. Jika keadaan awal merupakan tujuan, keluar (sukses).    
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.

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 :

·        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.

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 :

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 :

http://diniaprillia9496.blogspot.co.id/2016/10/4-metode-pencarian-dan-pelacakan-1.html

https://www.scribd.com/document/52500558/Metode-Pencarian-Dan-Pelacakan-prolog

http://buatugasai.blogspot.co.id/2013/04/metode-pencarian-dan-pelacakan_4.html