KIZUIZI CHA 1962 KATIKA SAYANSI YA KOMPYUTA CHAANGUKA

Mzunguko wa Hamilton (Hamiltonian cycle) ni safari ya kwenda na kurudi katika mtandao inayotembelea kila kituo mara moja hasa na kurudi mahali pa kuanzia. Katika mtandao wenye mwelekeo (directed), kila kiungo ni mshale unaoweza kufuatwa upande mmoja tu, kama barabara ya njia moja. Toleo lenye uzito la tatizo hili ni tatizo la mchuuzi msafiri lisilo na ulinganifu (asymmetric travelling salesman problem).

Kuamua kama mzunguko kama huo upo ni tatizo gumu la vitabu vya kiada. Mnamo 1962, Richard Bellman na, kwa kujitegemea, Michael Held na Richard Karp walitoa algoriti za upangaji wenye mabadiliko (dynamic programming) zinazolitatua kwa muda wa takriban 2ⁿ kwa mtandao wa vituo n (bila kuhesabu vipengele vinavyokua kwa kasi ya polinomia tu). Kwa zaidi ya miaka sitini, hakuna aliyeweza kufanya vizuri zaidi kimsingi kwa mitandao ya jumla yenye mwelekeo.

Binamu asiye na mwelekeo alikuwa ameshaanguka

Kwa mitandao yenye viungo vya pande mbili, Andreas Björklund alivunja kizuizi hicho mwaka 2014 kwa algoriti ya kubahatisha inayoendeshwa kwa 1.657ⁿ, kazi iliyomletea Tuzo ya Nerode ya EATCS–IPEC ya 2016, kwa mujibu wa makala. Bado ndiyo algoriti ya kasi zaidi inayojulikana kwa mitandao ya jumla isiyo na mwelekeo. Kwa ile yenye mwelekeo, maendeleo yalikuja tu kwa hali maalum — mitandao ya pande mbili (bipartite), mitandao yenye viungo vichache kwa kila kituo — au chini ya dhana isiyothibitishwa, dhana ya Strassen ya cheo cha kiasimptoti (asymptotic rank conjecture).

Kikomo kipya

Tomohiro Koana, wa Chuo Kikuu cha Tokyo, na Soh Kumabe, wa kampuni ya CyberAgent ya Tokyo, sasa wanatoa algoriti ya kubahatisha inayoamua tatizo lenye mwelekeo kwa muda wa

O((375/196)ⁿ) = O(1.9133ⁿ)**.

Kwa mitandao ya jumla yenye mwelekeo, ni maboresho ya kwanza katika msingi wa kipeo tangu 1962.

Kuhesabu kwa witiri na shufwa

Ugumu ni wa kina. Kuhesabu mizunguko kwa moduli 2 — kujua tu kama idadi yake ni witiri au shufwa — tayari kuliwezekana chini ya 2ⁿ. Lakini idadi shufwa isiyo sifuri ya mizunguko inaonekana sawasawa kabisa na sifuri. Suluhisho la kawaida ni kuvipa viungo uzito wa kubahatisha ili, kwenye jumla fulani ya uzito, suluhisho liwe moja tu (lema ya utengaji, isolation lemma); lakini mbinu ya haraka ya kuhesabu witiri na shufwa haikuweza kushughulikia uzito.

Mapishi ya waandishi, kwa maneno rahisi:

1. Kisia mshale mmoja wa mzunguko, na badala yake tafuta njia inayopita kila kituo kutoka ncha moja ya mshale huo hadi nyingine.
2. Futa kila mshale kwa kubahatisha kwa uwezekano wa 1/50.
3. Katika kila kituo, unda makundi matatu ya mishale inayoingia, na nakili kila mshale uliobaki katika seti ya kubahatisha isiyo tupu ya makundi.
4. Ikiwa safari ipo, basi kwa uwezekano wa angalau (49/50)ⁿ⁻¹ mtu anaweza kuchagua kundi moja kwa kila kituo ili idadi ya njia halali iwe witiri.
5. Ipe kila kundi — si kila mshale — uzito wa kubahatisha. Sasa mbinu ya utengaji inafanya kazi, na marudio takriban (50/49)ⁿ yanatosha.
6. Kila rudio hukokotoa hesabu za witiri au shufwa kwa kila jumla ya uzito kwa muda wa (15/8)ⁿ, kwa kutumia jumla za viambajengo (determinants) vya matriki za Björklund, Kaski na Koutis na “ulinearishaji” wa kubahatisha uliotumiwa pia na Arvind na Guruswami.

Zidisha viwili hivyo: (50/49)ⁿ × (15/8)ⁿ = (375/196)ⁿ ≈ 1.9133ⁿ.

Uthibitisho uliozalishwa na mashine

Makala inamalizia kwa tamko kuhusu AI zalishi: ChatGPT 6 Astra ilizalisha uthibitisho wa nadharia kuu na kusaidia kuandaa rasimu ya mswada. Waandishi walitoa kauli za mapendekezo ya kati, ambazo zinatoa usomaji wa kimchanganyiko (combinatorial) wa suluhisho la awali la modeli, kisha wakahakiki na kurekebisha kila kitu na wanabeba jukumu kamili.

Matokeo haya ni ya kinadharia — hakuna programu iliyoendeshwa — na algoriti ni ya kubahatisha, yenye uwezekano mdogo wa kukosea upande wowote. Kati ya 1.9133 kwa barabara za njia moja na 1.657 kwa za pande mbili, pengo pana bado liko wazi.