KUPANGA HUKU MALINGANISHO MENGINE YAKIWA YAMEKATAZWA, KARIBU KWA KASI ILEILE
Ili kupanga vitu n kwa mpangilio kwa kuvilinganisha viwili viwili, takriban malinganisho n log n yanahitajika na pia yanatosha. Lakini hilo linadhani kwamba vitu vyovyote viwili vinaweza kulinganishwa.
Mara nyingi haviwezi. Waandishi wanaazima mfano kutoka kwa makala ya 2011: waombaji kadhaa wanaomba kazi ileile, kila mmoja akiwa na wadhamini wake. Waombaji wawili wanaweza kulinganishwa tu ikiwa kuna mdhamini anayewajua wote wawili. Malinganisho yanayoruhusiwa yanaunda mtandao, grafu (graph): kila kitu ni nukta, kila ulinganisho unaoruhusiwa ni kiungo. Mpangilio halisi umefichwa, lakini ni hakika kwamba grafu inaujumuisha, kama njia inayounganisha kila kitu na kinachofuata. Swali ni: inahitaji malinganisho mangapi ili kupata mpangilio huo? Huu ndio upangaji wa jumla (generalized sorting).
Kwa nini mbinu za kawaida zinashindwa
Algorithimu za kawaida zinategemea uhuru wa kuchagua. QuickSort huchagua “mhimili” (pivot) na kuulinganisha na vitu vingine vingi, lakini grafu yoyote ile huenda isiwe na kitu kilichounganishwa na vingine vingi. MergeSort hugawa vitu katika makundi na kupanga kila kundi, lakini huenda kundi lisiweze kupangwa peke yake: vitu viwili vilivyo jirani katika mpangilio wa mwisho si lazima viwe vimeunganishwa ndani yake. Kimsingi zaidi, upangaji wa kawaida daima una ulinganisho unaopatikana ambao huondoa sehemu nzuri ya mipangilio inayowezekana; malinganisho yanapowekewa mipaka, huenda kusiwe na ulinganisho kama huo hata mmoja.
Maendeleo yalikuwa ya polepole. Mwaka 2011, Zhiyi Huang, Sampath Kannan na Sanjeev Khanna walipata mbinu inayotumia takriban malinganisho n¹·⁵, ukiacha vipengele vya logariti (logarithmic factors), na kikomo hicho kimesimama kwa grafu zozote tangu wakati huo. Hata waliuliza kama huenda tatizo hili ni gumu zaidi kimsingi kuliko upangaji wa kawaida, likihitaji n iliyopandishwa kwa kipeo kikubwa kuliko 1.
Tabiri kwanza, rekebisha baadaye
Sanjeev Khanna, wa Chuo Kikuu cha New York, Aaron Putterman, wa Chuo Kikuu cha Harvard, na Junkai Song, pia wa Chuo Kikuu cha New York, sasa wanajibu swali hilo: hapana. Algorithimu yao ya nasibu (randomised) hupanga kwa takriban malinganisho n log⁴ n kwa wastani, kwenye grafu yoyote — vipengele vichache tu vya logariti juu ya upangaji wa kawaida. Na, wanaandika, ni “rahisi kiasi”. Hata hivyo, faida hiyo ni ya kinadharia: viwango visivyobadilika vya uthibitisho ni vikubwa mno (vipengele kama 2³²), kwa hiyo ubora huo unaonekana tu kwa n kubwa sana.
Inajengwa juu ya tokeo linalojulikana: ikiwa mtu atakupa ubashiri wa uelekeo wa kila kiungo, wenye makosa kwenye viungo w kati yake, mpangilio unaweza kupatikana kwa takriban malinganisho n log n + w. Kwa hiyo kazi inakuwa kutoa ubashiri wenye makosa machache kwa kutumia malinganisho machache. Hatua muhimu:
- Ubashiri wa kwanza wa kukadiria. Linganisha sampuli ya nasibu ya jozi zilizounganishwa na uchague mpangilio wowote unaoendana na majibu. Una makosa mengi, lakini si mengi kupita kiasi.
- Tenga makosa, badala ya kuyarekebisha. Badala ya kusahihisha ubashiri usio sahihi, algorithimu hupata sehemu za grafu ambapo makosa ni mengi kuliko wastani na kuziweka kando. Kila mzunguko hugawa makosa yaliyobaki kwa nne, kwa matarajio (in expectation).
- Rudi baadaye. Viungo vilivyowekwa kando vinashughulikiwa katika awamu ya baadaye. Kila awamu hutatua angalau nusu ya viungo ambavyo bado vinasubiri, kwa hiyo takriban awamu ishirini zinatosha kwa viungo milioni moja.
Uthibitisho uliopatikana kwa msaada wa mashine
Tamko la makala kuhusu matumizi ya AI lina maelezo ya kina isivyo kawaida. Linasema kwamba ChatGPT 6-Astra “ilikuwa muhimu kabisa katika kuthibitisha vikomo vilivyoboreshwa”. Modeli moja kwanza ilipata algorithimu inayotumia takriban malinganisho n¹·³³, kisha ikakwama. Waandishi waliifikisha hadi n¹·²; kisha, baada ya kuombwa (prompted) mara makumi kadhaa kwa wiki kadhaa, modeli zilipata maboresho mfululizo — n^(10/9), n^(17/16), n^(19/18) — kabla ya kufikia algorithimu ya karibu-mstari (near-linear). Waandishi wanaongeza kwamba haijulikani wazi kama hatua yao wenyewe ya kati ilikuwa muhimu kwa ugunduzi huo wa mwisho.
Kinachobaki wazi
Tokeo linahesabu malinganisho, si muda wa kukokotoa: kama ilivyoelezwa, algorithimu haifanyi kazi katika muda wa polinomia (polynomial time), ilhali mbinu ya 2011 ilifanya hivyo. Waandishi wanaorodhesha maswali matatu yaliyo wazi: kama vipengele vya logariti vilivyobaki vinaweza kuondolewa, kama algorithimu isiyotumia unasibu inaweza kufanya vizuri vivyo hivyo, na kama algorithimu yenye ufanisi inaweza kufikia idadi ileile ya malinganisho — au hata kushinda n¹·⁵ kabisa.
