సంచార విక్రేత దాగిన సంఖ్య, మూలకు నెట్టబడింది

ఏఐ వినియోగం ప్రకటించబడింది. “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 ఇంకా దాని లోపల బాగా లోతుగా ఉంది. మరింత సూక్ష్మ గ్రిడ్‌లు, ఒకదానిపై ఒకటి వచ్చే వృత్తాల వైశాల్యాల పదునైన అంచనాలు, పొడవైన బ్లాకులు దాన్ని మరింత బిగించగలవు. మిగిలిన దూరాన్ని మూసివేయడానికి, రచయితలు రాస్తారు, “కొత్త పద్ధతులు అవసరం కావచ్చు.”