TEKNIK PENCARIAN

A. METODE BLIND SEARCH

       Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki inforamasi awal, model pencarian ini memiliki tiga ciri – ciri utama yaitu:

-  Membangkitkan simpul berdasarkan urutan

-  Kalau ada solusi maka solusi akan ditemukan

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

Blind Searching sendiri dibagi menjadi tiga macam yaitu :

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

 o    Pada metode breadth-first search, semua node pada level n akan dikunjungi terlebih dahulu                sebelum mengunjungi node-node pada level n+1.

o    Pencarian dimulai dari node akar terus ke level ke-1 dari kiri ke kanan, kemudian berpindah ke           level berikutnya, demikian pula dari kiri ke kanan hingga ditemukannya solusi (lihat algoritma di        bawah ini).

•  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).

       2. Depth First Search

           Depth-first Search sering disebut juga pencarian mendalam. Sesuai dengan namanya “pencarian mendalam”, DFS tidak mencari solusi per level, namun mencari pada kedalaman sebelah kiri terlebih dahulu, kemudian bila belum ditemukan “goal”nya dilanjutkan ke sisi sebelah kanan dan seterusnya sampai ditemukan target/goal.

            Teknik pencarian dengan Depth First Search adalah dengan melakukan ekspansi menuju node yang paling dalam pada tree. Node paling dalam dicirikan dengan tidak adanya successor dari node itu. Setelah node itu selesai diekspansi, maka node tersebut akan ditinggalkan, dan dilakukan ke node paling dalam lainnya yang masih memiliki successor yang belum diekspansi.

· 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 kasus Breadth First Search dan Depth First Search:

B. METODE HEURISTIK SEARCH

     Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan (completeness). Fungsi heuristik digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

    1. Generate and Test

         Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak ke belakang menuju pada suatu keadaan awal.

· Algoritma :

1. Bangkitkan suatu kemungkinan solusi (membangkitkan suatu tititk tertentu atau lintasan tertentu dari keadaan awal).

2. Uji untuk melihat apakah node tersebut benar-benar merupakan solusinya dengan cara membandingkan node terebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diharapkan.

3. Jika solusi ditemukan, keluar. Jika tidak, ulangi kembali langkah pertama.

Contoh : “Travelling Salesman Problem (TSP)”

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui ruter terpendek dimana setaip kota hanya boleh dikkunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini :

Penyelesaian dengan metode Generate and Test

Alur pencarian dengan Generate and Test

        

     2. Hill Climbing

          Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristic. Pembangkitan keadaan berikutnya tergantung pada feedback dari prosedur pengetesan. Tes yang berupa fungsi heuristic ini akan menunjukkan seberapa baiknya nilai terkaan yang diambil terhadap keadaan-keadaan lainnya yang mungkin.

· Algoritma Simple Hill Climbing

1. Cari operator yang belum pernah digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

a) Kerjakan langkah-langkah berikut sampai solusinya ditemukan atau sampai tidak ada operator baru yang akan diaplikasikan pada keadaan sekarang :
Cari operator yang belum digunakan; gunakan operator ini untuk mendapatkan keadaan yang baru.

b) Evaluasi keadaan baru tersebut :

(i) Jika keadaan baru merupakan tujuan, keluar

(ii) Jika bukan tujuan, namun nilainya lebih baik daripada keadaan sekarang, maka jadikan keadaan baru tersebut menjadi keadaan sekarang.

(iii) Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka lanjutkan iterasi.

Pada simple hill climbing, ada 3 masalah yang mungkin:

- Algoritma akan berhenti kalau mencapai nilai optimum local

- Urutan penggunaan operator akan sangat berpengaruh pada penemuan solusi

- Tidak diijinkan untuk melihat satupun langkah sebelumnya.

Contoh : TSP dengan Simple Hill Climbing

Seorang salesman ingin mengunjungi n kota. Jarak antara tiap-tiap kota sudah diketahui. Kita ingin mengetahui rute terpendek dimana setiap kota hanya boleh dikunjungi 1kali saja. Misal ada 4kota dengan jarak antara tiap-tiap kota seperti berikut ini:

menggunakan Steepest-Ascent HC

-  Gerakan pencarian slanjutnya berdassarkan nilai heuristik terbaik.

-  algoritma:

  1. Evaluasi keadaan awal, jika tujuan berhenti jika tidak lanjut dengan keadaan sekarang sebagia            keadaan awal.

  2. Kerjakan hingga tujuan tercapai atau hingga iterasi tidak memberi perubahan sekarang.

      i.  Tentukan SUCC sebagai nilai heuristik terbaik dari successor-successor

      ii. Kejakan tiap operator yang digunakan oleh keadaan sekarang.

          a. Gunakan operator tersebut dan bentuk keadaan baru

          b. Evaluasi keadaan baru. Jika tujuan keluar, jika bukan bandingkan nilai heuristiknya dengan                 SUCC. Jika lebih baik jadikan nilai heuristik keadaan baru tersebut sebagi SUCC. Jika                         tidak, nilai SUCC tidak berubah. 

       iii. Jika SUCC lebih baik dari nilai heuristik keadaan sekarang, ubah SUCC menjadi keadaan                     sekarang.

Pada steepest-ascent hill climbing inni ada 3 masalah yang mungkin, yaitu:

-  Local optimum: keadaan semua tetangga lebih buruk atau sama dengan keadaan dirinya.

-  Plateou: keadaan semua tetangga sama dengan keaddaan dirinya.

-  Ridgez local optimum yang ebih disebabkan karena ketidak mampuan untuk menggunakan 2              operator sekaligus.

Traveling Salesman Problem dengan Steepest-Acsent Hill Climbing:

Sumber:

http://wisatapikiran.blogspot.co.id/2013/03/perbedaan-blind-search-dengan.html

http://najibzot.blogspot.co.id/p/teknik-searching-kecerdasan-buatan-di.html

https://www.slideshare.net/ceezabramovic/metode-pencarian-heuristik