CitraRRahmedina

“Travelling 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. Misalkan ada 4 kota  dengan jarak antara tiap-tiap kota seperti berikut ini : Alur pencarian dengan  Generate and Test   Pencarian ke- Lintasan Panjang Lintasan Lintasan terpilih Panjang Lintasan terpilih 1 ABCD 19 ABCD 19 2 ABDC 18 ABDC 18 3 ACBD 12 ACBD 12 4 ACDB 13 ACBD 12 5 ADBC 16 ACBD 12 Dst…..

METODE PENCARIAN dan PELACAKAN 2 ( HEURISTIK ) MINGGU 5 5.1 BEST FIRST SEARCH Metode ini merupakan kombinasi dari metode depth first search dan breadth-first search. Pada metode best-first search, pencarian diperbolehkan mengunjungi node yang ada di level yang lebih rendah, jika ternyata node pada level yang lebih tinggi ternyata memiliki nilai heuristic yang lebih buruk. Tak seperti Hill Climbing, teknik Best First Search mempunyai kemampuan melakukan koreksi terhadap suatu langkah yang salah yang telah dipilih lebih dulu. Fungsi Heuristik yang digunakan merupakan prakiraan (estimasi) cost dari initial state ke goal state, yang dinyatakan dengan :  f’(n) = g(n) + h’(n) f’ = Fungsi evaluasi g = cost dari initial state ke current state h’ = prakiraan cost dari current state ke goal state Contoh:  Misalkan kita memiliki ruang pencarian seperti pada gambar berikut. Node M merupakan keadaan awal dan node T merupakan tujuannya. Biaya edge yang menghubungkan node M dengannode