Di sini akan dibahas mengenail solusi TSP dengan algoritma Generate & Test (GT). Pada prinsipnya, algoritma ini meng-generate sebuah kandidat solusi, lalu dites apakah kandidat tersebut solusi yang dicari. Iterasi berhenti jika solusi sudah ditemukan.
Tetapi untuk menyelesaikan kasus TSP ini, algoritma tersebut mengalami sedikit modifikasi, di mana iterasinya akan berhenti setelah semua kandidat solusi telah dites untuk menghasilkan solusi yang optimal.
Rute dikatakan valid jika jalur yang dilalui tidak berjarak 0. Jika rute valid, maka jarak dihitung lalu dibandingkan untuk mendapatkan jarak yang paling optimal.
Setiap rute yang valid akan dibandingkan dengan rute valid lainnya guna mendapatkan rute terpendek yang merupakan solusi dari kasus TSP-nya. Yang dalam hal ini dipecahkan menggunakan algoritma Generate & Test.
Kelebihan dari algoritma ini adalah pencariannya yang lengkap dan selalu menghasilkan solusi yang optimal. Sedangkan kekurangannya adalah tidak cocok untuk data yang besar/banyak dan waktu pencariannya yang lama sesuai dengan banyak datanya.
No comments:
Post a Comment