BILANGAN TERSEMBUNYI SANG PENJUAL KELILING, TERSUDUTKAN

Penggunaan AI dinyatakan. Dalam “Pernyataan Penggunaan AI”, para penulis menyatakan bahwa mereka menggunakan alat AI GPT-5.6 Sol Pro dalam menyiapkan makalah, bahwa mereka meninjau dan memverifikasi semua hasil, dan bahwa mereka bertanggung jawab penuh atas isinya. Kode mereka tersedia atas permintaan.

Masalah penjual keliling (travelling salesman problem) mencari rute terpendek yang mengunjungi setiap titik dalam suatu himpunan tepat satu kali lalu kembali ke titik awal. Sekarang buat titik-titiknya acak: lemparkan n titik secara seragam ke dalam persegi bersisi 1, lalu tanyakan berapa panjang rute terpendeknya.

Pada 1959, Beardwood, Halton, dan Hammersley membuktikan jawaban yang mencengangkan. Seiring n membesar, panjang rute terbaik hampir pasti menjadi sama dengan β√n, dengan β sebagai konstanta universal — sama untuk setiap sebaran acak. Mereka juga menunjukkan bahwa 0,625 ≤ β ≤ 0,9212.

Lebih dari enam puluh lima tahun kemudian, tak ada yang tahu nilai β. Tidak ada rumusnya. Eksperimen komputer berskala besar menempatkannya di sekitar 0,7124, tetapi eksperimen bukanlah bukti. Hingga kini, batas terbaik yang terbukti adalah 0,6277 ≤ β ≤ 0,90367. Konstanta semacam ini penting dalam logistik, tempat konstanta itu digunakan untuk memperkirakan panjang rute pengiriman tanpa menghitungnya — itulah sebabnya hasil baru ini datang dari McCombs School of Business di University of Texas at Austin, oleh Zhuolun Dong dan Junyu Cao.

Rentang baru

Makalah ini membuktikan:

0,6421 ≤ β ≤ 0,8810

dan, dengan pengambilan sampel acak, menunjukkan bahwa 0,6536 ≤ β ≤ 0,8749 dengan peluang sekurang-kurangnya 1 − 2 × 10⁻⁴. Peluang itu menyangkut keacakan pengambilan sampel komputer, bukan β itu sendiri, yang merupakan bilangan tetap.

Dari bawah: potong sisi-sisi yang panjang

Untuk membuktikan bahwa setiap rute pasti panjang, para penulis melihat apa yang terjadi jika kita menghapus semua sisi rute yang lebih panjang dari suatu panjang r. Rute itu terpecah menjadi potongan-potongan jalur, dan setiap potongan tetap berada di dalam satu gugus titik yang saling berjarak kurang dari r. Makin banyak jalur yang dibutuhkan untuk menutup suatu gugus, makin banyak sisi panjang yang mestinya dimiliki rute itu. Menjumlahkan hal ini untuk setiap nilai r yang mungkin menghasilkan panjang rute:

ℓ(H) = ∫₀^∞ N_H(r) dr,

dengan N_H(r) menghitung sisi-sisi yang lebih panjang dari r.

Titik-titik terisolasi dan ujung-ujung jalur memberikan suku lama 5/8 = 0,625 — persis batas tahun 1959. Bahan barunya adalah serangkaian koreksi dari gugus kecil berisi 3, 4, dan 5 titik, masing-masing berupa integral atas posisi-posisi titik yang mungkin. Integral ini tidak dapat dihitung secara eksak, sehingga para penulis memotong domainnya menjadi kubus-kubus mungil dan membatasi setiap kubus dari bawah, dengan setiap bilangan irasional dibulatkan ke arah yang tidak menguntungkan agar hasilnya benar-benar merupakan batas:

β ≥ 0,625 + 0,01113528859 + 0,005040573276 + 0,001015487669 > 0,6421.

Dari atas: zig-zag dalam blok berisi lima

Batas atas hanya membutuhkan satu rute yang baik. Resep klasiknya memotong persegi menjadi jalur-jalur horizontal dan menyapunya secara zig-zag, dari kiri ke kanan, lalu dari kanan ke kiri. Sentuhan barunya: di dalam setiap jalur, titik-titik diambil dalam blok berisi lima, dan setiap blok dikunjungi dalam urutan terbaik dari 24 kemungkinan urutannya.

Panjang harapan sebuah blok adalah integral sebelas dimensi — lima jarak horizontal antartitik dan enam ketinggian. Para penulis membatasinya secara numerik pada kisi halus, sekali lagi dengan bilangan rasional yang dibulatkan ke arah aman, dan memperoleh β < 0,8810.

Celah yang tersisa

Rentang itu telah menyempit dari lebar sekitar 0,28 menjadi sekitar 0,24, tetapi nilai empiris 0,7124 masih berada jauh di dalamnya. Kisi yang lebih halus, perkiraan yang lebih tajam atas luas cakram yang saling tumpang tindih, dan blok yang lebih panjang dapat mempersempitnya lebih jauh. Menutup jarak yang tersisa, tulis para penulis, “mungkin memerlukan teknik-teknik baru.”