Pemecah Masalah Penjual Keliling (TSP)

Tentang Pemecah Masalah Penjual Keliling (TSP)

Pemecah Masalah Penjual Keliling adalah kalkulator praktis dan edukatif untuk masalah klasik Masalah Penjual Keliling (TSP): diberikan sekumpulan kota dan jarak berpasangan, temukan tur terpendek yang mungkin untuk mengunjungi setiap kota tepat satu kali dan kembali ke titik awal. Pemecah ini menerima koordinat planar atau matriks jarak khusus, memilih algoritma terbaik secara otomatis berdasarkan ukuran masalah, dan merender tur yang dihasilkan sebagai peta SVG animasi.

Apa Itu Masalah Penjual Keliling?

Secara formal, diberikan graf berbobot lengkap G = (V, E) dengan himpunan simpul V = {1, 2, ..., n} dan bobot tepi d(i, j), TSP mencari permutasi π dari simpul yang meminimalkan:

Istilah terakhir menutup lingkaran. TSP adalah salah satu masalah tertua dan paling banyak dipelajari dalam optimasi kombinatorial — ini termasuk NP-hard dalam kasus umum, yang berarti tidak ada algoritma yang diketahui dapat menyelesaikan setiap instansi dalam waktu polinomial. Meskipun demikian, masalah ini muncul dalam aplikasi dunia nyata yang tak terhitung jumlahnya: perutean kendaraan, pengeboran PCB, pengurutan DNA, rute pengambilan barang di gudang, jadwal pengamatan astronomi, dan bahkan pengiriman pos pedesaan.

Cara Kerja Pemecah Ini

Pemrograman Dinamis Held–Karp (Tepat)

Untuk instansi kecil (hingga 12 kota), pemecah menghitung tur yang terbukti optimal menggunakan algoritma Held–Karp, yang diterbitkan secara independen oleh Richard Bellman serta Michael Held & Richard Karp pada tahun 1962. Rekurensi utamanya, di mana C(S, j) adalah jalur terpendek dari simpul 1 ke simpul j yang mengunjungi tepat himpunan bagian S:

Biaya tur optimal adalah min_j [C({1,...,n}, j) + d(j, 1)]. Held–Karp berjalan dalam waktu O(2ⁿ · n²) dan memori O(2ⁿ · n) — peningkatan besar dibandingkan brute force n!, tetapi tetap eksponensial. Melewati sekitar 20 kota, jejak memorinya menjadi tidak praktis.

Nearest-Neighbor + 2-opt (Heuristik)

Untuk instansi yang lebih besar, pemecah menggunakan heuristik dua tahap. Pertama, Nearest-Neighbor membangun tur cepat dengan berjalan secara rakus ke kota terdekat yang belum dikunjungi dari setiap simpul awal. Pemecah mencoba banyak simpul awal dan menyimpan tur terbaik. Kemudian pencarian lokal 2-opt meningkatkan tur dengan menghapus dua tepi secara iteratif dan menyambungkan kembali dua jalur yang dihasilkan dengan satu-satunya cara lain yang memungkinkan:

Secara geometris, 2-opt menghilangkan setiap "persilangan" dalam tur: setiap dua segmen yang bersilangan selalu dapat dilepas persilangannya untuk total panjang yang lebih pendek. Algoritma berhenti pada optimum lokal di mana tidak ada satu pun pertukaran yang membantu, yang disebut tur 2-optimal. Pada instansi Euclidean yang realistis, 2-opt biasanya menemukan tur dalam 2–5% dari optimum yang sebenarnya dalam hitungan milidetik.

Format Masukan

Mode koordinat (x, y)

Satu kota per baris. Setiap baris adalah label, x, y — label bersifat opsional. Pemecah menghitung jarak Euclidean secara otomatis dan memvisualisasikan kota pada posisi sebenarnya.

Mode matriks jarak

Matriks persegi n × n dari jarak non-negatif, satu baris per baris teks, nilai dipisahkan oleh spasi atau koma. Matriks dapat berupa simetris atau asimetris — matriks asimetris memodelkan jalan satu arah, harga penerbangan dengan ketersediaan yang bervariasi, dan perjalanan yang bergantung pada angin. Opsional berikan label di bidang Label matriks.

Perbandingan Algoritma

Cara Menggunakan Pemecah Ini

