Definisi Contoh Blind Search & Heuristic Search

1. Metode Pencarian Buta

• Breadth Search First (BFS) 

Breadth First Search adalah suatu metode yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya. Jika graf berbentuk pohon graf berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul-simpul pada aras d+1.

Berikut ini adalah algoritma BFS

1. Masukkan simpul ujung (akar) ke dalam antrian.
2. Ambil simpul dari awal antrian, lalu cek apakah simpul merupakan solusi.
3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.
4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam antrian.
5. Jika antrian kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan.
6. Ulangi pencarian dari langkah kedua.

• Depth Search First (DFS) 

Algoritma Depth First Search (DFS) adalah suatu metode pencarian pada sebuah pohon dengan menelusuri satu cabang sebuah pohon sampai menemukan solusi. Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri dan dilanjutkan pada node sebelah kanan. Jika solusi ditemukan maka tidak diperlukan proses backtracking yaitu penelusuran balik untuk mendapatkan jalur yang diinginkan. Pada metode DFS pemakaian memori tidak banyak karena hanya node-node pada lintasan yang akktif saja yang disimpan. Selain itu, jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat.

Berikut ini adalah algoritma DFS :

1. Masukkan Initial State pada Tumpukan.
2. Periksa apakah ada data di tumpukan.
3. Jika tidak, maka solusi tidak ditemukan, dan proses berhenti.
4. Jika ya, Ambil state pada tumpukan paling atas.
5. Bandingkan State tersebut apakah sama dengan Goal State
6. Jika sama, maka solusi ditemukan dan proses berakhir.
7. Jika tidak, ekspansikan state tersebut.
8. Masukkan seluruh state hasil ekspansi ke dalam tumpukan.
9. Kembali ke langkah 2.

• CONTOH

➝Pada suatu hari ada seorang petani yang mempunyai seekor kambing dan srigala.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)

Metode Penyelesaian dengan BFS (Breadth First Search)

Metode Penyelesaian Dengan DFS (Depth First Search)

2. Metode Pencarian Heuristik

• Generate and Test 

Metode Generate and Test adalah sebuah metode dari beberapa konsep pencarian heuristik. Menurut Kusumadewi (2003), pada prinsipnya metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking) yaitu bergerak ke belakang menuju pada suatu keadaan awal. Nilai pengujian berupa jawaban ‘ya’ atau ‘tidak’. 

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.

• Definisi Metode Hill Climbing

Metode Hill Climbing adalah salah satu metode yang di gunakan dalam menyelesaikan permasalahan pencarian jarak terdekat (Rich et al.,1991 dalam Russel dan Norvig, 2003). Cara kerjanya adalah menentukan langkah berikutnya dengan menempatkan node yang akan muncul sedekat mungkin dengan sasarannya. Proses Pengujian dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristik ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan keadaan lainnya yang mungkin (Kusumadewi, 2003).

Algoritma:
(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) Mengerjakan langkah berikut sampai solusi ditemukan atau sampai tidak ada lagi operator baru yang dapat digunakan dalam state sekarang:
a. Mencari sebuah operator yang belum pernah digunakan dalam state sekarang dan gunakan operator tersebut untuk membentuk state baru.
b.  Evaluasi state baru. 
➝i. Jika state baru adalah tujuan, maka proses berhenti.
➝ii. 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 2. 

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

Metode Penyelesaian Dengan Generate and Test

Metode Penyelesaian Dengan Hill Climbing
Ruang keadaan berisi semua kemungkinan lintasan, sementara operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan adalah panjang lintasan yang terjadi. Operator yang akan digunakan adalah menukar urutan posisi 2 kota dalam 1 lintasan.  Bila ada n kota, dan ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka banyak lintasan yang mungkin di nyatakan dalam perumusan:  

n!/2!(n-2)!
Misalkan dalam tersebut di terapkan pada 4 kota, sehingga dapat di peroleh:
4!/2!(4-2) = 6 kombinasi.
Keenam kombinasi ini akan kita pakai semuanya sebagai operator, yaitu:
1. Tukar1,2 (menukar urutan posisi kota ke-1 dengan kota ke-2).
2. Tukar2,3 (menukar urutan posisi kota ke-2 dengan kota ke-3).
3. Tukar3,4 (menukar urutan posisi kota ke-3 dengan kota ke-4).
4. Tukar4,1 (menukar urutan posisi kota ke-4 dengan kota ke-1).
5. Tukar2,4 (menukar urutan posisi kota ke-2 dengan kota ke-4).
6. Tukar1,3 (menukar urutan posisi kota ke-1 dengan kota ke-3).

Sumber :

Rinaldi Munir. 2005. BFS dan DFS. Bandung: Institut Teknologi Bandung.

Kusumadewi, S., 2003. Artificial Intelligence (Teknik &  Aplikasinya).  Yogyakarta: Graha Ilmu.
http://yoursknowladge.blogspot.co.id/2015/04/makalah-algoritma-breadth-first-search.html
http://cikalinspirasi.blogspot.co.id/2013/05/algoritma-dept-first-search-dfs.html

https://creactiveit.wordpress.com/2015/05/08/halo-dunia/
https://ejournal.undip.ac.id/index.php/jsinbis/article/view/9890/pdf

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