Dinamično programiranje#

Recimo, da imamo veliko kock velikosti 1, 2 in 3, vsako v svoji barvi. Zanima nas, koliko različnih stolpov lahko sestavimo iz njih.

Na primer, sestavimo lahko štiri različne stolpe višine 3: 1 1 1, 1 2, 2 1 in 3. V splošnem lahko vidimo, da so stolpi višine \(n\) treh različnih oblik:

  1. na dnu je kocka velikosti 1, nad njo pa stolp višine \(n - 1\),

  2. na dnu je kocka velikosti 2, nad njo pa stolp višine \(n - 2\),

  3. na dnu je kocka velikosti 3, nad njo pa stolp višine \(n - 3\).

Pri tem moramo paziti še na robne pogoje, ki jih najbolj enostavno zapišemo tako, da je stolp ničelne višine natanko en, stolpov negativne višine pa ni:

def stevilo_stolpov(n):
    if n < 0:
        return 0
    elif n == 0:
        return 1
    else:
        return sum(stevilo_stolpov(n - k) for k in [1, 2, 3])

stevilo_stolpov(3)

4

stevilo_stolpov(10)

274

Čas za izračun števila stolpov višine \(n\) hitro narašča:

%timeit stevilo_stolpov(10)

191 µs ± 646 ns per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

%timeit stevilo_stolpov(11)

352 µs ± 794 ns per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

%timeit stevilo_stolpov(12)

651 µs ± 1.08 µs per loop (mean ± std. dev. of 7 runs, 1,000 loops each)

Razlog za to je v podvojevanju izračunov. Na primer, poglejmo, katere vrednosti moramo izračunati, da ugotovimo število stolpov višine 3:

Funkcijo moramo poklicati trinajstkrat. Število klicev bi s posebnimi primeri lahko zmanjšali, vendar je eksponentna rast neizogibna. Vidimo, da pri klicih prihaja do podvojitev. Strategiji, s katero se jim izognemo, pravimo dinamično programiranje. Intuitivno je struktura podnalog videti približno takole:

Podvojevanju se lahko izognemo na dva načina. Prvi je memoizacija, pri kateri si računalnik samodejno shranjuje izračunane rezulate in jo bomo pogledali naslednjič. Drugi pa je pristop od spodaj navzgor, v katerem rešitve pripravimo v ustreznem vrstnem redu. Takih vrstnih redov je lahko več, saj moramo poskrbeti le za to, da so vse podnaloge pravočasno rešene:

V primeru računanja števila stolpov je tak vrstni red samo en: od \(1\) do \(n\), zato ni vprašanja, kako se bomo lotili dela. Vsako izračunano vrednost si bomo shranili v seznam in nadaljevali z naslednjo. V resnici ne potrebujemo vseh izračunanih vrednosti, temveč samo zadnje tri:

def hitro_stevilo_stolpov(n):
    stevilo, stevilo_minus_1, stevilo_minus_2 = 1, 0, 0
    for i in range(n):
        novo_stevilo = stevilo + stevilo_minus_1 + stevilo_minus_2
        stevilo, stevilo_minus_1, stevilo_minus_2 = novo_stevilo, stevilo, stevilo_minus_1
    return stevilo

hitro_stevilo_stolpov(3)

4

hitro_stevilo_stolpov(10)

274

Nova funkcija deluje mnogo hitreje in sicer v linearnem času.

%timeit hitro_stevilo_stolpov(10)

737 ns ± 13 ns per loop (mean ± std. dev. of 7 runs, 1,000,000 loops each)

%timeit hitro_stevilo_stolpov(100)

7.18 µs ± 60.1 ns per loop (mean ± std. dev. of 7 runs, 100,000 loops each)

%timeit hitro_stevilo_stolpov(1000)

106 µs ± 3.51 µs per loop (mean ± std. dev. of 7 runs, 10,000 loops each)

hitro_stevilo_stolpov(10000)

1930715638812503980978477742176765059817000946408020458616966472532160136748685107885905980372339049224776587678431380225014854419087911121131396370148439482037441811335770739632524231756180470676206524632137242871648864178751465042753209923059876871711637731225356990628561878347663767117976253661277522979962519786201622871530774770637486281263408219608965804499766300728870340881571295969662390555384137391425076062990692682318756919512343540885026173478700526094764968441814941887862435392916726255063188548564097823974367812775902885600490532695134200880579294185102149934220395208779681909069641715377598726598332270512736052329261902007259465880127414067819207706704390368062999842794862763437159098488131812468396667770977541784569786308819346920271818703891223466781031878470954603905351912111348558176468800741434264557449695354345746716131009982982017636906969591004514769269878719206834018215416994267573739388479951784999527799851652258110727538261742176091202079829830620486815249778625475238693390644083651762704217453735799816804413172171223434689196342963615038361674273524894874245568945059811939564115797631041266143063330365392499398501724080709091959012172021806993134787182001380898097360043331816909033259191678579450003863714483397595334971593972257605199408522260734830841216909691270785232156757176590253640499908827673376923144133787744116154841376095021117963693870277526898764858623966640853789117478648970478992514101337504808636652852984364471366272820035909723601410522219437068019495364649698623244740681547393811666634518114102147868844956036371461499546586852331283585300785900327839247939204205582693354098669543633046057890222624011175132264010713459005979014537778554203096317054194396713096782546679614415236733131969462826941311693549970027540774289950455984491240216393662297068078232748535624545451186844744385039914332342018166219951271152942927531653401178738367596865402888432989238731721608032445342782912019747215791930022127468528575795886164583090399609136974565184000304719559853065592962756615762189221562355501477384282655239367297099981861970002041923074093094315767673196782708973029913765232547695710360662256632221777654399005864677663533682942690860556838383041983564567154601294341140662928927582787185710584039211793215151302345840851724148655428030679536009820848391332350263370485321205324369323599941426412387240034829157420109122068953279465696010927715119511221107536031592185197333377580297818825824007421235046372894013450316689382024695255792153960245806766169732098492506684653219638122737801337025633407035724210635813119393946653088334908386739151802326021713639813341762179185

