Joulupukki kauppamatkaan jo käy!

Joulupukki kiertää yhdessä päivässä kaikki lapsiperheet. Tämä on aika tiivistä toimintaa, ja siksi Suomessa - jossa ollaan lähellä Joulupukin asumusta - lahjat tulevat siten että joulupukki tavataan. Sen sijaan USA:ssa joulupukki käy yömyöhällä. Tämä on selvä logistinen ongelma josta on syntynyt ilmiö.

Olen melko varma että Joulupukki on kuitenkin ratkaissut ns. kauppamatkustajan ongelman. Ja ennen kuin ihmettelette että onko loogista että taruolento ratkaisee ratkaisemattoman matemaattisen ongelman, muistutan että joulupukki on ratkaissut spesifin ongelman jossa on äärellinen määrä pisteitä, eli lapsiperheiden sijainti. (Lopuksi hän menee kotiin josta on lähtenytkin joten kauppamatkustajan ongelman "kierrosajattelu" on järkevää.)

Kuinka paljon joulupukilla on laskentatehoa kun hän on voinut laskea ratkaisun käyden läpi kaikki mahdolliset kombinaatiot?

---

Maailmassa on noin 7 miljardia ihmistä, joten ainakin 1 miljardi perhettä. Reittihän on määritelmällisesti sellainen että kahdessa paikassa ei käydä samanaikaisesti. Ensin on n vaihtoehtoa ja kun se on valittu, on jäljellä n-1 paikkaa, sitten n-2... Tälläiselle on olemassa konsepti nimeltä kertoma. Kertoman eri määritelmät
n ! = ∏ k = 1 n k ln ⁡ ( a . b )  = ln ⁡ ( a ) + ln ⁡ ( b ) → ln ⁡ ( n ! )  = ln ⁡ ( ∏ k = 1 n k )  = ∑ k = 1 n ( ln ⁡ n ) Tässä tapauksessa n=1000 000 000. Luku on liian suuri normaaleille taskulaskimille. (Se on on likimain 6.53x10^977.) Tuloksissa on päällekkäisyyksiä ; Monet keskenään samanlaiset reitit näyttävät eri tuloksilta. Ja toisaalta sama reitti voidaan käydä takaperin ja se on silti yhtä pitkä tai lyhyt. Näiden eliminoinnin jälkeen kauppamatkustajan ongelman lukumäärä, kunhan n>2 on [(n-1)!]/2 (Joka on yleiskaava kauppamatkustajan ongelman reittivaihtoehdoille.) Tällä saadaan suuruusarvio. (10^9-1)!/2 "Tieteellisen" analyysin lopputulos ; Joulupukin tietokone on vähintään yhtä vakuuttava kuin lepakkoluolan batcomputer.

Maksa vai laskentateho?

Iltalehdessä kerrottiin siitä miten matemaatikot ovat laskeneet lyhimmän reitin jolla voi kiertää kaikki Britannian pubit siten että päätyy alkupisteeseensä. (Olen itsekin kokeillut niistä muutamaa.) Toisin sanoen tässä ratkaistiin kauppamatkustajan ongelmaa 24 727 pisteen kautta. (Klassinen kauppamatkustajan ongelma on usein kuvattu ja esitetty 50 kohdalla ja jo tämä on ollut ei-tietokoneajalla hirvittävän kova ja vaikea ongelma ratkottavaksi.)

Kauppamatkustajan ongelma on siitä erikoinen ongelma, että jos haetaan aivan parasta mahdollista ratkaisua, joudutaan käymään aivan kaikki vaihtoehdot läpi. Toki likiarvoja voidaan lähestyä nopeastikin. On useita kikkoja. (Olen itse esimerkiksi tehnyt brute force -evoluutioalgoritmin joka parantaa tuloksia aluksi nopeammin kuin mitä pelkkä sattuma sanoisi..) Näitä approksimaatioalgoritmeja on toki kuvattu hienostuneemmin kuin pikku ohjelmia kyhäillen, esimerkiksi Aaro Tuomiston gradussa "Kauppamatkustajan ongelman approksimointialgoritmin suunnittelu, toteutus ja kokeellinen tutkimus".

