NAMBA ILIYOFICHIKA YA MCHURUZI ANAYESAFIRI, IMEBANWA KONA

Matumizi ya AI yametangazwa. Katika “Disclosure of AI Use” (Ufichuzi wa Matumizi ya AI), waandishi wanaeleza kwamba walitumia zana ya AI GPT-5.6 Sol Pro katika kuandaa makala, kwamba walipitia na kuthibitisha matokeo yote, na kwamba wanachukua jukumu kamili kwa maudhui yake. Msimbo wao unapatikana kwa ombi.

Tatizo la mchuruzi anayesafiri (travelling salesman problem) linauliza safari fupi zaidi inayotembelea kila nukta ya seti mara moja na kurudi mwanzoni. Sasa zifanye nukta kuwa za nasibu: tupa nukta n kwa usawa ndani ya mraba wenye upande wa 1 na uliza safari fupi zaidi ina urefu gani.

Mwaka 1959, Beardwood, Halton na Hammersley walithibitisha jibu la kushangaza. Kadiri n inavyokua, urefu wa safari bora karibu hakika unakuwa sawa na β√n, ambapo β ni kisawa cha ulimwengu wote — kilekile kwa kila mtawanyiko wa nasibu. Walionyesha pia kwamba 0.625 ≤ β ≤ 0.9212.

Zaidi ya miaka sitini na mitano baadaye, hakuna anayeijua β. Hakuna fomula. Majaribio makubwa ya kompyuta yanaiweka karibu 0.7124, lakini jaribio si uthibitisho. Hadi sasa, mipaka bora iliyothibitishwa ilikuwa 0.6277 ≤ β ≤ 0.90367. Visawa kama hivi vina umuhimu katika usafirishaji, ambapo hutumika kukadiria urefu wa njia za usambazaji bila kuzihesabu — ndiyo sababu tokeo jipya linatoka Shule ya Biashara ya McCombs ya Chuo Kikuu cha Texas huko Austin, kwa Zhuolun Dong na Junyu Cao.

Mabano mapya

Makala inathibitisha:

0.6421 ≤ β ≤ 0.8810

na, kwa kutumia sampuli za nasibu, inaonyesha kwamba 0.6536 ≤ β ≤ 0.8749 kwa uwezekano wa angalau 1 − 2 × 10⁻⁴. Uwezekano huo unahusu unasibu wa sampuli za kompyuta, si β yenyewe, ambayo ni namba isiyobadilika.

Kutoka chini: kata pande ndefu

Ili kuthibitisha kwamba kila safari lazima iwe ndefu, waandishi wanaangalia kinachotokea ukiondoa pande zote za safari zilizo ndefu kuliko urefu fulani r. Safari huvunjika kuwa vipande vya njia, na kila kipande hubaki ndani ya kundi la nukta zilizo ndani ya r kutoka moja hadi nyingine. Kadiri kundi linavyohitaji njia nyingi zaidi ili kufunikwa, ndivyo safari ilivyopaswa kuwa na pande ndefu zaidi. Kujumlisha hili kwa kila r inayowezekana kunatoa urefu wa safari:

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

ambapo N_H(r) huhesabu pande zilizo ndefu kuliko r.

Nukta zilizojitenga na ncha za njia zinatoa kipengele cha zamani 5/8 = 0.625 — sawasawa na mpaka wa 1959. Kiungo kipya ni mfululizo wa marekebisho kutoka makundi madogo ya nukta 3, 4 na 5, kila moja likiwa kiunganishi juu ya mahali panapowezekana pa nukta hizo. Viunganishi hivi haviwezi kuhesabiwa kwa usahihi kamili, hivyo waandishi wanakatakata maeneo yake kuwa mchemraba midogo sana na kuweka mpaka wa chini kwa kila mchemraba, huku kila namba isiyowiana ikikadiriwa kuelekea upande usiofaa ili tokeo liwe mpaka halisi:

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

Kutoka juu: zigizaga kwa vitalu vya tano

Mpaka wa juu unahitaji safari moja nzuri tu. Mbinu ya kawaida hukata mraba katika vipande vya mlalo na kuvipitia kwa zigizaga, kushoto kwenda kulia, kisha kulia kwenda kushoto. Ubunifu mpya: ndani ya kila kipande, nukta huchukuliwa katika vitalu vya tano, na kila kitalu hutembelewa kwa mpangilio bora kati ya mipangilio yake 24 inayowezekana.

Urefu unaotarajiwa wa kitalu ni kiunganishi cha vipimo kumi na moja — nafasi tano za mlalo kati ya nukta na vimo sita. Waandishi wanakiwekea mpaka kwa kinamba kwenye gridi laini, tena kwa namba wiani zilizokadiriwa kuelekea upande salama, na wanapata β < 0.8810.

Pengo lililobaki

Mabano yamepungua kutoka upana wa takriban 0.28 hadi takriban 0.24, lakini thamani ya kimajaribio 0.7124 bado iko ndani kabisa. Gridi laini zaidi, makadirio makali zaidi ya maeneo ya diski zinazopishana na vitalu virefu zaidi vingeweza kuibana zaidi. Kufunga umbali uliobaki, waandishi wanaandika, “huenda kukahitaji mbinu mpya.”