பயண விற்பனையாளரின் மறைந்த எண், மூலைப்படுத்தப்பட்டது

செயற்கை நுண்ணறிவுப் பயன்பாடு அறிவிக்கப்பட்டது. “செயற்கை நுண்ணறிவுப் பயன்பாட்டு வெளிப்படுத்தல்” பகுதியில், ஆய்வுக் கட்டுரையைத் தயாரிப்பதில் GPT-5.6 Sol Pro என்ற செயற்கை நுண்ணறிவுக் கருவியைப் பயன்படுத்தியதாகவும், அனைத்து முடிவுகளையும் மதிப்பாய்வு செய்து சரிபார்த்ததாகவும், அதன் உள்ளடக்கத்துக்கு முழுப் பொறுப்பேற்பதாகவும் ஆசிரியர்கள் கூறுகின்றனர். கேட்டால் அவர்களின் நிரல் குறியீடு கிடைக்கும்.

பயண விற்பனையாளர் சிக்கல் (travelling salesman problem), ஒரு கணத்தின் ஒவ்வொரு புள்ளியையும் ஒருமுறை சென்று தொடக்கத்துக்குத் திரும்பும் மிகக் குறுகிய சுற்றைக் கேட்கிறது. இப்போது புள்ளிகளைச் சீரற்றதாக்குங்கள்: பக்கம் 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 இன்னும் அதற்குள் நன்றாகவே உள்ளது. நுண்ணிய கட்டங்கள், ஒன்றின்மேல் ஒன்று படியும் வட்டுப் பரப்புகளின் கூர்மையான மதிப்பீடுகள், நீண்ட தொகுதிகள் ஆகியவை அதை மேலும் இறுக்கக்கூடும். எஞ்சிய தூரத்தை மூட, ஆசிரியர்கள் எழுதுவதுபோல், “புதிய நுட்பங்கள் தேவைப்படலாம்.”