Pemecah Masalah Penjual Keliling (TSP)

Temukan rute terpendek yang mengunjungi tiap kota sekali dan kembali ke titik awal. Menggunakan Held-Karp eksak untuk instance kecil dan nearest-neighbour dengan 2-opt untuk yang lebih besar, dari koordinat atau matriks jarak.

Gratis digunakanTidak perlu mendaftarHasil instan

Pemecah Masalah Penjual Keliling (TSP)Coba sekarang — gratis ▼

Contoh cepat:

5-kota persegi+puncak 8 kota acak 8 ibu kota UE Matriks 4×4 Benchmark 10-kota Segitiga (jalur terbuka)

⌖ Koordinat (x, y) ▦ Matriks jarak

Kota atau matriks

Baris koordinat: A, 10, 20 atau 10 20. Baris matriks: 0 10 15 20 — satu baris per baris teks, persegi, non-negatif. Maks 40 kota.

Label matriks (opsional)

Label dipisahkan koma atau spasi, satu per baris matriks. Default ke A, B, C… jika dikosongkan.

Algoritma

Jenis tur

Embed Pemecah Masalah Penjual Keliling (TSP) Widget

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:

minimalkan Σ_i=1^n-1 d(π(i), π(i+1)) + d(π(n), π(1))

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:

C(S, j) = min_{k ∈ S \ {j}} [ C(S \ {j}, k) + d(k, j) ]

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:

Sebelum: ... a — b ... c — d ... Setelah pertukaran 2-opt: ... a — c ... b — d ... Jika d(a,c) + d(b,d) < d(a,b) + d(c,d) → terima pertukaran, balikkan subtur b..c

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.

A, 10, 20 B, 40, 70 C, 75, 30 Paris: 2.35, 48.86 10 20 ← label otomatis C1

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.

0 10 15 20 10 0 35 25 15 35 0 30 20 25 30 0

Perbandingan Algoritma

Algoritma	Kompleksitas waktu	Memori	Kualitas hasil	Ukuran praktis
Brute force	O(n!)	O(n)	Optimal	n ≤ 10
Held–Karp DP	O(2ⁿ · n²)	O(2ⁿ · n)	Optimal	n ≤ 20
Nearest-Neighbor	O(n²)	O(n)	~25% lebih buruk dari optimal	n ≤ ribuan
NN + 2-opt	O(n² · lintasan)	O(n)	~2–5% lebih buruk dari optimal	n ≤ ratusan

Cara Menggunakan Pemecah Ini

Pilih mode masukan. Koordinat jika kota Anda memiliki posisi (x, y) yang bermakna; Matriks jarak jika biaya Anda non-Euclidean atau asimetris.
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.
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.
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.
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

Kutip konten, halaman, atau alat ini sebagai:

"Pemecah Masalah Penjual Keliling (TSP)" di https://MiniWebtool.com/id/pemecah-masalah-penjual-keliling-tsp/ dari MiniWebtool, https://MiniWebtool.com/

oleh tim miniwebtool. Diperbarui: 21 Apr 2026

Anda juga dapat mencoba Penyelesai Matematika AI GPT kami untuk menyelesaikan masalah matematika Anda melalui pertanyaan dan jawaban dalam bahasa alami.