Apa itu Traveling Salesman Problem?
Traveling Salesman Problem (TSP) adalah masalah optimasi dalam pemrograman yang bertujuan mencari rute terpendek yang menghubungkan sekumpulan titik tertentu. Mencari solusi yang benar-benar optimal butuh daya komputasi yang besar, jadi biasanya digunakan berbagai metode pendekatan untuk mendapatkan solusi yang cukup baik.
Contoh Traveling Salesman Problem
Penjelasan sederhana dari TSP biasanya seperti ini: “Seorang salesman harus mengunjungi N kota di peta dan kembali ke titik awal. Dia ingin menghabiskan bahan bakar seminimal mungkin. Buatlah program untuk menemukan rute terpendek.”
Masalah ini kelihatannya simpel, tapi ternyata nggak semudah itu. Kita bisa saja menulis program yang mencoba semua kemungkinan jalur dan memilih yang paling pendek. Tapi masalahnya, semakin besar jumlah titik N, jumlah jalur yang harus dicek juga meningkat secara eksponensial, tepatnya sebesar N! (faktorial dari N). Misalnya, jika ada 10 kota saja, jumlah kemungkinan rutenya sudah mencapai 3,6 juta!
Karena kompleksitasnya, TSP jadi sulit dihitung secara cepat dengan komputer biasa. Bahkan dengan superkomputer, masalah ini tetap sulit diselesaikan dalam skala besar. Masalah yang kompleksitasnya meningkat lebih cepat daripada eksponensial ini disebut sebagai masalah NP-hard.
Cara Menyelesaikan Traveling Salesman Problem
Daripada mencari solusi optimal yang sempurna, pendekatan dalam TSP seringkali berfokus pada mencari solusi yang cukup baik dalam waktu yang lebih cepat. Karena banyaknya variabel dalam TSP, pendekatan heuristik yang cepat dan efisien sering kali lebih menarik.
Dalam dunia komputer, TSP sering digunakan untuk optimasi rute data antar node, optimasi jaringan, perancangan perangkat keras, alat perencanaan jalur, hingga sequencing DNA.
Sejarah Traveling Salesman Problem
Matematikawan Irlandia W.R. Hamilton dan matematikawan Inggris Thomas Kirkman pertama kali menggambarkan TSP di tahun 1800-an lewat permainan bernama Icosian Game. Solusinya didasarkan pada Hamiltonian cycle, yaitu jalur yang mengunjungi semua titik tanpa mengulang jalur yang sama.
TSP telah diteliti selama puluhan tahun dan beberapa metode penyelesaiannya telah dikembangkan. Banyak yang menggunakan heuristik, yaitu metode yang menggunakan probabilitas untuk mendapatkan hasil yang cukup baik meskipun tidak selalu optimal. Beberapa metode lain termasuk branch and bound, algoritma Monte Carlo, dan algoritma Las Vegas. Dengan pendekatan ini, bisa didapatkan solusi yang hanya terpaut beberapa persen dari solusi optimal, bahkan untuk jutaan node.
Manusia vs. Komputer dalam Menyelesaikan TSP
TSP menarik karena manusia sering kali bisa menyelesaikannya dengan cukup baik secara intuitif, sementara komputer tidak. Dengan sekumpulan 100 titik, manusia bisa menemukan solusi dalam hitungan detik yang hampir setara dengan algoritma heuristik terbaik.
Diharapkan bahwa komputer kuantum bisa memberikan solusi lebih cepat untuk masalah optimasi seperti TSP. Karena menggunakan qubit yang memungkinkan komputasi paralel dalam jumlah besar, komputer kuantum dapat menyelesaikan masalah ini jauh lebih cepat dibandingkan komputer klasik.