1. Pilih mode masukan. Koordinat jika kota Anda memiliki posisi (x, y) yang bermakna; Matriks jarak jika biaya Anda non-Euclidean atau asimetris.
2. Tempel atau ketik data Anda. Satu kota atau baris per baris teks. Klik tombol contoh cepat di atas formulir untuk mengisi contoh yang valid secara otomatis.
3. Pilih algoritma. Biarkan pada Otomatis untuk default yang tepat: Held–Karp saat instansi cukup kecil untuk optimalitas yang terbukti, jika tidak gunakan NN + 2-opt. Paksa algoritma tertentu jika Anda ingin membandingkan.
4. Pilih tertutup atau terbuka. Tur tertutup kembali ke awal — TSP tradisional. Mode jalur terbuka menyelesaikan masalah Jalur Hamiltonian terkait di mana penjual berakhir di kota yang berbeda.
5. Klik Selesaikan. Halaman hasil menunjukkan total panjang tur, animasi SVG dari rute (klik "Putar ulang animasi" untuk memutarnya kembali), urutan kota lengkap, rincian per tepi, dan matriks jarak dengan tepi tur yang disorot.

Contoh Pengerjaan

Pertimbangkan lima kota — sebuah persegi panjang ditambah sebuah puncak: A (0, 0), B (4, 0), C (4, 3), D (0, 3), E (2, 5). Pemecah mengembalikan:

• Tur: A → D → E → C → B → A
• Panjang: 3 + √8 + √8 + 3 + 4 ≈ 15.66
• Optimal? Ya — Held–Karp membuktikan tidak ada tur yang lebih pendek.
• Mengapa urutan ini? Rute menelusuri selubung konveks (convex hull) dari kelima titik (A → D → E → C → B → A). Properti klasik dari Euclidean TSP adalah bahwa tur optimal mengunjungi titik-titik pada selubung konveks dalam urutan siklusnya; titik-titik interior terselip di antara tetangga selubung yang berdekatan. Tur apa pun yang memotong jalurnya sendiri, seperti A → C → B → D → E → A (panjang ≈ 21.8), selalu dapat dilepas persilangannya oleh 2-opt untuk hasil yang lebih pendek.

Aplikasi Dunia Nyata

• Logistik & pengiriman — optimalkan rute harian pengemudi di 15 pemberhentian untuk meminimalkan bahan bakar dan waktu.
• Manufaktur — urutkan lubang yang harus dibuat bor CNC pada PCB untuk meminimalkan perjalanan kepala bor.
• Perakitan genom — urutkan fragmen DNA berdasarkan kesamaan tumpang tindih, yang dikodekan sebagai matriks jarak.
• Astronomi — jadwalkan putaran teleskop di antara bintang target untuk memaksimalkan waktu pengamatan.
• Pengambilan barang di gudang — urutkan kunjungan lorong untuk memenuhi pesanan dalam langkah paling sedikit.
• Perencanaan pariwisata — rencanakan perjalanan multi-kota yang meminimalkan waktu tempuh dan biaya tarif.

Pertanyaan yang Sering Diajukan

Apa itu Masalah Penjual Keliling?

Masalah Penjual Keliling (TSP) mencari tur terpendek yang mengunjungi setiap kota tepat satu kali dan kembali ke kota awal. Ini adalah salah satu masalah paling terkenal dalam optimasi kombinatorial dan termasuk NP-hard dalam kasus umum, yang berarti tidak ada algoritma yang diketahui dapat menyelesaikan setiap instansi dalam waktu polinomial.

Apa itu algoritma Held–Karp?

Held–Karp adalah algoritma pemrograman dinamis yang menyelesaikan TSP secara tepat dalam waktu O(2ⁿ · n²) dan memori O(2ⁿ · n). Ini jauh lebih cepat daripada brute force (n faktorial) tetapi tetap eksponensial, sehingga dalam praktiknya hanya digunakan untuk instansi hingga sekitar 20 kota. Pemecah ini menggunakan Held–Karp saat ada 12 kota atau kurang.

Apa itu 2-opt dan mengapa digunakan?

2-opt adalah heuristik pencarian lokal yang berulang kali menghapus dua tepi dari tur saat ini dan menyambungkan kembali dua jalur yang dihasilkan dengan cara lain yang memungkinkan. Ketika tur baru lebih pendek, pertukaran tersebut dipertahankan. 2-opt berjalan dalam waktu polinomial per iterasi dan secara konsisten menemukan tur dalam beberapa persen dari optimal, itulah sebabnya ia menjadi heuristik andalan klasik untuk instansi TSP yang lebih besar.

Kapan saya harus menggunakan koordinat versus matriks jarak?

Gunakan koordinat ketika kota-kota Anda berada di bidang datar dengan jarak garis lurus — misalnya titik di peta, lokasi gudang, atau lubang bor pada papan sirkuit. Gunakan matriks jarak ketika biaya berpasangan bukan Euclidean — misalnya harga tiket pesawat, waktu tempuh dengan lalu lintas, jarak jalan satu arah, atau biaya asimetris. Mode matriks menerima jarak non-negatif apa pun, bahkan yang asimetris.

