METODE BLIND SEARCH & HEURISTIK

Desember 08, 2017

METODE BLIND SEARCH & HEURISTIK

METODE PENCARIAN BUTA (BLIND SEARCH)

Blind Search merupakan pencarian asal. Jika solusi sudah ditemukan, maka pencarian akan dihentikan. Jika dibuat skemanya, pencarian buta hanya mengenal 3 bagian yaitu [masalah]-[pencarian]-[solusi]. Blind search tidak mempunyai atribut atau informasi tambahan. Misalkan dalam kotak ada 3 kelereng warna merah, 3 biru, dan 3 kuning. Masalahnya adalah, ambillah satu kelereng yang berwarna merah. Solusi, setelah melakukan pencarian, kemudian didapat satu kelereng warna merah, nah, itulah solusinya. ciri2 Blind Search

Membangkitkan simpul berdasarkan urutan

Kalau ada solusi, solusi akan ditemukan

hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

A. Breadth First Search

Definisi

Breadth First Search merupakan salah satu dari metode pencarian buta. Mengapa dikatakan pencarian buta ? istilah buta disini lebih dikenal dengan nama blind. Dikatakan buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

Breadth First Search (BFS) juga memiliki alur algoritma yang paling sederhana dibandingkan dengan metode blind yang lain. Itulah alasan mengapa BFS selalu dipelajari lebih dulu ketika membahas masalah pencarian buta.

Sebelum menelaah lebih jauh bagaimana metode BFS dijalankan, kita telisik dulu mengapa metode ini dinamakan pencarian Breadth First. Breadth dapat diartikan dengan luas / lebar, sedangkan first adalah pertama. Jadi, Breadth First adalah lebar pertama, apa maksudnya? Penamaan metode ini disesuaikan dengan konsep algoritma secara garis besar yaitu melakukan proses pencarian pada semua node yang berada pada level atau hirarki yang sama terlebih dahulu sebelum melanjutkan proses pencarian pada node di level berikutnya.

BFS akan mencari satu per satu node secara melebar dari kiri ke kanan secara berurutan berdasarkan tingkat level nodenya. Jika pada satu level belum ditemukan solusi yang diinginkan, maka pencarian dilanjutkan hingga level berikutnya. Demikian seterusnya hingga ditemukan solusi. Maka, dengan cara seperti ini, BFS menjamin ditemukannya solusi apabila solusinya memang ada.

Contoh

Seperti pada gambar, jika dicari bagaimana jalur dari kota a menuju kota k, maka sistem akan menjelajahi setiap node hingga menemui titik kota k, sehingga hasil pencarian jalur terpendeknya adalah : a - b - c - d - e - f - g - h - i - j - k . Contoh lain seperti gambar dibawah ini :

Gambar a : Tentukan jalur terpendek dari simpul 1 hingga kembali ke simpul 1 lagi. !.

Gambar b :Tentukan rute dari node 1 hingga node 7 !.

Gambar c : Tentukan lintasan terpendek dari kota 1 ke kota 8 !.

Maka, solusi yang ditemukan adalah :

Gambar a : 1 - 2 - 3 - 4 - 5 - 6 - 7 – 1

Gambar b : 1 - 2 - 3 - 4 - 5 - 6 – 7

Gambar c : 1 - 2 - 3 - 4 - 5 - 6 - 7 - 8

Dalam implementasinya pada program, maka setiap node yang telah dikunjungi harus dimasukkan dalam sebuah queue (antrian) sebagai tempat menampung urutan node tahap demi tahap. untuk memperjelas bagaimana alur algoritmanya, berikut langkah-langkahnya :

Masukkan node akar (root) ke dalam queue

Ambil node dari awal antrian, lalu cek apakah node tersebut merupakan solusi

Jika node merupakan solusi, pencarian selesai dan hasil dikembalikan.

Jika node bukan solusi, masukkan node yang bertetangga dengan node tersebut (node anak) ke dalam queue

Jika queue kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

Ulangi pencarian dari langkah kedua.

Keuntungannya :

· Tidak akan menemui jalan buntu, menjamin ditemukannya solusi (jika solusinya memang ada) dan solusi yang ditemukan pasti solusi yang paling baik.

