Algoritm, mis juhib maailma

Seda algoritmi rakendatakse tuhandeid kordi igas sekundis äritegevuse sujuvuse tagamiseks kogu maailmas — kuid kas matemaatika, millele see toetub, on ikka nii usaldusväärne, kui oleme seni arvanud? Võimalik, et te pole kunagi kuulnudki algoritmist, mis maailma juhib.

Tegelikult on sellest teadlikud üsna vähesed, ehkki see võib mõjutada suurt osa teie igapäevaelust: seda, missugust toitu te sööte, millise graafiku alusel töötate või mis kell rongiga tööle sõidate. Kusagil serverijaamas otsib toosama algoritm praegusel hetkelgi vastust mõnele küsimusele, mis puudutab teie elukäiku homme, järgmisel nädalal või aasta pärast, vahendab New Scientist.

Võib-olla ongi parem selle algoritmi olemusest mitte liiga palju teada. Muistses Ateenas seisis Platoni akadeemia ukse kohal hoiatus: „sissepääs on keelatud kõigile, kes geomeetriat ei mõista“. Toona, mil geomeetria oli veel lahutamatult seotud kolme ruumimõõtmega, mille tajumisega meie ajud hakkama saavad, oli seda lihtne öelda. Meie algoritm toimib aga märksa kõrgematel tasanditel — selle matemaatiliste juhendite jada on konstrueeritud sondeerima kujuteldamatuid ruume, millel on neli, viis, mitu tuhat või isegi miljoneid dimensioone e mõõtmeid.

Võib-olla peaksime siiski veidi rohkem pingutama, et sellest paremini aru saada. Nimelt on too kahtlemata nutikas ja võimas algoritm hakanud viimasel ajal jänni jääma. Selle matemaatilised alused, mille ülesehitus pole küll veel ekslikuks osutunud, on hakanud n-ö servadest murenema. Paistab, et algoritm, millele meie maailmas nii palju toetub, ei pruugigi olla nii usaldusväärne, kui alul arvati.

Probleemi olemuse adumiseks peame esmalt süüvima sellesse, kui põhjalikult ja üllatavalt geomeetrilised abstraktsioonid meid ümbritsevat maailma kirjeldavad. Arusaam taolistest seostest ulatub ajaloos tagasi vähemalt Platonini, kes valis välja viis ruumilist geomeetrilist keha e hulktahukat, mille täiuslik korrapära tema arust kosmose olemust edasi andis. Nelitahukas e tetraeeder, kuup, kaheksatahukas e oktaeeder ja 20-tahuline ikosaeeder kehastasid „elemente“ — tuld, maad, õhku ja vett —, tosinatahulist dodekaeedrit pidas Platon aga universumi kuju täiuslikuks peegelduseks.

Sellest ajast peale on üht-teist muutunud. Tänapäevased füüsikateooriad käsitlevad tihtipeale Platonile tundmatuid, kummaliselt väändunud geomeetriaid, või võtavad eelduseks rohkem kui kolme hoomatava ruumimõõtme olemasolu. Ka matemaatikud on pürginud üha uutesse dimensioonidesse, laiendades hulktahukate ideed mõistust vaaruma panevate „polütoopideni“, millel on neli, viis või rohkem mõõdet.

Esiletõstmist väärib siinkohal hulktahukate reegel, mille 1957. aastal sõnastas USA matemaatik Warren Hirsch. Tema väitis, et suurim mõeldav arv servi, mida mööda tuleb suvalise hulktahuka kahe tipu vahelise vahemaa läbimiseks liikuda, pole kunagi suurem kui selle tahkude arv, millest on lahutatud ülesande mõõtmete arv, antud juhul kolm. Näiteks eraldavad kuuetahulise kuubi vastastippe täpselt kolm serva ning ühegi tipupaari vahele ei jää vähem kui kolm serva. 

Hirschi reegel kehtib kõigi kolmemõõtmeliste hulktahukate juures, kuid selle paikapidavust rohkemamõõtmeliste kehade kohta üldiselt pole kunagi tõestatud. Eeldus, et see peaks siiski võimalik olema, toetub suuresti analoogiale muude, samavõrd pandlikeks osutunud geomeetriliste reeglitega. Nelja-, viie- või tuhandemõõtmeliste kehade pinnapunktide vaheliste lühimate marsruutide leidmisel on Hirschi reegel jäänud tänini üheks matemaatikateadust kummitavatest lahendamata mõistatustest — pelgalt oletuslikuks hüpoteesiks (ingl conjecture).

