फिरत्या विक्रेत्याची दडलेली संख्या, कोंडीत पकडली

एआय वापर जाहीर. “Disclosure of AI Use” (एआय वापराचा खुलासा) मध्ये लेखक नमूद करतात की शोधनिबंध तयार करताना त्यांनी GPT-5.6 Sol Pro हे एआय साधन वापरले, सर्व निकालांचा आढावा घेऊन ते पडताळले, आणि त्याच्या आशयाची संपूर्ण जबाबदारी ते घेतात. त्यांचा कोड विनंतीनुसार उपलब्ध आहे.

फिरत्या विक्रेत्याचा प्रश्न (travelling salesman problem) अशा सर्वात लहान फेऱ्याचा शोध घेतो, जो संचातील प्रत्येक बिंदूला एकदा भेट देऊन सुरुवातीच्या ठिकाणी परत येतो. आता बिंदू यादृच्छिक करा: बाजू 1 असलेल्या चौरसात n बिंदू एकसमानपणे फेका आणि विचारा की सर्वात लहान फेरा किती लांब आहे.

1959 मध्ये बिअर्डवुड, हॉल्टन आणि हॅमर्सली यांनी एक थक्क करणारे उत्तर सिद्ध केले. n वाढत जातो तसतशी सर्वोत्तम फेऱ्याची लांबी जवळजवळ निश्चितपणे β√n इतकी होते, जिथे β हा एक वैश्विक स्थिरांक आहे — प्रत्येक यादृच्छिक विखुरण्यासाठी तोच. त्यांनी हेही दाखवले की 0.625 ≤ β ≤ 0.9212.

पासष्टहून अधिक वर्षांनंतरही β कोणालाच माहीत नाही. कोणतेही सूत्र नाही. मोठे संगणकीय प्रयोग तो सुमारे 0.7124 दाखवतात, पण प्रयोग म्हणजे पुरावा नव्हे. आतापर्यंत सिद्ध झालेल्या सर्वोत्तम मर्यादा 0.6277 ≤ β ≤ 0.90367 होत्या. असे स्थिरांक लॉजिस्टिक्समध्ये महत्त्वाचे आहेत, जिथे वितरण-मार्गांची लांबी प्रत्यक्ष न मोजता अंदाजण्यासाठी ते वापरले जातात — म्हणूनच हा नवीन निकाल ऑस्टिनमधील युनिव्हर्सिटी ऑफ टेक्सासच्या मॅककॉम्ब्स स्कूल ऑफ बिझनेसमधून, झुओलुन डाँग (Zhuolun Dong) आणि जुन्यू काओ (Junyu Cao) यांच्याकडून आला आहे.

नवीन कंस

शोधनिबंध सिद्ध करतो:

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 अजूनही त्याच्या खूप आत आहे. अधिक बारीक जाळ्या, एकमेकांवर येणाऱ्या वर्तुळांच्या क्षेत्रफळांचे अधिक धारदार अंदाज आणि अधिक लांब गट यांमुळे तो आणखी आवळता येईल. उरलेले अंतर मिटवण्यासाठी, लेखक लिहितात, “नवीन तंत्रांची आवश्यकता भासू शकते.”