Apakah solusi 2-opt itu optimal?

Tidak, 2-opt mengembalikan tur 2-optimal, yang berarti tidak ada satu pun pasangan tepi yang dapat ditukar untuk menghasilkan rute yang lebih pendek. Ini adalah optimum lokal dan biasanya dalam beberapa persen dari optimum global pada instansi yang berperilaku baik, tetapi tidak dijamin sebagai yang terbaik secara global. Untuk tur yang terbukti optimal pada instansi kecil, pilih Held–Karp.

Apakah alat ini mendukung matriks jarak asimetris?

Ya. Dalam mode Matriks jarak, Anda dapat memasukkan matriks persegi non-negatif apa pun, termasuk yang asimetris di mana D[i][j] berbeda dari D[j][i]. Held–Karp and 2-opt keduanya menangani matriks asimetris dengan benar. Ini berguna untuk masalah perutean dunia nyata dengan jalan satu arah, lalu lintas, atau biaya penerbangan yang bergantung pada angin.

Bacaan Lebih Lanjut

• Travelling Salesman Problem — Wikipedia
• Held–Karp algorithm — Wikipedia
• 2-opt — Wikipedia
• Nearest-neighbour algorithm — Wikipedia

Operasi matematika tingkat lanjut:

• Kalkulator Antilog
• Kalkulator Fungsi Beta
• Kalkulator Koefisien Binomial
• Kalkulator Distribusi Binomial
• Kalkulator Bitwise
• Kalkulator Teorema Limit Tengah
• Kalkulator Kombinasi
• Kalkulator Fungsi Kesalahan Pelengkap
• Kalkulator Bilangan Kompleks Unggulan
• Kalkulator Entropi
• Kalkulator fungsi kesalahan
• Kalkulator Peluruhan Eksponensial
• Kalkulator Pertumbuhan Eksponensial Presisi Tinggi
• Kalkulator Integral Eksponensial
• Kalkulator Eksponen (Presisi Tinggi)
• Kalkulator Faktorial
• Kalkulator Fungsi Gamma
• Kalkulator Rasio Emas
• Kalkulator Setengah Hidup
• Kalkulator Pertumbuhan Persentase
• Kalkulator Permutasi
• Kalkulator Distribusi Poisson
• Kalkulator Akar Polinomial dengan Langkah-Langkah Terperinci
• Kalkulator Probabilitas
• Kalkulator Distribusi Probabilitas
• Kalkulator Proporsi
• Kalkulator Rumus Kuadrat
• Kalkulator Ilmiah
• Kalkulator Notasi Ilmiah Unggulan
• Kalkulator Angka Penting Baru
• Kalkulator Jumlah Kubik
• Kalkulator Jumlah Angka Berurutan
• Kalkulator Jumlah Kuadrat
• Generator Tabel Kebenaran
• Kalkulator Teori Himpunan
• Generator Diagram Venn (3 Himpunan)
• Kalkulator Teorema Sisa Cina
• Kalkulator Fungsi Totien Euler
• Kalkulator Algoritma Euklides Diperluas
• Kalkulator Invers Multiplikatif Modular
• Kalkulator Pecahan Lanjutan
• Kalkulator Jalur Terpendek Dijkstra
• Kalkulator Pohon Rentang Minimum
• Validator Urutan Derajat Graf
• Kalkulator Derangement Subfaktorial
• Kalkulator Bilangan Stirling
• Kalkulator Prinsip Sarang Merpati
• Kalkulator Distribusi Stasioner Rantai Markov
• Kalkulator Pembulatan Baru
• Kalkulator Distribusi Binomial Negatif Baru
• Kalkulator Permutasi dengan Pengulangan Baru
• Kalkulator Eksponensial Modular Baru
• Kalkulator Akar Primitif
• Penyederhana Aljabar Boolean Baru
• Pemecah Peta Karnaugh (K-Map) Baru
• Kalkulator Pewarnaan Graf Baru
• Kalkulator Pengurutan Topologi Baru
• Kalkulator Matriks Ketetanggaan Baru
• Kalkulator Inklusi-Eksklusi Baru
• Pemecah Pemrograman Linear Baru
• Pemecah Masalah Penjual Keliling (TSP) Baru
• Pemeriksa Jalur Hamilton Baru
• Pemeriksa Grafik Planar Baru
• Kalkulator Aliran Jaringan (Aliran Maksimum) Baru
• Pemecah Masalah Pernikahan Stabil Baru
• Kalkulator Orde Teori Grup Baru
• Kalkulator Ring dan Lapangan Baru