Kuidas see asjasse puutub? Nimelt sel moel, et nüüdismatemaatikute jaoks pole dimensioonid mitte ainult ruumi küsimus. Tõsi, kontseptsioon tõstatus, kuna kasutame asupaiga tähistamiseks kolme koordinaati, mida saab üksteisest sõltumatult varieerida: üles-alla-, paremale-vasakule- ja edasi-tagasi-telgesid. Lisame sellele aja ning saame neljanda „mõõtme“, mis toimib väga sarnaselt, kui välja arvata seletamatu tõik, et me saame sellel liikuda ainult ühes suunas.

Peale liikumise kohtame me aga tegelikus maailmas sageli olukordi, kus on üksteisest sõltumatult võimalik varieerida palju rohkem kui nelja tegurit. Oletame näiteks, et te valmistate lõunaeineks võileiba. Teie külmikus leidub kümme komponenti, mille koguseid saate ise määrata; juust, chutney-kaste, tuunikala, tomatid, muna, või, sinep, majonees, lehtsalat ja seesami-kikerhernepasta e hummus. Need koostisained ongi võileivavalmistamise ülesande dimensioonideks. Ülesandele saab läheneda geomeetriliselt: kui kombineerite koostisosad ükskõik millisel konkreetsel viisil, kujutab valmis einevõileib endast konkreetset lahenduspunkti kümnemõõtmelises ruumis.

Päratud ülesanded

Meie liikumine selles mitmemõõtmelises ruumis ei pruugi olla täiesti piiramatu. Võib-olla on külmkapis vaid kaks hallitavat juustukildu või majoneesipurgis napp teelusikatäis põhjakaabet. Meie isiklikud eelistused võivad võileiva valmistamise ülesandele lisada täiendavaid, peenemaid piiranguid, nagu näiteks kalorivaese dieedi järgimine või vastumeelsus segada kokku tuunikala ja hummust. Igaüks neist piirangutest kujutab endast piiri meie multimõõtmelises ruumis, millest edasi liikuda pole võimalik. Sisuliselt loovad meie ressursid ja isiklikud eelistused mitmedimensioonilise polütoobi, mille piires me täiusliku võileiva poole püüeldes navigeerima peame.

Tegelikkuses kujunevad võileivameisterdamisega seotud otsustusprotsessid tõenäoliselt mõnevõrra juhuslikeks, kuid kuna analüüsitavate tegurite koguhulk on väike ning kaalukeelel pole midagi peale kõhumõnude, pole sellest suurt lugu. Äri, riigivalitsemise ja teadusuuringute valdkonnas kerkivad aga kõikjal esile samasugused optimeerimisülesanded, mis kiiresti kasvavad päratuteks, tuhandete või isegi miljonite tegurite ja piirangutega konglomeraatmõistatusteks. Näiteks võib eksootiliste puuviljade maaletoojal olla tarvis lahendada tuhandemõõtmeline ülesanne: kuidas toimetada banaanid kõige väiksema vaevaga viiest eri mahtuvusega laost 200 eri nõudlusega kauplusse, ehk teisisõnu, mitu banaani tuleks transportida millisest laost millisesse poodi nii, et kulutused transpordile jääksid minimaalseks.

Samamoodi võib finantshaldur soovida koostada aktsiaportfelli moel, mis kõige tõhusamalt riske tasakaalustaks ja laia valiku osakute pealt ootuspärast tulu teeniks; raudteeliiklusgraafiku koostajat võib huvitada personali ja veeremi kõige optimaalsem töölerakendamine ning tehase või haigla direktorit küsimus, kuidas piiratud masinaressursse või voodikohti kõige tõhusamalt ära kasutada. Iga seesugust ülesannet saab kujutada geomeetrilise kujundina, mille mõõtmete e dimensioonide arv on võrdne ülesandes sisalduvate muutujate arvuga ja mille piirjooned märgivad maha konkreetses olukorras kehtivad piirangud. Igal juhul jääb meie ülesandeks leida taolise polütoobi sees kõige optimaalsem lahenduspunkt. Ja see ongi antud algoritmi töö.

