घुमंतू विक्रेता की छिपी संख्या, घेरे में

एआई के उपयोग की घोषणा। “एआई उपयोग के प्रकटीकरण” में लेखक बताते हैं कि उन्होंने शोधपत्र तैयार करने में एआई टूल GPT-5.6 Sol Pro का इस्तेमाल किया, सभी नतीजों की समीक्षा और पुष्टि की, और इसकी सामग्री की पूरी ज़िम्मेदारी लेते हैं। उनका कोड अनुरोध पर उपलब्ध है।

घुमंतू विक्रेता समस्या (ट्रैवलिंग सेल्समैन प्रॉब्लम) ऐसा सबसे छोटा चक्कर पूछती है जो किसी समुच्चय के हर बिंदु पर एक बार जाए और शुरुआत पर लौट आए। अब बिंदुओं को यादृच्छिक बना दें: भुजा 1 वाले वर्ग में n बिंदु समान रूप से फेंकें और पूछें कि सबसे छोटा चक्कर कितना लंबा है।

1959 में बियर्डवुड, हैल्टन और हैमर्सली ने एक चौंकाने वाला उत्तर सिद्ध किया। जैसे-जैसे n बढ़ता है, सबसे अच्छे चक्कर की लंबाई लगभग निश्चित रूप से β√n के बराबर हो जाती है, जहाँ β एक सार्वभौमिक स्थिरांक है — हर यादृच्छिक बिखराव के लिए एक ही। उन्होंने यह भी दिखाया कि 0.625 ≤ β ≤ 0.9212।

पैंसठ से अधिक वर्ष बाद भी β कोई नहीं जानता। इसका कोई सूत्र नहीं है। बड़े कंप्यूटर प्रयोग इसे लगभग 0.7124 पर रखते हैं, लेकिन प्रयोग प्रमाण नहीं होता। अब तक की सबसे अच्छी सिद्ध सीमाएँ थीं 0.6277 ≤ β ≤ 0.90367। ऐसे स्थिरांक लॉजिस्टिक्स में मायने रखते हैं, जहाँ इनका इस्तेमाल डिलीवरी मार्गों की लंबाई का अनुमान बिना गणना किए लगाने के लिए होता है — इसीलिए नया नतीजा टेक्सस विश्वविद्यालय, ऑस्टिन के मैककॉम्ब्स स्कूल ऑफ़ बिज़नेस से आया है, झुओलुन डोंग और जुन्यु काओ की ओर से।

नया दायरा

शोधपत्र सिद्ध करता है:

0.6421 ≤ β ≤ 0.8810

और यादृच्छिक नमूनाकरण की मदद से दिखाता है कि कम से कम 1 − 2 × 10⁻⁴ की प्रायिकता के साथ 0.6536 ≤ β ≤ 0.8749। यह प्रायिकता कंप्यूटर नमूनाकरण की यादृच्छिकता से जुड़ी है, ख़ुद β से नहीं, जो एक निश्चित संख्या है।

नीचे से: लंबी भुजाएँ काटो

यह सिद्ध करने के लिए कि हर चक्कर लंबा होना ही चाहिए, लेखक देखते हैं कि क्या होता है अगर आप किसी चक्कर की उन सभी भुजाओं को हटा दें जो किसी लंबाई r से लंबी हैं। चक्कर पथ के टुकड़ों में टूट जाता है, और हर टुकड़ा ऐसे बिंदुओं के एक गुच्छे के भीतर रहता है जो एक-दूसरे से r के भीतर हैं। किसी गुच्छे को ढकने के लिए जितने ज़्यादा पथ चाहिए, चक्कर में उतनी ही ज़्यादा लंबी भुजाएँ रही होंगी। हर संभव r पर इसे जोड़ने से चक्कर की लंबाई मिलती है:

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

जहाँ N_H(r) उन भुजाओं को गिनता है जो r से लंबी हैं।

अलग-थलग बिंदु और पथ के सिरे पुराना पद 5/8 = 0.625 देते हैं — ठीक 1959 वाली सीमा। नया घटक है 3, 4 और 5 बिंदुओं के छोटे गुच्छों से आने वाले सुधारों की एक शृंखला, जिनमें से हर एक बिंदुओं की संभावित स्थितियों पर एक समाकल है। इन समाकलों की सटीक गणना नहीं हो सकती, इसलिए लेखक उनके क्षेत्रों को नन्हे घनों में काटते हैं और हर घन के लिए निचली सीमा निकालते हैं, हर अपरिमेय संख्या को प्रतिकूल दिशा में पूर्णांकित करते हुए ताकि नतीजा एक वास्तविक सीमा हो:

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

ऊपर से: पाँच-पाँच के खंडों में ज़िगज़ैग

ऊपरी सीमा के लिए बस एक अच्छा चक्कर चाहिए। पारंपरिक नुस्ख़ा वर्ग को क्षैतिज पट्टियों में काटता है और उन्हें ज़िगज़ैग में पार करता है, बाएँ से दाएँ, फिर दाएँ से बाएँ। नया मोड़: हर पट्टी के भीतर बिंदुओं को पाँच-पाँच के खंडों में लिया जाता है, और हर खंड में उसके 24 संभावित क्रमों में से सबसे अच्छे क्रम में जाया जाता है।

एक खंड की अपेक्षित लंबाई एक ग्यारह-आयामी समाकल है — बिंदुओं के बीच पाँच क्षैतिज अंतराल और छह ऊँचाइयाँ। लेखक एक बारीक ग्रिड पर इसकी संख्यात्मक सीमा निकालते हैं, फिर से परिमेय संख्याओं को सुरक्षित दिशा में पूर्णांकित करते हुए, और β < 0.8810 पाते हैं।

बची हुई दूरी

दायरा लगभग 0.28 की चौड़ाई से घटकर लगभग 0.24 रह गया है, लेकिन प्रायोगिक मान 0.7124 अब भी उसके काफ़ी भीतर है। बारीक ग्रिड, एक-दूसरे पर चढ़ी डिस्कों के क्षेत्रफल के और सटीक अनुमान, और लंबे खंड इसे और कस सकते हैं। लेखक लिखते हैं कि बची हुई दूरी को पाटने के लिए “नई तकनीकों की ज़रूरत पड़ सकती है।”