Metode Pencarian dan Pelacakan 2 (Heuristik)

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

·  Fungsi heuristic digunakan untuk mengevaluasi keadaan-keadaan problema individual dan menentukan seberapa jauh hal tersebut dapat digunakan untuk mendapatkan solusi yang diinginkan.

·        Jenis-jenisHeuristic Searching:

§                            -Generate and Test.

§                            - Hill Climbing.

§                            -Best First Search.

§                            -Alpha Beta Prunning,Means-End-Anlysis,ConstraintSatisfaction, Simulated Annealing, dll.

Pembangkitan dan Pengujian (Generate and Test)

Metode ini merupakan penggabungan antara depth-first search dengan pelacakan mundur (backtracking), yaitu bergerak kebelakang menuju pada suatu ke adaan 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. Jikatidak, 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 dikunjungi tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti berikut ini :Pencarianke-Lintasan-PanjangLintasan-LintasanTerpilih-PanjangLintasanTerpilih

ReduksiMasalah

·         Kebanyakan solusi menggunakan pohon OR, dimana lintasan dari awa lsampai tujuan tidak terletak pada satu cabang.

·         Bila lintasan dari keadaan awal sampai tujuan dapat terletak pada satu cabang, maka kita akan dapat menemukan tujuan lebih cepat.

·         Graf AND-OR

·         Graf AO*

A.      Graf AND-OR

·         Pada dasarnya sama dengan algoritma Best First Search, dengan mempertimbangkan adanya arc AND.

·         Gambar berikut menunjukkan bahwa untuk mendapatkan TV orang bisa dengan cara singkat yaitu mencuri atau membeli asal mempunyai uang.

·         Untuk mendeskripsikan algoritma, digunakan nilai F_UTILITY untuk biaya solusi Goal.

B.      AlgoritmaAND-OR

1.       Inisialisasi graf ke node awal.

2.       Kerjakan langkah2 berikut hingga node awal SOLVED atau sampai biayanya lebih tinggi dari F_UTILITY :

·         Telusuri graf mulai dari node awal dan ikuti jalur terbaik. Akumulasikan kumpulan node yang ada pada lintasan tsb. dan belum pernah diekspansi atau diberilabel SOLVED.

·         Ambil satu node dan ekspansi node tsb. Jika tidak ada successor maka set F_UTILITY sebaga i nilai dari node tsb. Bila tidak demikian, tambahkans uccessor dari node tsb ke graf dan hitung nilai setiap f’(hanya gunakan h’dan abaikang). Jika f’=0 tandai node tsb dengan SOLVED.

·         Ubah f’ harapan dari node baru yang diekspansi. Kirim kan perubahan ini secara backward sepanjang graf. Jika node berisi suatu arc successor yang semua descendantnya berlabel SOLVED maka tandai node itudenganSOLVED.

Pencarian Terbaik Pertama (Best-First Search)

Metode ini merupakan kombinasi dari metode depth-first search dan breadth-first search. Pada metodebest-first search, pencarian diperbolehkan mengunjungi node yang ada dilevel yang lebih rendah, jika ternyat anode pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk.

Fungsi Heuristikyang digunakanmerupakanprakiraan(estimasi) cost dariinitial statekegoal state, yang dinyatakandengan:

f’(n) = g(n) + h’(n)

dimanaf’= Fungsievaluasi

g = cost dariinitial statekecurrent state

h’= prakiraancost daricurrent stateke

goal state

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

hendrik.staff.gunadarma.ac.id/.../teknik-pencarian-heuristik.pdf