Algoritmi täispikk nimetus on simpleksalgoritm (ingl simplex algorithm) ning sellele pani 1940. aastatel aluse USA matemaatik George Dantzig, kelle ülesandeks teise maailmasõja ajal oli leida võimalikke viise USA õhujõudude logistilise tõhususe tõstmiseks. Dantzig oli teerajajaks valdkonnas, mida ta nimetas lineaarprogrammeerimiseks ja mis rakendab multidimensionaalsete polütoopide matemaatikat optimeerimisülesannete lahendamiseks. Üks tema esimestest avastustest oli, et „sihtfunktsiooni“ — selle asja, mida tahame maksimumini suurendada või miinimumini kahandada, olgu selleks siis kasum, teekonna läbimise aeg või miski muu — optimaalne väärtus peab paiknema ühes polütoobi tippudest. See teeb kogu küsimuse hoobilt lihtsamaks: igas polütoobis on lõputu hulk punkte, kuid alati lõplik hulk tippe.

Kui mängus on vaid mõned muutuvad dimensioonid ja piirangud, pole rohkem teada tarviski. Me saame järgida marsruute mööda polütoobi servi, kontrollides funktsiooni sihtväärtust igas tipus, kuni leiame optimaalsuspunkti. Mida rohkem lisandub aga muutujaid, seda kiiremini lähevad asjad keerulisemaks. Isegi vaid kümnemõõtmeline ülesanne 50 piiranguga — näiteks töögraafiku koostamine kümnele eri oskuste ja isiklike ajapiirangutega inimesele — võib nõuda mitme miljardi tipu läbiproovimist.

Simpleksalgoritm leiab läbipääsu kiiremini. Polütoobi servi pidi juhusliku uitamise asemel rakendab see igas tipus „pöördereeglit“ (ingl pivot rule). Algoritmi eri rakenduste puhul tulevad mängu pöördereegli peenelt erinevad variatsioonid, kuid enamasti tähendab see taolise serva valimist, mida mööda liikudes sihtfunktsioon kõige järsemalt langema hakkab, garanteerides nii, et iga samm viib meid optimaalsele väärtusele lähemale. Kui leitakse tipp, kust edasi laskuda pole võimalik, teame, et olemegi jõudnud optimaalse väärtuseni.

Praktiline kogemus näitab, et reeglina on simpleksmeetod ülesannete lahendamisel tõeliselt tõhus, jõudes enamasti optimaalse lahenduseni pärast sellist hulka pöördeid, mis on võrreldav ülesande dimensioonide hulgaga. See tähendab, et 50-mõõtmelise ülesande lahendamiseks pole tõenäoliselt vaja rohkem kui paarsada sammu, mitte miljardeid, mida eeldaks variantide ükshaaval läbiproovimise meetod. Taoline lahendamiskiirus, mida nimetatakse polünoomseks ja tähistatakse enamasti lihtsalt P-ga, on tegelikus maailmas lõplikul hulgal protsessoritel jooksvate praktiliste algoritmide etaloniks.

Dantzigi algoritm jõudis esimest korda kommertsrakendusse 1952. aastal, mil Abraham Charnes ja William Cooper Pennsylvania osariigis Pittsburghis tegutsevast uurimisasutusest, mis tänapäeval Carnegie Melloni ülikooli nime kannab, koostöös kütusekontserni Gulf Oil Company esindaja Robert Melloniga avastasid meetodi, kuidas segada neljast eri petrooleumitootest kokku kõige optimaalsema oktaanisisaldusega lennukikütus.

Sellest ajast alates on simpleksalgoritm järjekindlalt maailma vallutanud, tungides kõikjale ärilistest optimeerimispakettidest tellija spetsifikatsioonidele vastavate tarkvaratoodeteni. Iga kord, kui keegi üritab lahendada mastaapsemat sorti optimeerimisülesannet, ragistab mõni arvutikiip kusagil väga tõenäoliselt simpleksalgoritmi rütmis soovitud väärtust otsida. „Simpleksmeetodit rakendatakse arvatavasti kümneid või sadu tuhandeid kordi igas minutis,“ usub Ühendkuningriigi Edinburgh’ ülikooli optimeerimisspetsialist Jacek Gondzio.

Kuid samaaegselt algoritmi populaarsuse jätkuva kasvuga 1950. ja 1960. aastatel hakkas selle aluskude ilmutama mõningaid läbikulumise märke. Esiteks on selle lahendamiskiirus polünoomne ainult keskeltläbi. 1972. aastal rõhutasid USA matemaatikud Victor Klee ja George Minty seda tõika, lastes algoritmi „kallale“ mõnedele geniaalselt deformeeritud mitmemõõtmelistele „hüperkuupidele“ (ingl hypercube). Samamoodi nagu ruudul on neli ja kuubil kaheksa tippu, on n-mõõtmelisel hüperkuubil kaks-astmel-n tippu. Klee ja Minty hüperkuupide taotluslikult „vildakas“ konstruktsioon tähendas, et simpleksalgoritm peab enne optimaalsesse punkti leidmist kõik need tipud ükshaaval „läbi käima“. Juba ainuüksi 41 dimensiooni juures tähendab see, et algoritm peab „liikuma“ mööda rohkem kui triljonit serva.

