Masalah penjual keliling

Traveling Salesman Problem (sering disebut TSP) adalah masalah algoritmik klasik dalam bidang ilmu komputer dan riset operasi. Ini difokuskan pada optimasi. Dalam konteks ini, solusi yang lebih baik sering kali berarti solusi yang lebih murah, lebih singkat, atau lebih cepat. TSP adalah masalah matematika. Hal ini paling mudah diekspresikan sebagai grafik yang menggambarkan lokasi dari sekumpulan node.

Travelling salesman problem didefinisikan pada tahun 1800-an oleh matematikawan Irlandia W. R. Hamilton dan oleh matematikawan Inggris Thomas Kirkman. Hamilton's Icosian Game adalah teka-teki rekreasi yang didasarkan pada menemukan siklus Hamiltonian. Bentuk umum TSP tampaknya pertama kali dipelajari oleh para matematikawan selama tahun 1930-an di Wina dan di Harvard, terutama oleh Karl Menger. Menger mendefinisikan masalahnya, mempertimbangkan algoritma brute-force yang jelas, dan mengamati ketidakoptimalan heuristik tetangga terdekat:

Kita nyatakan dengan masalah pengirim pesan (karena dalam prakteknya masalah ini harus dipecahkan oleh setiap tukang pos, bagaimanapun juga oleh banyak pelancong) tugas untuk menemukan, untuk ﬁnitely banyak titik yang jarak berpasangannya diketahui, rute terpendek yang menghubungkan titik-titik tersebut. Tentu saja, masalah ini dapat diselesaikan dengan banyak percobaan yang berhingga banyaknya. Aturan-aturan yang akan mendorong jumlah percobaan di bawah jumlah permutasi dari titik-titik yang diberikan, tidak diketahui. Aturan yang pertama-tama harus dilakukan dari titik awal ke titik terdekat, kemudian ke titik yang paling dekat dengan titik ini, dst., secara umum tidak menghasilkan rute terpendek.

Hassler Whitney di Princeton University memperkenalkan nama traveling salesman problem segera setelahnya.

Seorang salesman ingin mengunjungi semua kota, A, B, C, dan D. Apa cara terbaik untuk melakukan ini (tiket pesawat termurah, dan waktu tempuh minimal)?

Rute optimal seorang salesman yang mengunjungi 15 kota terbesar di Jerman. Rute yang ditunjukkan adalah yang terpendek dari 43.589.145.600 kemungkinan rute.

William Rowan Hamilton

Menyatakan masalah

Travelling Salesman Problem menggambarkan seorang salesman yang harus melakukan perjalanan antara N kota. Urutan perjalanannya tidak dipedulikannya, selama ia mengunjungi masing-masing kota sekali selama perjalanannya, dan selesai di tempat ia berada pada awalnya. Setiap kota terhubung ke kota-kota lain yang berdekatan, atau node, dengan pesawat terbang, atau melalui jalan darat atau kereta api. Setiap hubungan antara kota-kota tersebut memiliki satu atau lebih bobot (atau biaya) yang melekat. Biaya menggambarkan seberapa "sulit" untuk melintasi sisi ini pada graf, dan dapat diberikan, misalnya, dengan biaya tiket pesawat atau tiket kereta api, atau mungkin dengan panjang sisi, atau waktu yang diperlukan untuk menyelesaikan perjalanan. Salesman ingin menjaga biaya perjalanan, dan juga jarak yang ditempuhnya serendah mungkin.

Traveling Salesman Problem (Masalah Penjual Keliling) adalah tipikal dari kelas besar masalah optimasi "sulit" yang telah menarik minat para matematikawan dan ilmuwan komputer selama bertahun-tahun. Yang paling penting, masalah ini memiliki aplikasi dalam sains dan teknik. Misalnya, dalam pembuatan papan sirkuit, penting untuk menentukan urutan terbaik di mana laser akan mengebor ribuan lubang. Solusi yang efisien untuk masalah ini mengurangi biaya produksi bagi produsen.

