TEKNIKPENCARIAN/PENELUSURAN (SEARCHING)
· Pada umumnya manusia mempertimbangkan sejumlah alternatif strategi dalam menyelesaikan suatu problema.
· Dalam permainan catur misalnya, seorang pemain mempertimbangkan sejumlah kemungkinan tentang langkah-langkah berikutnya, memilih yang terbaik menurut kriteria tertentu seperti kemungkinan respon lawannya.
· Aspek tingkahlaku cerdas yang mendasari teknik penyelesaian problema seperti dalam permainan catur tersebut dinamakan proses pencarian ruang keadaan (space state search).
· Exhaustive search – adalah proses pencarian terhadap seluruh ruang keadaan serangakaian langkah yang paling dimungkinkan untuk menghasilkan kemenangan.
· Walaupun metode ini dapat diterapkan pada setiap ruang keadaan, namum ukuran ruang keadaan yang sangat besar membuat pendekatan ini secara praktis tidak dimungkinkan (dalam permainan catur terdapat 10120 keadaan )
· Bila kasus ini diimplementasikan ke dalam sisten komputer, maka akan membutuhkan memori yang sangat besar, dan waktu pencarian yang sangat lama. Dengan kata lain metodeexhaustive search ini tidak efisien dan tidak efektif, sehingga tidak praktis untuk diimplementasikan.
· Untuk mengatasi kendala tersebut di atas, ada beberapa cara yang dapat dilakukan, diantaranya: pertama teknik pencarian parsial (Blind Search) dan yang kedua teknik pencarian heuristic (Heuristik Search).
Pencarian Parsial (Blind Search)
A. PENCARIAN MELEBAR PERTAMA
(Breadth-First Search)
· Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu sebelum mengunjungi node-node pada level n+1.
· Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke level berikutnya, demikian pula dari kiri kekanan hingga ditemukannya solusi (lihat gambar di bawah ini).
Prosedur breadth_first_search
Inisialisasi : open = [start]; closed [ ]
While open = [ ] do
Begin
Hapuskan keadaan paling kiri dari keadaan open,
sebutlah keadaan itu dengan X;
Jika X merupakan tujuan then return (sukses);
Buatlah semua child dari X;
Ambillah X dan masukkan pada closed;
Eliminasilah setiap child X yang telah berada pada
open atau closed, yang akan menyebabkan loop
dalam search;
Ambillah turunan di ujung kanan open sesuai urutan
penemuan-nya;
End;
· Keuntungan :
Ø Tidak akan menemui jalan buntu
Ø Jika ada satu solusi, maka breadth-first search akan menemukannya. Dan, jika ada lebih dari satu solusi, maka solusi minimum akan ditemukan.
· Kelemahan :
Ø Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam satu pohon
Ø Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level yang ke-(n+1).
B. PENCARIAN KEDALAM PERTAMA
(Depth-First Search)
· Pada Depth-First Search, proses pencarian akan dilakukanpada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian dimulai dari node akar ke level yang lebih tinggi. Proses ini diulangi terus hingga ditemukannya solusi (lihat gambar di bawah).
sprosedur depth_first_search
inisialisasi: open = [Start]; closed = []
while open x [] do
begin
hapuskan keadaan berikutnya dari sebelah kiri open, sebutlah keadaan itu dengan X;
jika X merupakan tujuan then return(sukses);
buatlah semua child yang dimungkinkan dari X;
ambilah X dan masukkan pada closed;
eliminasilah setiap child X yang telah berada pada
open atau closed, yang akan menyebabkan loop
dalam search;
ambilah child X yang tersisa di ujung kanan open
sesuai urutan penemuannya;
end.
· Keuntungan :
Ø Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja yang disimpan.
Ø Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.
· Kelemahan :
Ø Memungkinkan tidak ditemukannya tujuan yang diharapakan
Ø Hanya akan menemukan 1 solusi pada setiap pencarian
Contoh penerapan nya :
Implementasi Breadth First Search pada Java
untuk mengimplementasikan java pada BFS, saya menukil kodingannya Mark Watson dalam buku beliau Programming AI with Java. Beliau memberikan dua contoh penerapan BFS untuk pencarian jalur terpendek.
1. Pencarian jalur terpendek pada game Maze
2. Pencarian jalur terpendek pada simpul Graph
Pencarian Jalur terpendek pada game Maze
Game maze adalah game yang mengharuskan user untuk menemukan jalan keluar dan melewati banyak halangan (obstacle) dari sebuah ruang yang mirip labirin. Titik awalnya dimulai dari huruf S (Start) dan diakhiri pada kotak bertuliskan G (Goal). Ketika program dijalankan, sistem akan otomatis mencari rute terpendek dari kotak S menuju kotak G menggunakan metode BFS. Panjang rute hasil pencarian dituliskan dalam bentuk angka disetiap kotak.
Pencarian Jalur Terpendek pada Graph
Titik awal adalah simpul 0 dan titik akhir adalah simpul 9, program secara otomatis akan mencari jalur terpendek dari simpul 0 menuju simpul 9 menggunakan metode BFS.
- STUDI KASUS :
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
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 :
Terdapat dua metode penyelesaian yang akan dibahas pada postingan kali ini. Metode pertama adalah metode breadth first search (BFS), dan metode kedua adalah metode Depth First Search (DFS). Berikut ini akan dijelaskan penyelesaian studi kasus diatas dengan kedua metode tersebut.
- BFS (Breadth First Search)
adalah sebuah algoritma pencarian solusi yang digambarkan dengan struktur pohon. Dimana penyelesaiannya dilakukan dimulai dari simpul akar kemudian melebar sesuai dengan tingkatan yang ada di dalam pohon. Berikut ini adalah algoritma BFS :
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi (goal node), maka stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian, bangkitkan semua anak-anaknya. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di belakang antrian.
4. Jika suatu simpul anak dari v adalah simpul solusi, maka solusi telah ditemukan, kalau tidak kembali lagi ke langkah 2.
adalah sebuah algoritma pencarian yang digambarkan dengan struktur pohon seperti pada BFS. Penyelesaiannya dilakukan dengan mendalam. Pencarian solusi dilakukan secara menurun sesuai urutan yang ditentukan.
1. Masukkan simpul akar ke dalam antrian Q. Jika simpul akar = simpul solusi, maka stop.
2. Jika Q kosong, tidak ada solusi. Stop.
3. Ambil simpul v dari kepala (head) antrian. Jika kedalaman simpul v sama dengan batas kedalaman maksimum, kembali ke langkah 2
4. .Bangkitkan semua anak dari simpul v. Jika v tidak mempunyai anak lagi, kembali ke langkah 2. Tempatkan semua anak dari v di awal antrian Q. Jika anak dari simpul v adalah simpul tujuan, berarti solusi telah ditemukan, kalau tidak, kembali lagi ke langkah 2.
Sumber :
https://creactiveit.wordpress.com/2015/05/08/halo-dunia/
http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
karmila.staff.gunadarma.ac.id/Downloads/folder/0.0
