GEZGİN SATICININ GİZLİ SAYISI KISKACA ALINDI

Yapay zekâ kullanımı beyan edildi. Yazarlar bir “Yapay Zekâ Kullanımının Açıklanması” bölümünde, makaleyi hazırlarken GPT-5.6 Sol Pro adlı yapay zekâ aracını kullandıklarını, tüm sonuçları incelediklerini ve doğruladıklarını ve içeriğin tüm sorumluluğunu üstlendiklerini belirtiyor. Kodları talep üzerine sağlanıyor.

Gezgin satıcı problemi, bir kümedeki her noktayı bir kez ziyaret edip başlangıca dönen en kısa turu arar. Şimdi noktaları rastgele yapın: kenarı 1 olan bir kareye düzgün dağılımla n nokta atın ve en kısa turun ne kadar uzun olduğunu sorun.

1959’da Beardwood, Halton ve Hammersley çarpıcı bir yanıt kanıtladı. n büyüdükçe en iyi turun uzunluğu neredeyse kesin olarak β√n’ye eşit hale gelir; burada β evrensel bir sabittir — her rastgele serpiştirme için aynı. Ayrıca 0,625 ≤ β ≤ 0,9212 olduğunu gösterdiler.

Altmış beş yılı aşkın bir süre sonra, β’yı kimse bilmiyor. Bir formülü yok. Büyük bilgisayar deneyleri onu yaklaşık 0,7124 olarak buluyor, ama bir deney kanıt değildir. Şimdiye kadar kanıtlanmış en iyi sınırlar 0,6277 ≤ β ≤ 0,90367 idi. Bu tür sabitler, teslimat rotalarının uzunluğunu hesaplamadan tahmin etmek için kullanıldıkları lojistikte önemlidir — yeni sonucun Austin’deki Texas Üniversitesi’nin McCombs İşletme Okulu’ndan, Zhuolun Dong ve Junyu Cao’dan gelmesinin nedeni de bu.

Yeni aralık

Makale şunu kanıtlıyor:

0,6421 ≤ β ≤ 0,8810

ve rastgele örnekleme kullanarak, en az 1 − 2 × 10⁻⁴ olasılıkla 0,6536 ≤ β ≤ 0,8749 olduğunu gösteriyor. Bu olasılık, sabit bir sayı olan β’nın kendisiyle değil, bilgisayar örneklemesinin rastgeleliğiyle ilgili.

Aşağıdan: uzun kenarları kes

Her turun uzun olması gerektiğini kanıtlamak için yazarlar, bir turun belli bir r uzunluğundan uzun tüm kenarlarını silerseniz ne olduğuna bakıyor. Tur yol parçalarına bölünüyor ve her parça, birbirine r’den yakın noktalardan oluşan bir küme içinde kalıyor. Bir kümenin kapsanması için ne kadar çok yol gerekiyorsa, turun o kadar çok uzun kenarı olmuş olmalı. Bunu olası her r üzerinden toplamak tur uzunluğunu verir:

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

burada N_H(r), r’den uzun kenarları sayar.

Yalıtılmış noktalar ve yol uçları eski 5/8 = 0,625 terimini veriyor — tam olarak 1959 sınırı. Yeni bileşen, 3, 4 ve 5 noktalık küçük kümelerden gelen bir dizi düzeltme; her biri noktaların olası konumları üzerinden bir integral. Bu integraller tam olarak hesaplanamıyor; bu yüzden yazarlar tanım bölgelerini minik küplere bölüyor ve her küpü aşağıdan sınırlıyor; sonucun gerçek bir sınır olması için her irrasyonel sayı aleyhte yöne yuvarlanıyor:

β ≥ 0.625 + 0.01113528859 + 0.005040573276 + 0.001015487669 > 0.6421.

Yukarıdan: beşli bloklar halinde zikzak

Bir üst sınır için yalnızca tek bir iyi tur yeterli. Klasik tarif kareyi yatay şeritlere böler ve bunları zikzak halinde tarar: soldan sağa, sonra sağdan sola. Yeni dokunuş: her şeridin içinde noktalar beşli bloklar halinde alınıyor ve her blok, 24 olası sırasının en iyisiyle ziyaret ediliyor.

Bir bloğun beklenen uzunluğu on bir boyutlu bir integral — noktalar arasındaki beş yatay aralık ve altı yükseklik. Yazarlar onu ince bir ızgara üzerinde sayısal olarak sınırlıyor, yine rasyonel sayılar güvenli yöne yuvarlanarak, ve β < 0,8810 sonucunu elde ediyor.

Kalan boşluk

Aralık yaklaşık 0,28 genişlikten yaklaşık 0,24’e daraldı, ama deneysel değer 0,7124 hâlâ rahatça içinde duruyor. Daha ince ızgaralar, örtüşen disk alanlarının daha keskin tahminleri ve daha uzun bloklar onu daha da daraltabilir. Kalan mesafeyi kapatmak, diye yazıyor yazarlar, “yeni teknikler gerektirebilir.”