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