Tugas

1.      Metode Pencarian Buta (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 dua macam yaitu :

Breadth First Search

·         Breadth First Search merupakan salah satu dari metode pencarian buta.  Mengapa dikatakan pencarian buta ? istilah buta disini lebih dikenal dengan nama blind. Dikatakan buta karena memang tidak ada informasi awal yang digunakan dalam proses pencarian.

·         Breadth First Search (BFS) juga memiliki alur algoritma yang paling sederhana dibandingkan dengan metode blind yang lain. Itulah alasan mengapa BFS selalu dipelajari lebih dulu ketika membahas masalah pencarian buta.

·         BFS akan mencari satu per satu node secara melebar dari kiri ke kanan secara berurutan berdasarkan tingkat level nodenya. Jika pada satu level belum ditemukan solusi yang diinginkan, maka pencarian dilanjutkan hingga level berikutnya. Demikian seterusnya hingga ditemukan solusi. Maka, dengan cara seperti ini, BFS menjamin ditemukannya solusi apabila solusinya memang ada.

Dalam persoalan pada gambar di atas, urutan node yang dilalui pada pencaian BFS adalah a, b, c, d, e, f, g, h. Seperti pada gambar di bawah ini.

Contoh:

Depth First Search

            Depth First Search merupakan suatu metode pencarian  pada sebuah  pohon dengan menelusuri satu cabang sebuah pohon sampai menemukan solusi. Pencarian dilakukan dalam satu langkah dalam setiap level dari yang paling kiri hingga dilanjutkan pada langkah sebelah kanan. Apabila solusi ditemukan maka tidak diperlukan proses penelusuran balik untuk mendapatkan jalur yang diinginkan.

DFS memiliki beberapa keuntungan,yaitu memori yang di gunakan tidak terlalu banyak karena tidak membuka semua node

Contoh:

2.      Metode Pencarian Heuristik

Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namum dengan kemungkinan mengorbankan kelengkapan.

merupakan suatu strategi untuk melakukan proses pencarian ruang keadaan (state space) suatu problema secara selektif, yang memandu proses pencarian yang kita lakukan di sepanjang jalur yang memiliki kemungkinan sukses paling besar, dan mengesampingkan usaha yang bodoh dan memboroskan waktu.
Heuristik adalah sebuah teknik yang mengembangkan efisiensi dalam proses pencarian, namun dengan kemungkinan mengorbankan kelengkapan (completeness).
            Heuristic Search memperkirakan jarak menuju Goal (yang disebut dengan fungsi heuristik).
Fungsi heuristik ini digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.
Jenis-jenis Heuristic Searching :

·                     Generate and Test

·                     Hill Climbing

·                     Best First Search

·                     Alpha Beta Prunning

·                     Means-End-Anlysis

·                     Constraint Satisfaction

Kali ini yang akan dibahas adalah metode Generate and Test, Hill Climbing. 

·         Generate & Test

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

Strategi bangkitkan dan uji (generate and test) merupakan pendekatan yang paling sederhana dari semua pendekatan yang akan dibicarakan.
Pendekatan ini meliputi langkah–langkah sebagai berikut :

1.             Buatlah/bangkitkan sebuah solusi yang memungkinkan. Untuk sebuah problema hal ini dapat berarti pembuatan sebuah titik khusus dalam ruang problema.

2.             Lakukan pengujian untuk melihat apakah solusi yang dibuat benar–benar merupakan sebuah solusi, dengan cara membandingkan titik khusus tersebut dengan goal-nya (solusi).

3.             Jika telah diperoleh sebuah solusi, langkah – langkah tersebut dapat dihentikan. Jika belum, kembalilah ke langkah pertama.

Jika pembangkitan atau pembuatan solusi – solusi yang dimungkinkan dapat dilakukan secara sistematis, maka prosedur ini akan dapat segera menemukan solusinya (bila ada).  Namun, jika ruang problema sangat besar, maka proses ini akan membutuhkan waktu yang lama.
Metode generate and test ini memang kurang efisien untuk masalah yang besar atau kompleks

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 kal i. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti gambar di bawah ini: 

Penyelesaian dengan metode Generate and Test

·         Hill Climbing

Metode ini hampir sama dengan metode pembangkitan dan pengujian, hanya saja proses pengujian dilakukan dengan menggunakan fungsi heuristi006B. 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.

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 l intasan dengan menukar posisi urutan 2 kota, maka kita akan mendapatkan sebanyak: 

atau sebanyak 6 kombinasi (lihat gambar dibawah). Fungsi heuristic yang digunakan adalah panjang lintasan yang terjadi 

Sumber :

http://www.charisfauzan.net/2015/01/pencarian-buta-teori-dan-implementasi.html

https://www.researchgate.net/publication/307812355_Penggunaan_Metode_Depth_First_Search_DFS_dan_Breadth_First_Search_BFS_pada_Strategi_Game_Kamen_Rider_Decade_Versi_03

https://shabri-prayogi.blogspot.co.id/2013/08/teknik-pencarian-heuristik-heuristic.html

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

https://aiukswkelasgkelompok7.wordpress.com/metode-pencarian-dan-pelacakan/

http://fryunfirst.blogspot.co.id/2015/06/pencarian-heuristik-heuristic-search.html