Näissä haetaan kuitenkin hyvää tulosta - jopa hämmentävän tehokkaasti, ainakin itseäni hämmästyttää aina miten nopeasti eri tarjolla olevat algoritmit lyhentävät reittiä, ne tekevät sen niin paljon paremmin kuin oma kyhäelmäni - ei sitä aivan kaikista reiteistä lyhintä. Tätä ratkaisua hakiessa aletaan puhumaan hyvin hämmentävistä ja syvistä matemaattisista ongelmista kuten P = NP? -ongelmasta jonka ratkaisemisesta on luvattu rahakas matematiikan palkinto. Clay Mathematics Institute antaa miljoona dollaria ensimmäiselle joka ratkaisee N=NP? -ongelman. Tämä tarkoittaa sitä että kenties teoriassa olisi mahdollista että ongelman aivan paras kierros voitaisiin ratkaista muuten kuin laskemalla jokainen reitti ja katsomalla mikä niistä on lyhin,  mutta me emme sellaista vielä tunne. Koska jos onnistuu ratkaisemaan miten kauppamatkustajan ongelman parhaan tuloksen voi vain suoraan laskea, on väkisin keksinyt keinon joka ratkaisee tämän kuuluisan haasteen. (Oma intuitioni on että tämänlaista ratkaisua ei ole. Mutta minun intuitioni ei ole jostain syystä.)

Baarikierros on tärkeä tieto. Matemaatikkojen mukaan baarikierrokseen menisi kolmisen vuotta. 24727 paikkaa jossa nautittavan oluen määrä on arvioitavissa itse kunkin preferenssien mukaan tuottaa sitten hintaa koskevia arvokkaita estimointeja jotka ovat matemaattisesti hyvin helppoja. Selvää on, että kauppamatkustajan elämäntapaan sopiva aihevalinta on vähintään yhtä kova haaste kauppamatkustajan maksalle kuin mitä ongelman ratkaisu on ollut matemaatikkojen tietokoneiden laskentateholle. Lovi lompakollekin on messevä, sellaisen loven täyttämiseksi olisi tietenkin miellyttävää keksiä rahakkaita matemaattisia vastauksia. Tosin tässä vaiheessa motiivina voi olla lopettaa kauppamatkustajana toimiminen ja jättää kaikenmaailman tälläiseen usein heikosti palkkaa tuottavaan työhön liittyvät ongelmat taakseen. Sitten sitä voisi vain heittäytyä lepäämään laakereillaan ja lähteä baarikierrokselle.

Pieni maailma - Kuuden ketju.

Nykyisin verkostoja on joka paikassa. On internettiä ja verkostomarkkinointia. Luonnossa ei ole niinkään ravintoketjuja, kuin monimutkaisempaa kiertoa kun "energia virtaa systeemin läpi mutta aineet kiertävät", ja puhutaankin ravintoverkoista. Yritykset ovat toisiensa kanssa tekemisissä, ja ihmisetkin. Kenties tämän vuoksi matemaattista graafiteoriaa on käytetty apuna kun on haluttu selvittää yhteisöjen toimintaa ja jopa ennustaa ihmisen kollektiivista toimintaa.

Verkostojen tutkimus alkoi 1700 luvulla, kun matemaatikko Leonhard Euler ratkaisi Köningsbergin siltaongelman, jossa tavoitteena oli löytää reitti joka kulkee jokaisen sillan kautta kerran, mutta ei koskaan käytä samaa siltaa kahdesti. (Euler valitettavasti osoitti että tälläistä reittiä ei ole. Et siis voi kunnioittaa hänen saavutusta juoksentelemalla silloilla.) Kuitenkin valtaosa aiheeseen liittyvästä matematiikasta tehtiin vasta 1900 -luvun puolivälissä kun Paul Erdős ja Alfred Renyi kehittelivät abstrakteimpia verkkoja käsittelevää matematiikkaa jossa käsitellään solmuja eli noodeja (yleensä piirretty piste) joita on yhdistetty linkeillä (viivoilla), joista syntyy erilaisia verkkoja joissa on sallitut yhteydet. Tämä lopullinen kuva on graafi:
1: Tämä ei ole mikään ihme, koska verkostojen laskeminen jossa on paljon solmuja sisältää valtavasti laskentaa. Esimerkkitapauksena tälläisestä voisi sanoa ns. kauppamatkustajan ongelmaa, jossa pitää etsiä reitti joka alkaa ja päättyy samaan pisteeseen, käy tietyn monen kaupungin läpi ja on lyhin reitti joka tekee tämän. Sen ratkaiseminen on eräänlainen lyhimmän ketjun metsästys, joka on laskennallisesti erittäin työläs. Sille ei ole helppoja ratkaisuja, ratkaisu saadaan kun kokeillaan kaikki mahdolliset reitit ja katsotaan sitten mikä niistä oli lyhin. Tietenkin suuri osa verkostolaskuista ei ole näin monimutkaisia. Mutta se kuitenkin kertoo osaltaan siitä, miten hankalia ratkottavia asioita verkostoihin liittyvät asiat ovat.

