Definisi dan Contoh dari Metode Pencarian Buta (Blind Search) dan Metode Pencarian Heuristik

1.   Metode Pencarian Buta (Blind Search)

Blind Searching adalah Model Pencarian Buta atau Pencarian yang tidak memiliki informasi awal, model pencarian ini memiliki tiga ciri-ciri utama, yaitu :

    ·   Membangkitkan simpul berdasarkan urutan.

    ·   Kalau ada solusi akan ditemukan.

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

-         Breadth First Search (BFS)

Algoritma Breadth-First Search (BFS) atau dikenal juga dengan nama algoritma pencarian melebar adalah algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpulsimpul yang tadi dikunjungi , demikian seterusnya. Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pad aras d+1. merupakan pencarian yang dilakukan dengan mengunjungi tiap tiap node secara sistematis pada setiap level hingga keadaan tujuan ditemukan. Penelususran yang dilakukan dengan mengunjungi node node pada level yang sama hingga ditemukan tujuan (goal state) nya.

Contoh Kasus dari Breadth First Search (BFS)

Berikut adalah contoh kasus dengan menggunakan metode BFS. Kita akan mencari jalur tujuan dengan menggunakan angkutan umum.Contoh :

Mencari jalur angkutan umum dari terminal senen ke terminal Kp. Rambutan

*Initial State : Senen

* Goal State : Kp. Rambutan

RUTE PERJALANAN

Gambar 1.2 : Rute perjalanan

Penjelasan Gambar :

1. Membangkitakan anak dari terminal Senen = Terminal blok M, Terminal Pulo Gadung, Terminal Manggarai
2. Karena goal state (Terminal Kp. Rambutan) belum tercapai maka kita bangkitkan anak dari terminal senen

Terminal Blok M = Terminal Grogol, Terminal Lebak Bulus            

Terminal Lebak Bulus = Terminal Ciputat, Terminal Kp. Rambutan.            

Terminal Pulo Gadung = Terminal bekasi            

Terminal Manggarai = Terminal Cililitan, Terminal Harmoni

3. Akhirnya tercapai Goal State (Terminal Kp. Rambutan).

    -    Depth First Search (DFS)

Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

Pencarian menggunakan DFS akan berlanjut terus sampai kedalaman paling terakhir dari tree. Permasalahan yang muncul pada DFS adalah ketika proses pencarian tersebut menemui infinite state space. Hal ini bisa diatasi dengan menginisiasikan batas depth pada level tertentu semenjak awal pencarian. Sehingga node pada level depth tersebut akan diperlakukan seolah-olah mereka tidak memiliki successor.

Contoh Penerapan BFS & DFS

Studi Kasus : Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan serigala.Pada saat itu ia baru saja panen sayuran. Karena membutuhkan uang, petani tersebut hendak menjual kambing, serigala, dan sayurannya ke pasar Johar. Untuk sampai di pasar Johar, ia harus menyeberangi sebuah sungai.

Permasalahannya : adalah di sungai itu hanya tersedia satu perahu saja yang bisa memuat petani dan satu penumpang lainnya (kambing, srigala, atau sayuran). Jika ditinggalkan oleh petani tersebut, maka sayuran akan dimakan oleh kambing dan kambing akan dimakan oleh serigala.

Deskripsi

• P = Petani
• Sy = Sayuran
• K = Kambing
• Sg = Serigala

Ruang Keadaan

• Untuk daerah asal dan daerah seberang digambarkan. (P, Sy, K, Sg)

Keadaan Awal

• Daerah Asal = (P, Sy, K, Sg)
• Daerah seberang = (0, 0, 0, 0)

Tujuan

• Daerah Asal = (0, 0, 0, 0)
• Daerah seberang = (P, Sy, K, Sg)

    2.   Metode Pencarian Heuristic 

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 pencairan, namun dengan kemungkinan mengorbankan kelengkapan (completeness).

    -    GENERATE and TEST (Pembangkitan dan Pengujian)

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 dari Generate and Test : “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 :

Gambar 1

  

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

    -     HILL CLIMBING (Pendakian Bukit)

• 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:

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

a) 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.

b) 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 dari Hill Climbing: 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.

Gambar 1

Sumber :

http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html

http://azizmusyaffaa.blogspot.co.id/2016/10/breadth-first-search-depth-first-search.html

http://yoursknowladge.blogspot.co.id/2015/04/makalah-algoritma-breadth-first-search.html

https://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html