MATERI 3

PENCARIAN
Materi ini membahas tentang bagaimana sebuah pencarian data ataupun pelacakan suatu data dengan berbagai macam metode yang ada.

PENCARIAN DAN PELACAKAN

Hal yang terpenting dalam menentukan keberhasilan sistem ceersas adalah kesuksesan fadalam pencarian.
pengertian pencarian : proses mencari solusi dari suatu permasalahan melalui sekumpilan kemungkinan ruang keadaan.
Untuk mengukur performansi metode pencarian,terdapat empat kriteria yang dapat di gunakan :

• Completeness : apakah metode tersebut menjamin penemuan solusi jika solusi memang da ?
• Time Complexity : berapa lama waktu yang diperluakan
• Space Complexity : berapa banyak memori yang diperlukan
• Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda

Dua Teknik Pencarian & Pelacakan

1. Pencarian Buta (Blind Search)

• Pencarian Melebar pertama (Breadth-First Search)
• Pencarian mendalam pertama (Depth-First Search)

2. Pencarian Terbimbing (Heuristic Search)

• Pendakian Bukit (Hill Climbing)
• Pencarian Terbaik Pertama (Best First Search)

PENCARIAN MELEBAR PERTAMA

• Semua node pada level n akan dikunjungi terlebihy dahulusebelum level n+1
• Mulai dari akar terus ke level 1 dari kiri ke kanan
• Keuntungan : Tidak menemui jalan buntu,Menjamin di temukannya solusi yang paling baik,Jika ada satu solusi maka Bredth-First Search akan menemukannya
• Kelemahan : Membutuhkan memori yang cukup banyak

PENCARIAN MENDALAM PERTAMA

• Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel
• Keuntungan : Memori relatif kecil,Secara kebetulan akan menemukan solusi tanpa harus meguji lebih banyak lagi

PENCARIAN HEURISTIK

• Pencarian buta tidak selalu dapat diterapkan dengan baik
• Metode Heuristic Search diharapkan bisa menyelesaikan permasalahan yang lebih besar
• Mettode Heuristic Search menggunakan suatu fungsi yang menghitung biaya perkiraan dari suatu simpul tertentu menuju ke simpul tujuan

Ada 4 Metode Pencarian Heuristik

• Pembangkit & Pengujian (Generate & Test)
• Pendakian bukit (Hill Climbing)
• Pencarian terbaik pertama (Best First Search)
• Simulated Annealing

Pembangkit & Pengujian (Generate & Test)

• Pada prinsipnya metode ini merupakan penggabungan antara Depth-First Search dengan pelacakan mundur,yaitu bergerak ke belakang menuju pada suatu keadaan awal
• Algoritma :
  

1. Bangkitkan suatu kemungkinan solusi
2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara mebandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang di harapkan
3. Jika soulsi ditemukan ,keluar.Jika tidak ulangi langkah pertama

• Kelemahan : Perlu membangkitkan semua kemungkinan sebelum dilakuka pengujian,Membutuhkan Waktu yang lama dalam pencariannya

Pendakian Bukit (Hill Climbing)

• Metode ini hampir sama dengan metode pembangkitan & pengujian hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristik
• Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan

Simple Hill Climbing

• Algoritma :

1. Mulai dari keadaan awal, lakukan pengetesan,jika merupakan tujuan maka berhenti dan jika tidak, lanjutkan dengan keadaan sekarang sebagai keadaan awal.
2. Kerjakan Llangkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan di aplikasiakan pada keadaan sekarang
3. Cari operator yang belum digunakan sebagai keadann awal
4. Evaluasi keadaan awal tersebut
5. Jika keadaan merupakan tujuan maka keluar
6. Jika bukan keadaan tujuan,namun nilainya lebih baik daripada keadaan sekarang,maka jadikan keadaan baru tersebut menjadi keadaan sekarang.
7. Jika keadaan baru tidak lebih baik daripada keadaan sekarang maka lanjutkan iterasi.
   

Steepest Ascent Hill Climbing

• Steepest Ascent Hill Climbing sebenarnya hampir sama dengan simple hill climbing hanya saja gerakan pencarian tidak dimulai dari posisi paling kiri
  
• Algoritma :

1. Mulai dari keadaan awal lakukan pengujian,jiak merupakan tujuan maka berhenti dan jika tidak,lanjutkan dengan keadaan sekarang sebagai keadaan awal
2. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberikan perubahan pada keadaan sekarang
3. Tentukan SUCC sebagai nilai heuristic terbaik dari success or successor
4. Kerjakan untuk tiap operator yang digunakan oleh keadaan sekarang
   
5. Gunakan operator tersebut dan bentuk keadaan baru
6. Evaluasi keadaan baru tersebut
7. Jika SUCC lebih baik daripada nilai heuristic keadaan sekarang,ubah node SUCC menjadi keadaan sekarang