TSP adalah problem untuk menentukan urutan dari sejumlah
kota yang harus dilalui oleh salesman, setiap kota hanya boleh dilalui satu
kali dalam perjalanannya, dan perjalanan tersebut harus berakhir pada kota
keberangkatannya dimana salesman tersebut memulai perjalananya, dengan jarak
antara setiap kota satu dengan kota lainnya sudah diketahui. Salesman tersebut
harus meminimalkan pengeluaran biaya, dan jarak yang harus ditempuh untuk
perjalanannya tersebut.
Kota dapat dinyatakan sebagai sebuah simpul graf, sedangkan
sisi menyatakan jalan yang menghubungkan antara dua kota. Bobot pada sisi menyatakan
jumlah antara dua buah kota. Persoalan ini adalah persoalan yang menentukan
sirkuit Hamilton dengan sisi memiliki bobot minimum pada suatu graf terhubung.
Algoritma exhaustive, yaitu dengan mencari semua kombinasi
yang mungkin terjadi, kemudian memilih kombinasi perjalanan dengan jarak
terdekat, algoritma ini mempunyai kompleksitas n!/2n.
Permasalahan :
· Diberikan
n buah kota serta diketahui jarak antara setiap kota satu dengan kota yang
lain. Temukan perjalanan (tour) terpendek yang melalui setiap kota lainnya
dengan hanya sekali melewati kota-kota tersebut dan kembali lagi ke kota asal
keberangkatan.
· Permasalahan
TSP ini dimodelkan sebagai graf lengkap dengan n buah simpul. Bobot pada setiap
setiap sisi menyatakan jarak antara dua buah kota yang bertetangga.
· Permasalahan
TSP tidak lain adalah menemukan sirkuit Hamilton dengan bobot paling minimum.
· Algoritma
exhaustive search untuk persoalan TSP :
A. Enumerasikan (list) semua sirkuit
Hamilton dari graf lengkap dengan n buah simpul.
B. Hitung (evaluasi) bobot
setiap sirkuit Hamilton yang ditemukan pada langkah 1.
C. Pilih sirkuit Hamilton yang
mempunyai bobot paling terkecil.
contoh diatas, graf tersebut memiliki n=4, jadi 4!/2(4)=3 sirkuit hamilton, jadi terdapat 3 rute yang dapat dilalui, sekarang tinggal tambahkan jarak antarkota dan pilihlah perjalanan dengan jumlah jarang terkecil
0 komentar: