metode pencarian

metode pencarian

1. Metode Pencarian Buta (Blind Search)

1.1.BFS (Breadth First Search)

Breadth First Search yaitu model pencarian yang memakai metode melebar. Untuk mencari hasilnya, model BFS ini menggunakan teknik pencarian persoalannya dengan cara membuka node (titik) pada tiap levelnya.
contoh :

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.

Contohnya terlihat dibawah ini:

Maka penyelesaiannya adalah:Gambar (a) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1.Gambar (b) BFS(1): 1, 2, 3, 4, 5, 6, 7, 1Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

1.2.DFS (Depth-first Search)

Algoritma DFS (Depth First Search) adalah salah satu algoritma yang digunakan untuk pencarian jalur. Contoh yang dibahas kali ini adalah mengenai pencarian jalur yang melalui semua titik.

Algoritma ini mirip dengan Algoritma BFS (Breadth First Search) yang sudah dijelaskan sebelumnya. Jika Algoritma BFS (Breadth First Search) melakukan perhitungan secara terurut dari urutan pertama sampai urutan terakhir, maka algoritma ini melakukan kebalikannya, yaitu melakukan perhitungan secara terurut dari urutan terakhir. Setelah menghabiskan semua kemungkinan dari titik terakhir, barulah mundur ke titik-titik sebelumnya sampai pada titik pertama.
contoh : 
Di dalam DFS, pencarian dilakukan pada suatu struktur pohon yaitu kumpulan semua kondisi yang mungkin yang diimplementasikan dalam sebuah struktur pohon. Paling atas adalah akar (root) yang berisi kondisi awal pencarian (initial state) dan di bawahnya adalah kondisi-kondisi berikutnya sampai kepada kondisi tujuan (goal state).

Untuk melakukan pencarian, DFS menggunakan cara sebagai berikut :

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.
6. Masukkan seluruh state hasil ekspansi ke dalam tumpukan.
7. Kembali ke langkah 2.

Pada prinsipnya, DFS ini menggunakan tumpukan untuk menyimpan seluruh state yang ditemukan atau bisa dikatakan bahwa DFS menggunakan metode LIFO (Last In First Out).

2. Metode Pencarian Heuristik

2.1 Metode Generate-and-Test

Metode Generate-and-Test adalah metode yang paling sederhana dalam pencarian heuristic. Jika pembangkitan possible solution dikerjakan secara sistematis, maka prosedur akan mencari solusinya, jika ada. Tetapi jika ruang masalahnya sangat luas, mungkin memerlukan waktu yang sangat lama.

Algoritma Generate-and-Test adalah prosedur DFS karena solusi harus dibangkitkan secara lengkap sebelum dilakukan test. Algoritma ini berbentuk sistematis, pencarian sederhana yang mendalam dari ruang permasalahan. Generate & test juga dapat dilakukan dengan pembangkitan solusi secara acak, tetapi tidak ada jaminan solusinya akan ditemukan.
contoh : 

“Travelling Salesman Problem (TSP)” Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setiap kota hanya boleh dikunjungin tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar dibawah ini:

Cara penyelesaian :

2.2 Hill Climbing

Hill Climbing adalah proses pengujian yang dilakukan dengan menggunakan fungsi heuristik. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan

Hill Climbing berbeda Generate-and-Test, yaitu pada feedback dari prosedur test untuk membantu pembangkit menentukan yang langsung dipindahkan dalam ruang pencarian. Dalam prosedur Generate & test , respon fungsi pengujian hanya ya atau tidak. Tapi jika pengujian ditambahkan dengan atauran fungsi-fungsi yang menyediakan estimasi dari bagaimana mendekati state yang diberikan ke state tujuan, prosedur pembangkit dapat mengeksplorasi ini sebagaimana ditunjukkan di bawah. HC sering digunakan jika terdapat fungsi heuristic yang baik untuk mengevaluasi state. Sebagai contoh, anda berada di sebuah kota yang tidak dikenal, tanpa peta dan anda ingin menuju ke pusat kota. Cara sederhana adalah gedung yang tinggi. Fungsi heuristics-nya adalah jarak antara lokasi sekarang dengan gedung yang tinggi dan state yang diperlukan adalah jarak yang terpendek.

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 

sumber :

http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html

https://dimasandree.wordpress.com/2013/10/24/metode-pencarian-heuristic/

http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html
http://web.unair.ac.id/admin/file/f_22572_2_Simple_Hill_Climbing.pdf
https://amandainhere.blogspot.co.id/2016/11/contoh-pencarian-generate-and-test.html
http://cikalinspirasi.blogspot.co.id/2013/05/algoritma-dept-first-search-dfs.html
http://yoursknowladge.blogspot.co.id/2015/04/makalah-algoritma-breadth-first-search.html

http://hanz-kampus.blogspot.co.id/2010/02/heuristic-search-kecerdasan-buatan.html
https://piptools.net/algoritma-dfs-depth-first-search/

first-search/