Kesulitan

Secara umum, masalah travelling salesman sulit untuk dipecahkan. Jika ada cara untuk memecah masalah ini menjadi masalah komponen yang lebih kecil, komponen-komponen tersebut akan sekurang-kurangnya sama rumitnya dengan masalah aslinya. Inilah yang disebut ilmuwan komputer sebagai masalah NP-hard.

Banyak orang telah mempelajari masalah ini. Solusi yang paling mudah (dan paling mahal) adalah dengan mencoba semua kemungkinan. Masalahnya adalah bahwa untuk N kota Anda memiliki (N-1) kemungkinan faktorial. Ini berarti bahwa hanya untuk 10 kota ada lebih dari 180 ribu kombinasi untuk dicoba (karena kota awal sudah ditentukan, maka bisa ada permutasi pada sembilan kota sisanya). Kita hanya menghitung setengahnya karena setiap rute memiliki rute yang sama secara terbalik dengan panjang atau biaya yang sama. 9! / 2 = 181 440

Solusi yang tepat untuk masalah ini bisa ditemukan, dengan menggunakan algoritme branch and bound. Saat ini, hal ini dimungkinkan hingga 85.900 kota.
Pendekatan heuristik menggunakan seperangkat aturan panduan untuk pemilihan node berikutnya. Tetapi karena heuristik menghasilkan perkiraan, mereka tidak akan selalu memberikan solusi optimal, meskipun heuristik yang dapat diterima dengan kualitas tinggi dapat menemukan solusi yang berguna dalam sebagian kecil dari waktu yang dibutuhkan untuk menyelesaikan masalah secara penuh. Contoh heuristik untuk sebuah node adalah penjumlahan dari berapa banyak node yang belum dikunjungi yang "dekat" dengan node yang terhubung. Hal ini dapat mendorong salesman untuk mengunjungi sekelompok node yang berdekatan yang dikelompokkan bersama sebelum pindah ke cluster alami lainnya dalam graf. Lihat algoritma Monte Carlo dan algoritma Las Vegas

Pertanyaan dan Jawaban

T: Apa yang dimaksud dengan Masalah Penjual Keliling?

J: Travelling Salesman Problem (TSP) adalah masalah algoritmik klasik di bidang ilmu komputer dan riset operasi. TSP berfokus pada optimasi, dengan solusi yang lebih baik sering kali berarti solusi yang lebih murah, lebih pendek, atau lebih cepat.

T: Bagaimana TSP dinyatakan?

J: TSP paling mudah diekspresikan sebagai grafik yang menggambarkan lokasi sekumpulan node.

T: Siapa yang pertama kali mendefinisikan TSP?

A: Masalah salesman keliling didefinisikan pada tahun 1800-an oleh matematikawan Irlandia, W. R. Hamilton, dan matematikawan Inggris, Thomas Kirkman.

T: Siapa yang mempelajarinya lebih lanjut selama tahun 1930-an?

J: Selama tahun 1930-an, ahli matematika Karl Menger di Wina dan Harvard mempelajarinya lebih lanjut.

T: Apa yang diperkenalkan oleh Hassler Whitney setelahnya?

J: Hassler Whitney di Universitas Princeton memperkenalkan nama "masalah salesman keliling" segera setelah definisinya.

T: Apa yang dimaksud dengan "solusi yang lebih baik" dalam konteks ini?

J: Dalam konteks ini, solusi yang lebih baik sering kali berarti solusi yang lebih murah, lebih singkat, atau lebih cepat.

T: Algoritma apa yang dianggap jelas oleh Menger ketika mempelajari TSP?

J: Menger mempertimbangkan algoritma brute-force yang jelas ketika mempelajari TSP dan mengamati bahwa menggunakan heuristik tetangga terdekat tidak selalu memberikan hasil yang optimal.