Metode ini merupakan pemggabungan antara depth-first
search dengan pelacakan mundur (backtracking),
yaitu bergerak kebelakang menuju pada suatu keadaan awal. Algoritma;
- Bangkitkan suatu kemungkinan solusi (membangkitkan suatu titik tertentu atau lintasan tertentu dari keadaan awal)
- Uji untuk melihat apakah node tersebut benar-benar merupak solusinya dengan cara membandingkan node tersebut atau node akhir dari suatu lintasan yang dipilih dengan kumpulan tujuan yang diaharapkan
- Jika solusi ditemukan, keluar. Jika tidak, 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 rute terpendek dimana setiap kota hanya boleh dikunjungin
tepat 1 kali. Misalkan ada 4 kota dengan jarak antara tiap-tiap kota seperti
gambar dibawah ini:
Penyelesaian dengan metode Generate and Test
Tidak ada komentar:
Posting Komentar