wiki:k2015/luennot/luento20/euler67
Last modified 2 years ago Last modified on 2015-03-20 14:05:47

Tämän päivän luennolla rekursio, ja erityisesti se "Suurin polku" -esimerkki (ks. https://projecteuler.net/problem=67) jäi ajatuksena aavistuksen kesken. Se mitä jäi sanomatta, oli se, että tekemässäni esimerkissä oli tekstitiedostossa rivejä "vain" 28 kappaletta, ja sen takia solutions- muuttujaan tuli "vain" 200 miljoonaa tarkistusta. Jos rivejä olisi 100, kuten alkuperäisessä tehtävässä, tulisi tehtävästä mahdoton ratkaista äärellisessä ajassa tuolla tekemälläni algoritmilla, koska siinä käydään kaikki mahdolliset ratkaisut (reitit) läpi -- toisin kuin annoin ymmärtää tänään luennolla.

Eli vaikka rekursiolla tehtäessä ratkaisuista tulee monesti elegantteja ja lyhyitä, eivät ne kuitenkaan välttämättä ole kovin tehokkaita. Tämä riippuu kuitenkin pikkaisen kielestä ja sen sisäisestä toteutuksesta.

Se miksi tuo rekursio-tyylinen naiivi ratkaisu ei ole tuossa kyseisessä tehtävässä järkevä johtuu siitä, että tiettyjen reittien matkat tulee käytännössä laskettua monta kertaa. Esimerkiksi tuossa alkuperäisessä euler- tehtävässä reitti 4->9 (toiseksi viimeiseltä riviltä viimeiselle riville) tulee käytyä läpi SEKÄ 7:n kautta laskettuna (toinen rivi ylhäältä) ETTÄ 4:n kautta laskettuna (toinen rivi ylhäältä). Tehdään siis turhaa työtä joka oleellisesti hidastaa laskentaa kun noita rivejä on paljon.

Laitoin tuon tehtävän demo 10:n gurutehtäväksi (https://trac.cc.jyu.fi/projects/ohj1/wiki/k2015/demot/demo10#G5-6), joten en vielä paljasta omaa "nopeaa" ratkaisuani siihen :-).

Antti-Jussi