PENG. TEKNOLOGI SISTEM CERDAS #
TUGAS. 5
{ HEURISTIC SEARCH }
Heuristic search
Pencarian buta tidak selalu dapat diterapkan dengan baik, hal ini
disebabkan waktu aksesnya yang cukup lama & besarnya memori yang
diperlukan. Kelemahan ini dapat diatasi jika ada informasi tambahan dari domain
yang bersangkutan.
1.Generate
& Test
Teknik Generate-and-Test adalah teknik yang paling mudah dibandingkan
teknik search yang lain, namun relatif lebih lama dalam mendapatkan solusi.
Algoritma Generate-and-Test :
- Bentuk solusi yang mungkin. Untuk beberapa masalah, ini berarti membentuk poin terpisah dari area permasalahan. Pada masalah lain, ini berarti membentuk jalur dari stata awal.
- Lakukan test untuk melihat apakah poin yang ditemui adalah solusi dengan membandingkan poin yang dipilih atau poin terakhir dari jalur yang dipilih dengan kumpulan stata tujuan
3. Jika solusi sudah ditemukan, quit. Jika belum kembali
ke langkah 1.
Contoh Generate-and-Test
:
2.
Hill Climbing
Teknik Hill Climbing adalah pengembangan dari teknik Generate-and-Test,
dengan penambahan adanya umpan balik dari prosedur test yang sudah digunakan
untuk membantu memilih arah mana yang harus ditelusuri pada setiap area search.
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 :
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) dst
SUMBER :
Komentar
Posting Komentar