Persoalan Pedagang Keliling [PDF]

Citation preview

8.14 Persoalan Pedagang Keliling Persoalan Pedagang Keliling ( Travelling Salesperson Problem- TSP) termasuk kedalam persoalan yang sangat terkenal dalam teori graf. Nama persoalan ini diilhami oleh masalah pedagang yang berkeliling mengunjungi sejumlah kota. Tentukan sirkuit terpendek yang harus dilalui oleh seorang pedagang bila pedagang itu berangkat dari sebuah kota asal dan menyinggahi setiap kota tepat satu kali dan kembali lagi ke kota asal keberangkatan. Kota dapat dinyatakan sebagai simpul graf, sedangkat sisi menyatakan jalan yang menghubungkan dua buah kota. Bobot pada sisi menyatakan jarak antara dua buah kota. Persoalan pedagang tidak lain adalah menentukan sirkuit Hamilton yang memiliki bobot minimum pada sebuah graf terhubung. Meskipun persoalan ini bernama perjalanan pedagang namun penerapannya tidak hanya pada kasus yang berhubungan dengan pedagang. Banyak terapan TSP yang muncul dalam kehidupan sehari-hari. Pada persoalan TSP ini jika setiap simpul mempunyai sisi ke simpul yang lain, maka graf yang merepresentasikannya adalah graf lengkap berbobot. Pada sembarang graf lengkap dengan n buah simpul (n > 2), jumlah sirkuit Hamilton yang berbeda adalah (n – 1)!/2. Rumus ini dihasilkan dari kenyataan bahwa dimulai dari sembarang simpul kita mempunyai n - 1 buah sisi untuk dipilih dari simpul pertama, n - 2 sisi dari simpul kedua, dan seterusnya. Ini adalah pilihan yang independen, sehingga kita memperoleh (n – 1)! Pilihan. Jumlah itu harus dibagi dengan 2, karena setiap sirkuit Hamilton terhitung dua kali, sehingga semuanya ada (n – 1)!/2 buah sirkuit Hamilton.



Tinjau graf lengkap dengan n=4 simpul ssperti yang ditunjukkan pada gambar. graf tersebut memiliki ( 4 – 1)!/2 = 3 sirkuit Hamilton, yaitu :



S1=( a ,b ,c , d , a ) atau ( a , d , c , b , a ) dengan panjang rute = 10 + 12 + 8 + 15 = 45 S2=( a , c , d , b , a ) atau ( a , b , d , c , a ) dengan panjang rute = 12 + 5 + 9 + 15 = 41



S3= ( a , c , b , d , a ) atau ( a , d , b , c , a ) dengan panjang rute = 10 + 5 + 9 + 8 = 32



Jadi sirkuit Hamilton terpendek adalah S3 dengan panjang sirkuit 32. Ini adalah solusi persoalan TSP untuk graf berbobot. Persoalan TSP adalah persoalan yang sulit ( hard problem ) dipandang dari sudut komputasinya. Artinya secara teoritis TSP dapat dipecahkan dengan mengenumerasi (n – 1)!/2 buah sirkuit Hamilton, menghitung panjang rute masing-masing sirkuit, dan kemudian memilih sirkuit yang memiliki panjang rute terpendek. Untuk n yang besar, jumlah sirkuit Hamilton yang harus diperiksa tentu saja sangat banyak. Misalnya untuk jumlah simpul n = 20 akan terdapat 19!/2 sikuit Hamilton penyelesaian.