Nalogo se da rešiti tudi v logaritemskem času, se spomnite kako?

Najcenejša pot v matriki#

Malo zahtevnejši primer je iskanje najcenejše poti iz zgornjega levega v spodnji desni kot matrike, pri čemer se lahko premikamo le desno in navzdol. V spodnji matriki je ta pot označena s krepkimi števkami:

131

673

234

103

18

201

96

342

965

150

630

803

746

422

111

537

699

497

121

956

805

732

524

37

331

Eden izmed načinov, kako to nalogo razbijemo na manjše, je, da si ogledamo prvi korak. Ta gre lahko desno ali navzdol. Če gre na desno, potem mora biti njen preostanek najkrajša pot v matriki brez prvega stolpca. Če to ne bi bilo res in bi v matriki brez prvega stolpca obstajala cenejša pot, bi jo lahko razširili s prvim poljem in tako dobili še cenejšo pot v celotni matriki. Če pa gre prvi korak navzdol, mora biti njen preostanek podobno najkrajša pot v matriki brez prve vrstice.

Da nam matrik ne bo treba spreminjati, si bomo zabeležili indeksa začetnega polja in raje spreminjali ta dva:

def cena_najcenejse_poti_iz_polja(matrika, i, j):
    m, n = len(matrika), len(matrika[0])
    if i < n - 1 and j < m - 1:
        cena_navzdol = cena_najcenejse_poti_iz_polja(matrika, i + 1, j)
        cena_desno = cena_najcenejse_poti_iz_polja(matrika, i, j + 1)
        return matrika[i][j] + min(cena_navzdol, cena_desno)
    elif i < n - 1:
        cena_navzdol = cena_najcenejse_poti_iz_polja(matrika, i + 1, j)
        return matrika[i][j] + cena_navzdol
    elif j < m - 1:
        cena_desno = cena_najcenejse_poti_iz_polja(matrika, i, j + 1)
        return matrika[i][j] + cena_desno
    else:
        return matrika[i][j]

m = [[131, 673, 234, 103, 18],
     [201, 96, 342, 965, 150],
     [630, 803, 746, 422, 111],
     [537, 699, 497, 121, 956],
     [805, 732, 524, 37, 331]]

cena_najcenejse_poti_iz_polja(m, 0, 0)

2427

Če želimo, lahko program spremenimo tako, da vrne tudi obiskana polja:

def najcenejsa_pot_iz_polja(matrika, i, j):
    m, n = len(matrika), len(matrika[0])
    if i < n - 1 and j < m - 1:
        cena_in_pot_navzdol = najcenejsa_pot_iz_polja(matrika, i + 1, j)
        cena_in_pot_desno = najcenejsa_pot_iz_polja(matrika, i, j + 1)
        min_cena, min_pot = min(cena_in_pot_navzdol, cena_in_pot_desno)
        return matrika[i][j] + min_cena, [matrika[i][j]] + min_pot
    elif i < n - 1:
        cena_navzdol, pot_navzdol = najcenejsa_pot_iz_polja(matrika, i + 1, j)
        return matrika[i][j] + cena_navzdol, [matrika[i][j]] + pot_navzdol
    elif j < m - 1:
        cena_desno, pot_desno = najcenejsa_pot_iz_polja(matrika, i, j + 1)
        return matrika[i][j] + cena_desno, [matrika[i][j]] + pot_desno
    else:
        return matrika[i][j], [matrika[i][j]]

najcenejsa_pot_iz_polja(m, 0, 0)

(2427, [131, 201, 96, 342, 746, 422, 121, 37, 331])

Seveda pa ta rešitev ni učinkovita, saj podvajamo klice. Na primer, če gremo desno in dol, pridemo do istega polja kot dol in desno.

Spet se bomo poslužili dinamičnega programiranja in najcenejšo pot iz vsakega polja izračunali samo enkrat. Najprej bomo izračunali pot, ki začne v spodnjem desnem kotu, kar bo trivialno. S pomočjo te bomo izračunali pot iz njegovega levega soseda in tako naprej. Ko bomo pregledali poti iz vseh polj spodnje vrstice, se bomo premaknili eno vrstico višje. Ko bomo izračunali poti iz vseh polj, bomo končali v zgornjem levem polju, kar je vrednost, ki smo jo iskali.

def cena_najcenejse_poti(matrika):
    m, n = len(matrika), len(matrika[0])
    # Pripravimo matriko, v katero bomo shranjevali cene
    cena = [[None for _ in range(n)] for _ in range(m)]
    # Premikamo se po vrsticah navzgor
    for i in range(m - 1, -1, -1):
        # V vsaki vrstici se po poljih premikamo na levo
        for j in range(n - 1, -1, -1):
            if i < n - 1 and j < m - 1:
                cena[i][j] = matrika[i][j] + min(cena[i + 1][j], cena[i][j + 1])
            elif i < n - 1:
                cena[i][j] = matrika[i][j] + cena[i + 1][j]
            elif j < m - 1:
                cena[i][j] = matrika[i][j] + cena[i][j + 1]
            else:
                cena[i][j] = matrika[i][j]
    return cena[0][0]

cena_najcenejse_poti(m)

2427