Heuristic Search

2. Heuristic Search

A. Pembangkitan dan Pengujian (Generate and Test)

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

Algoritma:

1.Bangkitkan suatu kemungkinan solusi(membangkitkan suatu titik 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.

B. Pendakian Bukit (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:

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 :

– Jika keadaan baru merupakan tujuan, keluar

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

– Jika keadaan baru tidak lebih baik daripada keadaan sekarang, maka  lanjutkan iterasi.

Contoh : Traveling 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 dikunjungi tepat 1 kali. Misal ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :

a) Solusi – solusi yang mungkin dengan menyusun kota-kota dalam urutan

abjad, misal :

A – B – C – D : dengan panjang lintasan (=19)

A – B – D – C : (=18)

A – C – B – D : (=12)

A – C – D – B : (=13)

Metode Simple Hill Climbing

 Ruang keadaan berisi semua kemungkinan lintasan yang mungkin. Operator digunakan untuk menukar posisi kota-kota yang bersebelahan. Fungsi heuristik yang digunakan adalah panjang lintasan yang terjadi. Operator yang akan digunakan adalah menukar urutan posisi 2 kota dalam 1 lintasan. Bila ada n kota, dan ingin mencari kombinasi lintasan dengan menukar posisi urutan 2 kota, maka akan didapat

sebanyak :

Keenam kombinasi ini akan dipakai semuanya sebagaioperator, yaitu :

Tukar 1,2 = menukar urutan posisi kota ke – 1 dengan kota ke – 2

Tukar 2,3 = menukar urutan posisi kota ke – 2 dengan kota ke – 3

Tukar 3,4 = menukar urutan posisi kota ke – 3 dengan kota ke – 4

Tukar 4,1 = menukar urutan posisi kota ke – 4 dengan kota ke – 1

Tukar 2,4 = menukar urutan posisi kota ke – 2 dengan kota ke – 4

Tukar 1,3 = menukar urutan posisi kota ke – 1 dengan kota ke – 3

Metode Steepest – Ascent Hill Climbing

·         Steepest – ascent hill climbing hampir sama dengan simple – ascent hill climbing, hanya saja gerakan pencarian tidak dimulai dari kiri, tetapi berdasarkan nilai heuristik terbaik.

·         Keadaan awal, lintasan ABCD (=19).

·         Level pertama, hill climbing memilih nilai heuristik terbaik yaitu ACBD (=12) sehingga ACBD menjadi pilihan selanjutnya.

·         Level kedua, hill climbing memilih nilai heuristik terbaik, karena nilai heuristik lebih besar dibanding ACBD, maka hasil yang diperoleh lintasannya tetap ACBD (=12).

Sumber :

http://slideplayer.info/slide/2805739/

lily.staff.gunadarma.ac.id/Downloads/files/17559/Pertemuan2.pdf

Anik Nur Handayani, ST., MT. T. Sutojo,S.Si.,M.Kom. Edy Mulyanto, S.Si.,M.Kom. Dr. VIncent Suhartono. (2009).  Kecerdasan  Buatan. Yogyakarta:  Andi.

https://rinnooberta.wordpress.com/2013/10/29/pencarian-heuristik/

Blind Search

1.      Blind Search

Blind Searching adalah model pencarian buta atau pencarian yang tidak memiliki informasi 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).

A. Pencarian Melebar pertama (Breadth-First Search)

Semua node pada level n akan dikunjungi terlebih dahulu sebelum level n+1. BFS (Breadth First Search) juga merupakan salah satu algoritma penelusuran struktur graf / pohon seperti DFS, namun bedanya BFS melakukan pencarian secara melebar atau per level pohon. Simpul ditelusuri dari root kemudian menelusuri semua simpul pada setiap level di bawahnya ( misalnya prioritas penelusuran dari kiri ke kanan ), maka penelusuran dilakukan terus dari simpul paling kiri ke simpul anak – anak tetangganya yang selevel. 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 :

1. Masukkan simpul root ke dalam antrian
2. Periksa antrian terdepan apakah memiliki anak simpul
3. Jika ya, masukan semua anak simpul ke dalam antrian
4. Hapus antrian terdepan
5. 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.

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 implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Kita akan membahas dengan cara yang menggunakan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Bagaimana cara kerjanya ? Berikut ini adalah urutan algoritmanya :

1. Masukkan simpul root ke dalam tumpukan dengan push
2. Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas
3. Hapus isi stack teratas dengan prosedur pop
4. Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul
5. Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack
6. 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 :

Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L

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. Oiya, pada iterasi ke 13 itu kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.

Sumber : 

http://mudt-dae.blogspot.co.id/2010/04/kcb-kecerdasan-buatan.html

https://aig1003.wordpress.com/

http://yoosinhay.blogspot.co.id/2011/03/teknik-pencarian-perancangan.html

https://saungkode.wordpress.com/2014/04/16/penelusuran-pohon-biner-berdasarkan-kedalaman-dengan-algoritma-dfs-stack-dan-secara-melebar-level-order-dengan-algoritma-bfs-queue-dan-implementasinya-dalam-bahasa-c/