· Jika ada 1 solusi, maka breadth – first search akan menemukannya.

· Jika ada lebih dari 1 solusi, maka solusi minimum akan ditemukan

Kerugiannya :

· Membutuhkan memori yang banyak, karena harus menyimpan semua simpul yang pernah dibangkitkan dan hal ini harus dilakukan agar BFS dapat melakukan penelusuran simpul-simpul sampai di level bawah.

· Membutuhkan waktu yang cukup lama

Kesimpulan :

Teknik pencarian Breadth – First Search ini :

Completeness : dimana teknik yang digunakan adanya solusi

Optimality : dimana teknik yang digunakan menemukan solusi yang terbaik saat adanya beberapa solusi berbeda

Time complexity : waktu yang dibutuhkan cukup lama

Space complexity : memori yang dibutuhkan juga banyak.

B. Depth First Search

Definisi

Pada algoritma DFS, pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam solusi belum ditemukan, maka pencarian dilanjutkan pada node sebelah kanan. Node yang di kiri dapat dihapus dari memori. Jika pada level yang paling dalam belum ditemukan solusi, maka pencarian dilanjutkan ke level sebelumnya. Demikian seterusnya sampai ditemukannya solusi. Jika solusi ditemukan, maka tidak diperlukan proses backtracking (penelusuran untuk mendapatkan jalur yang diinginkan). Beberapa kelebihan dari algoritma DFS adalah pemakaian memori hanya sedikit karena hanya menyimpan lintasan yang aktif saja. Selain itu kelebihannya adalah jika solusi berada pada level yang paling dalam dan paling kiri, maka DFS akan menemukannya secara cepat. Misal suatu ruang keadaan masalah ditunjukkan dengan suatu seperti gambar berikut ini.

Contoh

Dalam pencarian menggunakan algoritma DFS, simpul-simpul yang paling dalam pada tree yang akan di cari paling awal. Sebagai contoh pada Gambar di atas. Urutan pencarian keadaan awal (S) sampai keadaan tujuan (G) adalah dimulai dari node S, kemudian ke node A, kemudian ke node B, kemudian ke node C, setelah itu akan melewati node B kembali dan menuju ke node E, selanjutnya akan menuju node D, setelah itu akan menuju node F setelah melewati node E, dan yang terakhir akan menuju node G.

Keuntungannnya :

Membutuhkan memori relatif kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.

Dan secara kebetulan, akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan, jadi jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya dengan cepat (waktunya cepat)

Kerugiannya :

Memungkinkan tidak ditemukannya atau tidak adanya tujuan yang diharapkan, karena jika pohon yang dibangkitkan mempunyai level yang sangat dalam (tak terhingga) à tidak complete karena tidak ada jaminan akan menemukan solusi.

Hanya mendapat 1 solusi pada setiap pencarian, karena jika terdapat lebih dari satu solusi yang sama tetapi berada pada level yang berbeda, maka DFS tidak menjamin untuk menemukan solusi yang paling baik à tidak optimal.

METODE PENCARIAN HEURISTIK

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaankeadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan. Jenis-jenis Heuristic Searching:

1. Generate and Test.

2. HillClimbing.

3. Best First Search.

4. Alpha Beta Prunning,Means-End-Anlysis,Constraint Satisfaction, Simulated Anealing, dll

· PEMBANGKITAN dan PENGUJIAN (Generate and Test)

· Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

· Algoritma :

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).

2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

Contoh : “Travelling Salesman Problem (TSP)” 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 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :

Alur pencarian dengan Generate and Test

Pencarian ke-	Lintasan	Panjang Lintasan	Lintasan terpilih	Panjang Lintasan terpilih
1	ABCD	19	ABCD	19
2	ABDC	18	ABDC	18
3	ACBD	12	ACBD	12
4	ACDB	13	ACBD	12
5	ADBC	16	ACBD	12
Dst…..

· PENDAKIAN BUKIT (Hill Climbing)

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnyayang mungkin.

· Algoritma:

Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

· Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang : Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

· Evaluasi keadaan baru tersebut : – Jika keadaan baru merupakan tujuan, keluar – Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang. – Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Contoh: TSP dengan Simple Hill Climbing 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 lintasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak n!/2!(n-2)! atau sebanyak 6 kombinasi. Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi.