Metode Pencarian dan Macamnya

2. Pencarian Mendalam Pertama (Depth – First Search)

Pencarian ini dilakukan pada suatu simpul dalam setiap level dari yang paling kiri.

Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi. Alur depth – first search dapat dilihat pada gambar 2.

Pencarian mendalam-pertama mulai dari A, dengan asumsi bahwa tepi kiri dalam grafik ditunjukkan dipilih sebelum tepi kanan, dan dengan asumsi pencarian sebelumnya-ingat node dikunjungi dan tidak akan mengulangi mereka (karena ini

adalah grafik kecil), akan mengunjungi node dalam urutan sebagai berikut: A, B, D, F, E, C, G.

Melakukan pencarian yang sama tanpa mengingat hasil sebelumnya mengunjungi node dalam mengunjungi node dalam urutan A,B, D, F, E, A, B, D, F

, E, dll selamanya, terperangkap dalam A, B, D, F , E siklus dan tidak pernah mencapai C atau G.

Iteratif memperdalam mencegah loop ini dan akan mencapai node berikut pada kedalaman berikut, dengan asumsi itu hasil dari kiri-ke-kanan seperti di atas:

0: A

1: A (diulang), B, C, E

(Perhatikan bahwa iterasi memperdalam sekarang melihat C, ketika sebuah pencarian depth-first konvensional tidak.)

2: A B,, D, F, C, G, E, F

(Perhatikan bahwa masih melihat C, tetapi itu datang belakangan juga diketahui bahwa melihat E melalui jalan yang berbeda, dan loop kembali ke F dua kali..)

3: A B,, D, F, E, C, G, E, F, B

Untuk grafik ini, kedalaman lebih yang ditambahkan, dua siklus "ABFE" dan "AEFB" hanya akan mendapatkan lagi sebelum algoritma menyerah dan mencoba cabang lain.

Pencarian Terbimbing (Heuristic Search)

Pencarian terbimbing yakni metode pencarian dimana ada informasi awal yang digunakan dalam proses pencarian. Pencarian terbimbing menggunakan fungsi heuristic (fungsi yang menghitung biaya perkiraan/ estimasi dari suatu simpul tertentu  menuju ke simpul tujuan). Aplikasi yang menggunakan fungsi heuristic adalah Google, Deep Blue Chess Machine. Ada 2 macam pencarian terbimbing, yaitu pendakian bukit (hill climbing) dan pencarian terbaik pertama (best first search).

1. Pendakian Bukit (Hill Climbing)

Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search. Ada 2 jenis Hill climbing, yakni simple hill climbing (hill climbing sederhana) dan steepest-ascent hill climbing (hill climbing dengan memilih kemiringan yang paling tajam / curam).

Simple Hill Climbing

Algoritma dari simple hill climbing adalah :

1. Evaluasi state awal, jika state awal sama dengan tujuan, maka proses berhenti. Jika tidak sama dengan tujuan maka lanjutkan proses dengan membuat state awal sebagai state sekarang. 

2. Kerjakan langkah berikut sampai solusi ditemukan atau sampai tidak ada lagi operator baru yang dapat digunakan dalam state sekarang: 

i. Cari sebuah operator yang belum pernah digunakan dalam state sekarang dan gunakan operator tersebut untuk membentuk state baru. 

ii. Evaluasi state baru. 

• Jika state baru adalah tujuan, maka proses berhenti 

• Jika state baru tersebut bukan tujuan tetapi state baru lebih baik daripada state sekarang, maka buat state baru menjadi state sekarang. 

iii. Jika state baru tidak lebih baik daripada state sekarang, maka lanjutkan ke langkah sebelumnya.

Contoh :

Kasus Traveling Salesman Problem(TSP)

Steepest-Ascent Hill Climbing

Algoritma dari steepest-ascent hill climbing adalah :

1. Evaluasi keadaan awal (initial state). Jika keadaan awal sama dengan tujuan (goal state) maka kembali pada initial state dan berhenti berproses. Jika tidak maka initial state tersebut jadikan sebagai current state. 

2. Mulai dengan current state = initial state. 

3. Dapatkan semua pewaris (successor) yang dapat dijadikan next state pada current statenya dan evaluasi successor tersebut dengan fungsi evaluasi dan beri nilai pada setiap successor tersebut. 

4. Jika salah satu dari  successor tersebut mempunyai nilai yang lebih baik dari current state maka jadikan successor dengan nilai yang paling baik tersebut sebagai new current state. 

5. Lakukan operasi ini terus menerus hingga tercapai current state = goal state atau tidak ada perubahan pada current statenya.

Contoh :
Diketahui keadaan awal dan tujuan dari suatu permainan kotak 8 puzzle, sebagai berikut :



Contoh :
Disini ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Apabila ada n kota, dan kita ingin mencari kombinasi l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak:



atau sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi



Pembangkitan dan pengujian (Generate and Test)
Teknik ini merupakan gabungan dari DFS dan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Dimana nilai pengujian berupa jawaban “ya” atau “tidak”.
Algoritmanya :
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
- Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan
- Jika solusi ditemukan, keluar dan jika tidak, ulangi lagi langkah pertama
Salah satu kelemahan teknik Generate and Test adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar dalam pencariannya.

Contoh:
Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat 1 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini:



Penyelesaian dengan Generate and Test




Sumber :
https://www.scribd.com/document/360433628/Metode-Pencarian
http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html