Sama kehtib algoritmi pöördereegli kõigi variatsioonide kohta, mida pärast Dantzigi algupärast konstruktsiooni läbi on proovitud: paistab, et hoolimata sellest, kui hästi algoritm ülesannete lahendamisega keskeltläbi hakkama saab, on alati võimalik konstrueerida mõni kohmakas optimeerimisülesanne, mille lahendamisega algoritm jänni jääb. Hea uudis on, et praktiliste rakenduste juures taoliseid patoloogilisi juhtumeid üldiselt ei esine — ehkki seni pole päris selge, miks see nii peaks olema. „Taoline käitumine ei mahu ühegi jäiga matemaatilise selgituse piiresse, kuid teeb kahtlemata heameelt praktikutele,“ märgib Gondzio.

Sädelevate alternatiivide plussid ja miinused

Viga oli siiski piisavalt suur, ajendamaks uurijaid simpleksmeetodile alternatiive otsima. Peamine troonipretendent kerkis esile 1970. ja 1980. aastatel pärast „sisepunktimeetodite“ (ingl interior point method) avastamist. Tegemist oli uhkete ja paljutõotavate algoritmidega, mis polütoobi pinnavormidel liikumise asemel „puurivad“ raja otse selle tuumani. Sisepunktimeetodil töötavate algoritmidega kaasnes matemaatiline garantii, et simpleksmeetodiga võrreldes kulub neil optimaalsuspunkti leidmiseks vähem astmeid ning et ülesande dimensioonide arvust hoolimata kulub selleks harva üle saja sammu.

Avastus põhjustas palju elevust ja mõnda aega paistis, et Dantzigi algoritmi praktiliste rakenduste päevad on peagi loetud. Ometi on see jäänud püsima ja isegi oma mõjusfääri laiendanud. Sisepunktimeetodite häda on selles, et iga samm nõuab märksa rohkem arvutamist kui üks simpleksalgoritmi pöördepunkt; sihtfunktsiooni võrdlemise asemel väikese hulga servamarsruutidega tuleb analüüsida kõiki võimalikke suundi polütoobi sees, mis on tohutult mahukas ettevõtmine. Selline kompromiss on vastuvõetav mõnede röögatusuurte tööstuslike ülesannete lahendamise juures, aga kaugeltki mitte igas olukorras. Gondzio hinnangul lahendatakse 80–90 protsenti nüüdisaegsetest optimeerimisülesannetest jätkuvalt mõne simpleksalgoritmi variandi abil. Sama kehtib paraja portsu veelgi keerulisemate mittelineaarsete ülesannete kohta. „Ehkki olen pühendunud sisepunktimeetodite uurimisele, suhtun simpleksmeetodisse vägagi aupaklikult,“ rõhutab Gondzio. „Annan endast parima, üritades pakkuda võrdväärset konkurentsi.“

Aga ikkagi oleks äärmiselt tore leida midagi paremat — mõni simpleksalgoritmi variatsioon, millel on säilinud kõik selle plussid, kuid mis leiab igal juhul lahenduse polünoomse kiirusega. USA matemaatik ja Fieldsi medali laureaat Steve Smale kirjutas 1998. aastal, et „tugevalt polünoomse“ algoritmi leidmine on üheks kaheksateistkümnest silmapaistvast matemaatilisest küsimusest, millele 21. sajand peab vastuse leidma.

Ent võib-olla pole sellise algoritmi leidmine enam isegi võimalik.

Miks nii? Sest sellise täiendatud, eksimatu algoritmi olemasolu sõltub ühest märksa fundamentaalsemast geomeetrilisest eeldusest: et piisavalt lühike otsetee kahe tipu vahel ümber polütoobi pinna on tegelikult olemas. Tuleb tuttav ette? Kes tabas ära, et see tähendabki eelpoolmainitud Hirschi hüpoteesi, võib end siinkohal õnnitleda.

Võimalik, et hüpoteesi ja algoritmi saatused jäävad aegade lõpuni omavahel seotuks. Hirsch ise oli operatsiooniliste uuringute pioneer ja algusaegadel ka Dantzigi töökaaslane. Oma hüpoteesi formuleeriski Hirch esmalt Dantzigile 1957. aastal saadetud kirjas, milles ta mõlgutas mõtteid algoritmi tõhususe piiride üle.

