Metode Pencarian (I)

Metode Pencarian

(Bagian I)

Pencarian dapat diartikan sebagai sebush proses pelacakan yang merupakan teknik untuk pencarian. Didalam pencarian ada dua kemungkinan hasil yang didapat yaitu menemukan dan tidak menemukan. Sehingga pencarian merupakan teknik yang penting dalam AI (Artificial Inteligen). Hal penting dalam menentukan keberhasilan sebuah sistem berdasarkan kecerdasan adalah kesuksesan dalam pencarian dan pencocokan. Pencarian adalah suatu proses mencari solusi dari suatu permasalahan agar dapat mendapat solusi melalui sekumpulan pencarian yang sudah diperoleh dengan semua kemungkinan keadaan. Untuk mengukur performansi metode pencarian, terdapat empat kriteria yang dapat digunakan:

·         Completeness (Kelengkapan)

·         Time compexity (Kekompleksan waktu)

·         Space complexity (Kekompleksan ruang)

·         Optimality (Optimal)

Ada beberapa teknik pelacakan :

·         Blind Search

Blind Search disebut sebagai model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:
-          Membangkitkan simpul berdasarkan urutan
-          Jika ada solusi maka solusi akan ditemukan
-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui).

Ada beberapa metode yang tersedia di dalam Blind Search diantaranya:

1.      Breadth First Search

Breadth First Search yaitu model pencarian melebar pertama atau juga merupakan  model pencarian yang memakai metode melebar. Untuk dapat mencari hasilnya, model Breadth First Serach ini menggunakan teknik pencarian persoalan dengan cara membuka node (titik) pada tiap levelnya.

Sebagai Contoh:

Jadi, untuk pohon biner :

Maka, urutan penelusurannya adalah : a – b – c – d – e – f – g – h – i – j – k – l

Salah satu cara implementasi BFS adalah dengan bantuan struktur data queue. Sama seperti stack pada DFS, queue yang digunakan adalah queue yang isi elemennya adalah simpul pohon / tree.  Berikut ini adalah urutan algoritmanya :

o   Memasukkan simpul root ke dalam antrian.

o   Memeriksa antrian terdepan apakah memiliki anak simpul.

o   Jika ya, masukan semua anak simpul ke dalam antrian.

o   Menghapus antrian terdepan.

o   Jika antrian kosong berhenti, tapi jika tidak kembali ke langkah dua.

Untuk gambar pohon biner di atas, urutan langkah dan kondisi queue pada setiap iterasinya adalah sebagai berikut :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kiri terlebih dahulu ke dalam queue. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu B dulu, baru C ke dalam stack. Untuk penelusurannya yang dilihat adalah bagian yang berwarna biru, yaitu antrian terdepan yang setiap iterasinya memiliki urutan a – b – c – d – e – f – g – h – i – j – k – l. Sama seperti DFS lagi pada iterasi ke 13 itu kondisi antrian sudah kosong.

2.      Depth First Search

Depth-first Search disebut juga pencarian mendalam pertama. Sesuai dengan namanya “pencarian mendalam”, Depth First Search tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemukan targetnya maka akan dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target. Pada DFS memori yang digunakan tidak terlalu banyak karena tidak membuka semua node.

Sebagai Contoh:

Jadi, jika ada pohon biner seperti gambar di bawah ini :

Maka, urutan penelusurannya adalah : a – b – d – h – e – i – c – f – g – j – k – l

Dalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Berikut ini adalah urutan algoritmanya :

o   Memasukkan simpul root ke dalam tumpukan dengan push.

o   Mengambil dan menyimpan isi elemen (berupa simpul pohon) dari tumpukan teratas.

o   Menghapus isi stack teratas dengan prosedur pop.

o   Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul.

o   Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack.

o   Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua.

Jadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan a – b – d – h – e – i – c – f – g – j – k – l. Pada iterasi ke 13 kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.

Sumber:

http://www.ziddu.com/download/23183192/MetodePencariandanPelacakan.docx.html

Pengantar Inteligensia Buatan – Heuristic Searching