Kenties kuuluisin verkostoihin liittyvä näkemys on ns. "six degrees of separation" tai "kuuden ketju". Sen mukaan kuka tahansa tällä planeetalla on yhteydessä kehen tahansa toiseen ihmiseen ketjulla joka on korkeintaan 5 askelta pitkä. Ajatuksen kehitti vuonna 1929 Frigyes Karinthy, ja se oli osana novellia nimeltä "Chains."
1: Tälläisten verkostojen pituuden tutkimiseen on toki panostettu jonkin verran kaunokirjallisuutta syvemmin: Stanley Milgram teki postilaatikkokokeen, jossa Nebraskassa asuvia ihmisiä kehotettiin lähettämään paketti tutuilleen. Paketti piti sitten postittaa eteenpäin, mutta tässä oli mukana myös peli: Tavoitteena oli saada paketti tietylle postimeklarille. Kaikki paketit saapuivat perille korkeintaan viidellä postituksella.
2: Lisäksi maailmassa esiintyvien, konkreettisten verkostojen, tutkimiseen on oman erikoisen osansa antanut näyttelijä Kevin Bacon -fanittaminen ; Syynä on se, että hän oli osana monessa elokuvassa 1990 -luvulla. Eräät pennsylvanialaiset opiskelijat keksivätkin eräänlaisen leikin, jossa oli tavoitteena yhdistää joku näyttelijä Kevin Baconiin mahdollisimman lyhyellä tavalla. Tämä kasvoi ja siitä kehittyi tutkimusohjelma, jolla on olemassa nettisivutkin. Käytännössä voi sanoa että lähes kaikki elokuvanäyttelijät voidaan liittää toisiin elokuvanäyttelijöihin verkoston kautta. Syynä on se, että he kaikki eivät ole näytelleet vain vakioporukan kanssa, vaihtamatta elokuvassa mukana olevaa näyttelijäkaartia lainkaan. Kun näin ei tehdä, syntyy esimerkiksi sellainen kytkös, että Penelope Cruz yhdistyy Baconiin Tom Cruisen kautta, vaikka ei ole suoraan näytellytkään hänen kanssaan.

Konkreettinen ja matemaattinen yhdistettiin, kun Duncan Watts ja Steven Strogatz saivat Natureen läpi jutun "Dynamics of 'Small World' Networks". Esimerkiksi Tom Siegfried pitää tätä artikkelia lähtölaukauksena vakavalle verkostojen tutkimiselle. Havaittiin että verkostoja on muutamanlaisia:
1: Säännöllinen verkosto on esimerkiksi sellainen, jossa kytkökset ovat lähelle. Tällöin kauas verkostossa pääseminen vaatii paljon askelia. Sillä on kuitenkin suuri rypäytymistodennäköisyys, eli jos A on yhteydessä B:hen ja B on yhteydessä C:hen, on todennäköistä että A on yhteydessä myös C:hen.
2: Satunnainen verkosto sisältää "pienen maailman", koska sotkuisen näköinen satunnaisverkosto on sellainen että siinä yleensä löytyy lyhyt reitti paikasta kuin paikasta toiseen. Tässä rypäytyminen on melko epätodennäköistä. Se että A on yhteydessä B:hen ja B yhteydessä C:hen on vain harvoin "todennäköisyydestä huolimatta, ei sen ansiosta" yhteydessä A:han.
3: Verkosto, jossa lainattu molempien ominaisuuksia; Siinä on siis sekä säännöllisen verkon ja satunnaisen verkon ominaisuuksia. Tässä linkit ovat yleensä lähelle, mutta siinä on harvakseltaan kauas johtavia linkkejä, ja tämän seurauksena on myös se, että vähällä määrällä askelia päästään melko pitkälle. Toisaalta se silti rypäytyy melko suuresti.

Verkostojen ominaisuuksia voidaan käsitellä ja laskea. Ja tätä voidaan soveltaa näyttelijöihinkin: Jotkin yleiset ja paljon näytelleet näyttelijät toimivat verkoissa ikään kuin liimana: He ovat tekemisissä suuren määrän muiden näyttelijöiden kanssa ja heidän kauttaan se ei enää ole pelkkä satunnainen joukko saman ammattikunnan edustajia. Sitä kautta sellainenkin näyttelijä jolla on ollut yksi pikkurooli voi hyvinkin olla yhteydessä toiseen aivan toisessa elokuvassa näytelleeseen pikkutekijään, kollegaalisessa yhteydessä. Eikä yhteydet ole välttämättä edes kaukana. Kuitenkaan tämä ei tarkoita että "kuuden ketju" olisi fakta. Itse asiassa ennuste sanoo ainoastaan sen, että on todennäköistä että lyhyt ketju henkilöstä toiseen löytyy. Kun oikein etsitään, voidaan periaatteessa löytää sellainen henkilö joka on teoriassa vaikka kymmenen askeleen päässä. Kuuden ketju on siis nyrkkisääntö. Jos taas uskoo että se pätee aina, kyseessä on väärinkäsitys.