Panjang rute
Terpendek yang ditemukan
Jumlah langkah
Rute yang mungkin
  • Rute
  • Terpendek yang ditemukan
  • Awal

Metode Panjang Di atas terpendek Jumlah langkah
- - -
- - -
- - -
- - -
- - -

Selengkapnya tentang masalah pedagang keliling

Masalah pedagang keliling

Seorang pedagang harus mengunjungi setiap kota satu kali lalu kembali ke rumah. Urutan mana yang membuat perjalanannya paling pendek? Pertanyaannya mudah diajukan, tetapi seiring bertambahnya jumlah kota, mustahil dijawab dengan mencoba setiap urutan: 30 kota saja sudah memungkinkan sekitar 4,4 × 10³⁰ rute keliling. Sebarkan kota di peta atau klik untuk menempatkan kota Anda sendiri, lalu saksikan aturan praktis yang cepat, perbaikan yang cerdik, dan satu metode eksak menyusun rutenya langkah demi langkah, dan lihat seberapa dekat metode cepat bisa mendekati hasil terbaik. Pilih bagaimana kota-kota ditata dan berapa jumlahnya, pilih metode, lalu tekan Selesaikan untuk melihatnya menyusun rute keliling langkah demi langkah, atau Langkah untuk maju satu gerakan setiap kali. Klik peta untuk menambah kota, atau klik sebuah kota untuk menghapusnya. Bandingkan semua menjalankan setiap metode pada kota-kota yang sama dan menunjukkan seberapa jauh masing-masing dari rute terpendek yang ditemukan. Kota merah adalah titik awal perjalanan.

Cara kerjanya

  1. Pilih tata letak dan jumlah kota, atau klik peta untuk menempatkan kota sendiri dan klik sebuah kota untuk menghapusnya.
  2. Pilih metode lalu tekan Selesaikan untuk melihatnya langkah demi langkah, atau Langkah untuk maju satu gerakan setiap kali.
  3. Tekan Bandingkan semua untuk menjalankan setiap metode pada kota-kota yang sama dan lihat seberapa jauh setiap rute di atas rute terpendek yang ditemukan.

Mengapa sulit

Dengan n kota terdapat (n − 1)! / 2 rute keliling yang berbeda, karena tidak penting dari mana Anda mulai atau ke arah mana Anda berkeliling. Itu berarti 12 untuk 5 kota, 181.440 untuk 10 kota, dan sekitar 6 × 10¹⁶ untuk 20 kota. Belum diketahui metode yang dapat menemukan rute terpendek untuk setiap peta dalam waktu yang hanya tumbuh seperti suatu pangkat dari n; masalah ini bersifat NP-hard. Metode eksak terbaik dalam aplikasi ini, pemrograman dinamis Held–Karp dari tahun 1962, tetap membutuhkan sekitar n² · 2ⁿ langkah, sehingga di sini dibatasi hingga 12 kota.

Rute bagus dengan cepat

Dalam praktiknya, rute yang hampir terpendek dapat ditemukan dengan cepat. Tetangga terdekat selalu menuju kota terdekat yang belum dikunjungi dan biasanya berakhir sekitar 25% di atas rute terbaik. Penyisipan termurah menumbuhkan sebuah putaran dan menambahkan kota mana pun yang paling sedikit memperpanjangnya. 2-opt mengambil rute apa saja dan terus mengganti dua sisi dengan dua sisi yang lebih pendek, sehingga setiap persilangan hilang dan biasanya selisihnya hanya sekitar 5%. Simulated annealing melakukan gerakan 2-opt secara acak dan, selama masih “panas”, menerima beberapa gerakan yang membuat rute lebih panjang, sehingga dapat keluar dari jalan buntu sebelum akhirnya mapan.

Pertanyaan yang sering diajukan

Apakah ada rumus untuk rute terpendek?

Tidak. Rute terpendek bergantung pada posisi tepat semua kota, dan belum diketahui metode yang dapat menemukannya untuk setiap peta tanpa, dalam kasus terburuk, jumlah pekerjaan yang tumbuh secara eksponensial. Untuk beberapa ratus atau ribu kota, pemecah eksak khusus seperti Concorde tetap dapat membuktikan rute optimal dengan menggabungkan pemrograman linear dan pemangkasan yang cerdik, dan contoh terbesar yang sejauh ini terpecahkan secara eksak memiliki 85.900 titik.

Mengapa 2-opt menghilangkan setiap persilangan?

Jika dua sisi sebuah rute bersilangan, empat kota yang dihubungkannya membentuk segi empat yang diagonalnya adalah kedua sisi tersebut. Menukar keduanya dengan dua sisi berhadapan dari segi empat itu selalu lebih pendek, menurut ketaksamaan segitiga, dan membalik bagian rute di antaranya. 2-opt terus melakukan pertukaran seperti itu hingga tidak ada lagi yang membantu, sehingga rute akhirnya tidak pernah memotong dirinya sendiri.

Apa itu suhu dalam simulated annealing?

Suhu mengatur seberapa bersedia metode ini menerima gerakan yang membuat rute lebih panjang. Gerakan yang menambah panjang sebesar d diterima dengan peluang e^(−d/T). Pada suhu T yang tinggi hampir semua gerakan diterima, sehingga rute bisa lolos dari susunan yang buruk; ketika T turun, metode ini menjadi serakah dan mapan. Namanya berasal dari pendinginan logam secara perlahan agar atom-atomnya menemukan susunan berenergi rendah.

Mengapa metode eksak dibatasi hingga 12 kota?

Held–Karp menyimpan jalur terpendek untuk setiap subhimpunan kota dan setiap kemungkinan kota terakhir, yaitu sekitar n · 2ⁿ bilangan, dan mengisi masing-masing dengan n perbandingan. Untuk 12 kota itu berarti beberapa ratus ribu langkah; untuk 25 kota akan menjadi miliaran. Meski begitu, cara ini jauh lebih cepat daripada mencoba semua (n − 1)! / 2 rute: untuk 12 kota jumlahnya hampir 20 juta.

Apakah ada yang dikirim ke server?

Tidak. Kota-kota dan kelima metode berjalan di browser Anda. Kota yang Anda tambahkan dengan klik tetap tersimpan di penyimpanan lokal browser ini.

Siap mencobanya?

Buka PictorX di browser Anda — tanpa instalasi, tanpa kartu kredit untuk memulai.

Ke Editor