Kuni päris viimase ajani polnud eriti miski seda kahtluse alla seadnud. Klee tõestas juba 1966. aastal, et hüpotees kehtib kõigile kolmemõõtmelistele hulktahukatele, kuid aimas, et sama ei pruugi paika pidada rohkemamõõtmeliste polütoopide juures. Vanemas eas oli tal tavaks sööta probleem ette igale äsja ülikooli lõpetanud „rohelisele“ uurijale, keda ta kohtama juhtus. 2001. aastal võttis üks neist, praegu Santanderis Cantabria ülikoolis töötav noor hispaanlane Francisco Santos väljakutse vastu.

Nagu seesuguste mõistatuste puhul tavaks, võttis lahendamine palju aega. Peaaegu kümme aastat ülesande kallal pead murdnud Santose tulemused said esitlusvalmis Seattle’is 2010. aastal toimunud konverentsi ajaks. Möödunud kuul ilmus samasisuline uurimus ajakirjas Annals of Mathematics. Selles kirjeldab Santos 86 tahuga 43-mõõtmelist polütoopi. Hirschi hüpoteesi kohaselt peaks kõige pikem marsruut mööda taolise keha pinda võtma 86 miinus 43 sammu, s.t kokku 43 sammu. Santos suutis aga vastuvaidlematult näidata, et tema kirjeldatud keha sisaldab vähemalt üht paari tippe, mida lahutavad teineteisest 44 sammu.

Nii oli Hirschi hüpoteesi paikapidavus vähemalt ühel spetsiifilisel juhul kummutatud. „See lahendas küsimuse, millele me ei osanud aastakümneid vastust otsima hakatagi,“ nendib Jeruusalemma Heebrea ülikooli akadeemik Gil Kalai. „Tõestus ise on väga sügav, keeruline ja ülimalt elegantne. Tegu on suurepärase tulemusega.“

Tulemus võib tõesti olla suurepärane, kuid ei ennusta kindlasti midagi head simpleksalgoritmile. Pärast Santose esimest kummutust on Hirschi hüpoteesi trotsivaid polütoope avastatud isegi kuni 20-mõõtmeliste kehade hulgast. Ainus teadaolev piirang polütoobi pinna kahe punkti vahelise lühima vahemaa leidmisele sisaldub nüüd matemaatilises avaldises, mille Kalai ja Massachusettsi tehnoloogiainstituudi uurija Daniel Kleitman tuletasid 1992. aastal. Piirang on aga palju ulatuslikum sellest, mida võinuks pakkuda Hirschi hüpotees juhul, kui see tõeseks oleks osutunud. Tegelikult on piirang simpleksmeetodil mõistliku lahenduskiiruse tagamiseks kaugelt liiga suur sõltumata sellest, kui nutikaid pöördereegleid me välja nuputada suudame. Kui see on parim, milleks me võimelised oleme, võib juhtuda, et Smale’i paleus — ideaalne algoritm — jääb igaveseks väljapoole meie haardeulatust. Sellel võivad aga optimiseerimise tulevikule olla väga tõsised tagajärjed.

Kõik pole siiski kadunud. Kui nn polünoomne Hirschi hüpotees (ingl polynomial Hirsch conjecture) paika peab, võib enneolematult tõhusa simpleksalgoritmi loomine siiski võimalik olla. See võib Kalai-Kleitmani piirangut oluliselt kitsendada, garanteerides, et ühelgi polütoobil ei saa esineda radu, mis oleksid nende mõõtmete ja tahkude arvuga võrreldes ebaproportsionaalselt pikad. Pärast Santose avaldust ja Hirschi hüpoteesi normaalvariandi põrmustumist on viimase polünoomne versioon pakkunud väga suurt huvi nii neile, kellele meeldivad sügavad geomeetrilised mõistatused, kui paljulubavat lähtepunkti neile, kes kütivad optimaalselt tõhusat optimeerimisprotseduuri.

Seni puuduvad märgid, mis viitaksid kindlalt võimalusele, et polünoomne hüpotees on üldse tõestatav. „Mina pole selles sugugi kindel,“ möönab Kalai. Mitte, et see teda heidutaks: „Selle probleemi juures on kõige põnevam asjaolu, et me ei tea vastust.“

Vastusest võib aga sõltuda vägagi palju. Sedamööda, kuidas algoritm serverijaamades üha oma tööd teha ragistab ja enamasti ütleb meile, mida me teada tahame, aja jooksul, mil me seda teada tahame, on selle edasine saatus praegu rohkem kui kunagi varem matemaatikute kätes.