BLIND SEARCH

METODE PENCARIAN

Metode pencarian berhubungan dengan AI (Artificial Intelligence) yang merupakan salah satu metode pencarian masalah dengan penyelesaian berupa pencarian solusi pada suatu permasalahan yang dihadapi.

Untuk mengukur perfomansi metode pencarian, terdapat 4 kriteria yang dapat digunakan :

1.      Completeness : apakah metode tersebut menjamin penemuan solusi jika solusinya memang ada?

2.      Time complexity : berapa lama waktu yang diperlukan? [semakin cepat, semakin baik]

3.      Space complexity : berapa banyak memori yang diperlukan

4.      Optimality : apakah metode tersebut menjamin menemukan solusi yang terbaik jika terdapat beberapa solusi berbeda?

Metode pencarian atau teknik searching terbagi menjadi dua, yaitu:

-          Blind Searching

-          Heuristic searching

Blind Searching(Pencarian Buta)

Salah satu metode ini merupakan teknik pencarian yang tidak memiliki informasi awal, sehingga disebut dengan pencarian buta. Jadi jika suatu masalah lalu kita menemukan sebuah solusi maka pencarian tersebut akan berhenti dengan skema kasarnya berupa (masalahàpencarianàsolusi). Ciri-ciri dari metode ini yaitu:

-          Membangkitkan simpul berdasarkan urutan.

-          Kalau ada solusi maka solusi akan ditemukan.

-          Hanya memiliki informasi tentang node yang telah dibuka (node selanjutnya tidak diketahui). 

-          Variabel data pada Blind Search tidak mempunyai atribut / informasi tambahan.

A.     Pencarian melebar pertama (Breadth – First Search)

 Breadth First Search yaitu model pencarian yang memakai metode melebar. Metode pencarian ini menggunakan teknik pencarian solusi yang menggunakan cara membuka node(titik) pada tiap levelnya. Algoritma yang melakukan pencarian secara melebar yang mengunjungi simpul secara preorder yaitu mengunjungi suatu simpul kemudian mengunjungi semua simpul yang bertetangga dengan simpul tersebut terlebih dahulu. Selanjutnya, simpul yang belum dikunjungi dan bertetangga dengan simpul-simpul yang tadi dikunjungi, demikian seterusnya. algoritma BFS menggunakan graf sebagai media representasi persoalan, tidak sulit untuk mengaplikasikan algoritma ini dalam persoalan-persoalan teori graf.

Keuntungan BFS:

·           Tidak menemui jalan buntu.

·           Jika ada suatu solusi, maka Braedth First Search akan menemukannya. Dan jika didapat lebih dari satu solusi, maka solusi minimum akan ditemukan.

Kelemahan BFS:

·           Membutuhkan memori yang cukup banyak, karena menyimpan semua node dalam suatu pohon.

·           Membutuhkan waktu yang cukup lama, karena akan menguji n level untuk mendapatkan solusi pada level ke – ( n + 1 )

·           Idenya mirip dengan algo prim dan dijkstra.

·           Traversal dimulai dari simpul v.

·           Algoritma :

-       Kunjungi simpul v,

-       Kunjungi semua simpul yang bertetangga dengan simpul v terlebih dahulu,

-       Kunjungi simpul yang belum dikunjungi dan bertetangga dengan simpul – simpul yang tadi di kunjungi, demikian seterusnya.

·           Jika graf berbentuk pohon berakar, maka semua simpul pada aras d dikunjungi lebih dahulu sebelum simpul – simpul pada aras d + 1.

Contoh Algoritma Breadth First Search :

Dalam algoritma Breadth First Search, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yan bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian. Untuk memperjelas cara kerja algoritma Breadth First Search beserta antrian yang digunakannya, berikut langkah-langkah algoritma Breadth First Search:

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.

B.     Pencarian mendalam pertama (Depth – First Search)

Proses pencarian dilakukan pada semua anaknya sebelum dilakukan pencarian ke node-node yang selevel. Pencarian ini 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.

Dalam algoritma BFS, simpul anak yang telah dikunjungi disimpan dalam suatu antrian. Antrian ini digunakan untuk mengacu simpul-simpul yang bertetangga dengannya yang akan dikunjungi kemudian sesuai urutan pengantrian.Untuk memperjelas cara kerja algoritma BFS beserta antrian yang digunakannya, berikut langkah-langkah 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.

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, 1

Gambar (c) BFS(1): 1, 2, 3, 4, 5, 6, 7, 8, 9

Keuntungan DFS:

·           Membutuhkan memori yang relaatif kecil, karena hanya node – node pada lintasan yang aktif yang disimpan.

·           Secara kebetulan, metode Depth First Search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

Kelemahan DFS:

·           Memungkinkan tidak ditemukannya tujuan yang diharapkan.

·           Hanya akan mendapatkan satu solusi pada setiap pencarian.

SUMBER:

 http://www.elangsakti.com/2013/03/bahasan-fundamental-tentang-blind.html
http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html