Latar Belakang
Masalah salesman keliling (TSP) meminta sirkuit terpendek yang mengunjungi kumpulan kota tertentu. Untuk keperluan pertanyaan ini, kota-kota akan menjadi titik di pesawat dan jarak di antara mereka akan menjadi jarak Euclidean biasa (dibulatkan ke bilangan bulat terdekat). Sirkuit harus "pulang pergi", artinya harus kembali ke kota awal.
The Concorde TSP solver dapat memecahkan contoh masalah salesman keliling Euclidean, persis dan jauh lebih cepat dari yang diharapkan. Sebagai contoh, Concorde mampu memecahkan instance 85.900 poin persis, bagian yang terlihat seperti ini:
Namun, beberapa instance TSP terlalu lama, bahkan untuk Concorde. Misalnya, tidak ada yang bisa menyelesaikan contoh 100.000 poin ini berdasarkan Mona Lisa . (Ada hadiah $ 1.000 yang ditawarkan jika Anda bisa menyelesaikannya!)
Concorde tersedia untuk diunduh sebagai kode sumber atau yang dapat dieksekusi. Secara default, ia menggunakan built-in linear program (LP) solver QSopt , tetapi juga dapat menggunakan solver LP yang lebih baik seperti CPLEX.
Tantangan
Apa contoh TSP terkecil yang dapat Anda hasilkan yang membutuhkan waktu lebih dari lima menit untuk menyelesaikan Concorde ?
Anda dapat menulis program untuk menampilkan instance, atau menggunakan metode lain yang Anda inginkan.
Mencetak gol
Semakin sedikit poin dalam contoh semakin baik. Dasi akan dipecah berdasarkan ukuran file instance (lihat di bawah).
Standardisasi
Komputer yang berbeda berjalan lebih cepat atau lebih lambat, jadi kami akan menggunakan Server NEOS untuk Concorde sebagai standar pengukuran untuk runtime. Anda dapat mengirimkan daftar poin dalam formulir koordinat 2-d sederhana berikut:
#cities
x_0 y_0
x_1 y_1
.
.
.
x_n-1 y_n-1
Pengaturan yang harus digunakan pada NEOS adalah "data Concorde (file xy-list, norma L2)", "Algoritma: Concorde (QSopt)", dan "Benih acak: diperbaiki".
Baseline
Mesin virtual 1.889-point rl1889.tsp
dari TSPLIB membutuhkan "Total Running Time: 871.18 (detik)", yang lebih dari lima menit. Ini terlihat seperti ini:
Jawaban:
88 Kota, 341 detik runtime di NEOS
Dalam sebuah makalah baru-baru ini kami membangun sebuah keluarga yang sulit untuk memecahkan contoh TSP euclidean. Anda dapat mengunduh instance dari keluarga ini serta kode untuk membuatnya di sini:
http://www.or.uni-bonn.de/%7Ehougardy/HardTSPInstances.html
Contoh 88 kota dari keluarga ini membawa Concorde di server NEOS lebih dari 5 menit. Contoh 178 kota dari keluarga ini sudah lebih dari sehari diselesaikan.
sumber
77 kota, 7,24 menit (434,4 detik) waktu berjalan rata-rata di NEOS
Saya sedikit terlambat ke pesta, tetapi saya ingin berkontribusi contoh 77-node, weruSnowflake77.
Saya membuat contoh ini ketika mencoba untuk memahami karakteristik lokal dan global mana yang memberikan tekanan ke atas pada jumlah waktu yang diperlukan untuk mencocokkan dengan batas bawah terbaiknya dengan lamanya tur yang paling pendek ditemukan.
Untuk membangun contoh ini, saya mulai dengan grafik dasar (13 x 13 persegi), dan kemudian secara sistematis memperkenalkan poin baru atau menerjemahkan poin lama, mempertahankan penyesuaian yang tampaknya membuat kerukunan masuk lebih dalam ke cabang-cabangnya secara rata-rata sebelum memotong.
Teknik ini mirip dengan cara algoritma genetika memutasikan tur yang ada dan mempertahankan tur yang lebih pendek untuk generasi mutasi berikutnya, kecuali grafik itu sendiri dimutasi dan grafik yang lebih sulit dipecahkan dipertahankan. Ini juga mirip dengan cara kita memutasi grafik menggunakan relaksasi untuk membantu membangun batas bawah yang baik, kecuali aku akan sebaliknya, mengubah grafik yang ada untuk membangun grafik dengan sulit untuk menemukan batas bawah.
Dalam prosesnya saya telah menemukan beberapa grafik yang lebih kecil yang membutuhkan waktu beberapa menit untuk menyelesaikannya, tetapi ini adalah grafik kecil pertama yang saya temukan yang membutuhkan persetujuan minimum 5 menit.
Dengan 10 percobaan berjalan pada NEOS menggunakan seed tetap dan QSopt, runtime rata-rata adalah 7,24 menit (434,531 detik). Runtime minimum adalah 5,6 menit (336,64 detik). Runtime maksimum adalah 8,6 menit (515,80 detik). Tidak ada uji coba yang dibuang. Tabel benchmark lengkap di bawah ini:
Hasil benchmark lebih dari 10 kali berjalan:
weruSnowflake77 (daftar xy, norma L2):
Gudang
Masalah mengatur file dari repo:
sumber
Python 3, 911 kota, waktu menjalankan 1418 detik di NEOS
Skrip Python 3.x berikut ini menghasilkan koordinat 911 kota. Butuh NEOS 1418 detik untuk menghitung jalur terpendek 47739.
Ini adalah gambar jalan terpendek bagimu (terima kasih kepada A. Rex):
Kode / algoritma didasarkan pada bifurkasi Feigenbaum , yang saya gunakan untuk menghasilkan serangkaian nilai, yang saya gunakan sebagai dasar untuk menghasilkan koordinat kota-kota. Saya bereksperimen dengan parameter sampai saya menemukan sejumlah kota di bawah 1000 yang membutuhkan NEOS jumlah waktu yang mengejutkan (jauh di atas 5 menit yang diperlukan).
PS: Saya memiliki skrip yang sedang berjalan untuk mencari sejumlah kota yang lebih rendah yang juga memerlukan> 5 menit pada NEOS. Saya akan mempostingnya di jawaban ini jika saya menemukannya.
PS: Sial! Menjalankan skrip ini dengan l parameter 1811 alih-alih 1.301 menghasilkan di 1156 kota dengan waktu berjalan di NEOS lebih dari 4 jam , yang jauh lebih banyak daripada kasus lain dengan parameter serupa ...
sumber