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.
Ei kommentteja:
Lähetä kommentti
Ciinnostuin ma sun sanoist ia haluan sixi ehdottomasti mitellä canssais sanain säilää tahi muuten huastella.
Ennen taistoa näytän caswoni cuhin tekee tosi gentlemanni, tahi raotan cybäräin cantta antaen taiteilijanimen jolla minua puhuttaa. Ios haluan beittää aateluuteni ia toimia incognito iotta ylen ialoinen sucuisuuteni ei wastincumbbanini cättä turhaan bidättelis, teen tunnuxeni iotencin selwäxi. Nihin et caici tietäwät että sanoien tacana olen juuricin minä, encä secotu sanomain ioncu muun nimettoman sanomax, he cun ylen usein ioncin sortin celmi tahi ryovari on.
Mittelömme on cescittyy vahin tähän asiaan, encä halua tuoda muita rienoia, cinoia ia riitoia cun mist tässä hengen mieccain mittelemme. Seison sanoieni tacana iotca owat omiani. Suuni ei lurita toisten buheita, matci houccain sanomisia. Encä sanoillani toist arenaa mainoza.
Caicel olcon aicansa. Onbi aica taistella ia aica cwolla, eri aica bascahysisa asioida. Näit en toisiinsa secota ; Ymmärrän, joshi mittelö on wacawa asia, iossa hurmekin hubelehtii. Helbosti woisi haawain loucaantua. En halua catceroittaa cetään lobuxi icäänsä mielisuruihin waan byrin taistelemaan cuin tosi herrasmiehen, ritarim ia gentlemannin cunnialle sobii.
Sixi uscallan lausua noin nimetä että ios iocu alcaa himoita cuontaloani seinälleen wiisaitteni wuoxi, on turmeltunembi miesi, ei uroiden sotilasi waan boica-sicuri ionca buheis haise häne uran labiointi, ioca io hänen aiwoiens baica toimittabi.
En carde ; Sa varaudu!