Dua teknik pencarian dan pelacakan (Blind Search & Heuristic Search)

PENGANTAR TEKONOLOGI SISTEM CERDAS

BLIND SEARCH & HEURISTIC SEARCH

RIZKI APRILIA DWIJAYANTI

16115138 

3KA23

UNIVERSITAS GUNADARMA

FAKULTAS ILMU KOMPUTER DAN TEKNOLOGI INFORMASI 

2017

Dua teknik pencarian dan pelacakan 

1.    Pencarian buta (blind search) : tidak ada informasi awalyang digunakan dalam proses pencarian, simpul pencarian dibangkitkan berdasarkan urutan tertentu
Contoh blind search : 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.

Pencarian blind search di bagi menjadi 2 yaitu :

•    Pencarian melebar pertama (Breadth– First Search)
•    Pencarian mendalam pertama (Depth– First Search)

2.    Pencarian terbimbing (heuristic search) : adanya informasi awal yang digunakan dalam proses pencarian. 
Contoh aplikasi yang menggunakan fungsi heuristic : Google, Deep Blue Chess Machine.
•    Pendakian Bukit ( Hill Climbing)
•    Pencarian Terbaik Pertama (Best First Search)
 
A. Pencarian meluas pertama (Breadth - First Seacrh)

Pada 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 1 dari kiri ke kanan, kemudian berpindah ke level berikutnya dari kiri ke kanan hingga solusi ditemukan.

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.


Contoh Breadth - First Search : 

Contoh kakas pencarian yang menggunakan metode Breadth - First Search adalah WebCrawler.
WebCrawler adalah suatu kakas yang membuat indeks isi dari suatu dokumen di Web yang selanjutnya akan dimanfaatkan oleh mesin pencari. Terdapat tiga langkah yang dilakukan oleh WebCrawler ini ketika mengunjungi dokumen, yaitu menandai bahwa suatu dokumen telah dikunjungi, mengenali link yang terdapat pada dokumen tersebut, kemudian isinya didaftarkan pada daftar indeks. Pada akhirnya, WebCrawler akan menampilkan file yang paling banyak berkaitan dengan kata kunci.

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 Breadth First Search.

 

B. Pencarian mendalam pertama (Depth – First Search)

Pada pencarian Depth – First Search dilakukan pada suatu simpul dalam setiap level dari yang paling kiri. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada simpul sebelah kanan dan simpul yang kiri dapat dihapus dari memori. Jika pada level yang paling dalam tidak ditemukan solusi, maka pencarian dilanjutkan pada level sebelumnya. Demikian seterusnya sampai ditemukan solusi.

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

Contoh Depth - First Search :

Pencarian buta (blind search) tidak selalu dapat diterapkan dengan baik, disebabkan karena waktu aksesnya yang cukup lama & besarnya memori yang diperlukan. Untuk masalah dengan ruang masalah yang besar, teknik pencarian buta (blind search) bukan teknik yang baik untuk digunakan karena keterbatasan kecepatan komputer dan memori.

Dengan adanya teknik heuristic search diharapkan bisa menyelesaikan permasalahan yang lebih besar. Fungsi dari teknik heuristic search menggunakan suatu fungsi yang menghitung biaya perkiraan (estimasi) dari suatu simpul tertentu menuju ke simpul tujuan.

Ada empat jenis pencarian terbimbing (heuristic search) :

A.  Pembangkitan dan pengujian (Generate and Test) 

Teknik ini merupakan gabungan dari DFS dan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal. Dimana nilai pengujian berupa jawaban “ya” atau “tidak”. 

•    Algoritmanya : Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
•    Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan
•    Jika solusi ditemukan, keluar dan jika tidak, ulangi lagi langkah pertama
•    Salah satu kelemahan teknik Generate and Test adalah perlu membangkitkan semua kemungkinan sebelum dilakukan pengujian, sehingga membutuhkan waktu yang cukup besar dalam pencariannya.
 
Contoh Generated and Test 
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 di kunjungi tepat 1 kali. misalkan ada 4 kota dengan jarak antara tiap tiap kota seperti berikut ini :

 Alur pencarian dengan Generate and Test

B.    Pendakian Bukit (Hill Climbing)

 
Hampir sama dengan teknik Generate and Test dimana roses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya sangat tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baik nilai terkaan yang diambil terhadap kesalahan-kesalahan lainnya yang mungkin. Teknik-teknik pada Hill Climbing :
a)    Teknik simple hill climbing, Algoritma akan berhenti kalau mencapai nilai optimum lokal. Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi. Tidak diijinkan untuk melihat satupun langkah selanjutnya.
b)    Teknik steepest – ascent hill climbing, Hampir sama dengan simple hill climbing, hanya saja gerakan pencarian tidak dimulai dari paling kiri. Gerakan selanjutnya dicari berdasarkan nilai heuristic terbaik.
 
Contoh Hill Climbing :
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-20)! atau sebanyak 6 kombinasi. fungsi heuristic yang di gunakan adalah panjang lintasan yang terjadi.

 
C.    Pencarian terbaik pertama (Best First Search)
 
Teknik Best First Search merupakan kombinasi dari teknik depth first search dan breadth first search dengan mengambil kelebihan dari kedua teknik tersebut. Hill climbing tidak diperbolehkan untuk kembali ke node pada lebih rendah meskipun node tersebut memiliki nilai heuristic lebih baik. Pada best first search, pencarian diperbolehkan mengunjungi node di lebih rendah, jika ternyata node di level lebih tinggi memiliki nilai heuristic lebih buruk. Untuk mengimplementasikan teknik ini, dibutuhkan 2 antrian yang berisi node-node, yaitu :
•    OPEN : berisi node-node yang sudah dibangkitkan, sudah memiliki fungsi heuristic namun belum diuji. Umumnya berupa antrian berprioritas yang berisi elemen-elemen dengan nilai heuristic tertinggi
•    CLOSED : berisi node-node yang sudah diuji

D.    Branch and Bound Search
 
Membentuk antrian satu-elemen, sampai jalur pertama adalah antrian berakhir pada node tujuan atau antrian kosong, Hapus jalur pertama dari antrian, kemudian membuat jalur baru dengan memperpanjang jalan pertama untuk semua dari node terminal, Menolak semua path baru dengan loop, Jika ada tambahkan jalur baru yang tersisa ke antrian, Urutkan seluruh antrian dengan panjang lintasan yang paling dekat di depan, Jika node tujuan ditemukan, berarti berhasil, jika tidak ditemukan berarti gagal

E.    A* Search
 
A* Search merupakan gabungan antara best-first search dan branch and bound search. Misalkan kita memberikan estimasi setiap node terhadap solusi yang diinginkan. Maka proses searching untuk mencari jarak terpendek dilakukan dengan melakukan komputasi terhadap total estimasi.

Sumber :
http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html
https://www.scribd.com/doc/116048931/Metode-Pencarian-Buta

jurnal.stmik-aub.ac.id/index.php/goinfotech/article/view/38/34
https://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html