10. Dynaaminen ohjelmointi

Dynaaminen ohjelmointi (dynamic programming) on algoritmitekniikka, jonka avulla voidaan ratkaista tehokkaasti monia hakuongelmia. Tutustumme tässä luvussa dynaamiseen ohjelmointiin seuraavan tehtävän kautta:

Tehtävä

Edellisessä luvussa ratkaisimme tehtävän tehokkaasti ahneella algoritmilla tapauksessa, jossa kolikot ovat $[1,2,5]$. Ahne algoritmi ei kuitenkaan toimi kaikissa tapauksissa: esimerkiksi jos kolikot ovat $[1,4,5]$, algoritmi voi antaa väärän vastauksen. Lisäksi ahneella algoritmilla ei ole mahdollista ratkaista tehtävän kohtaa 3, jossa tulee laskea kaikkien tapojen määrä.

Näemme seuraavaksi, miten saamme ratkaistua tehtävän kaikki kohdat tehokkaasti dynaamisen ohjelmoinnin avulla. Tässä tehtävässä esille tulevia ideoita pystyy käyttämään myös muiden tehtävien ratkaisemisessa.

Optimiratkaisun haku

Dynaamisessa ohjelmoinnissa on ideana ratkaista ongelma saman ongelman pienempien tapausten eli osaongelmien avulla. Esimerkiksi kun halutaan muodostaa summa $x$ kolikoista, osaongelmat ovat tapauksia, joissa halutaan muodostaa summat $0 \dots x-1$ kolikoista.

Tarkastellaan esimerkkiä, jossa halutaan muodostaa summa $x=13$ kolikoilla $[1,2,5]$. Voimme lähteä muodostamaan summaa $x$ valitsemalla ensimmäisen summaan kuuluvan kolikon. Vaihtoehdot ovat:

• Valitaan kolikko $1$. Tämän jälkeen tulee muodostaa summa $x=12$.
• Valitaan kolikko $2$. Tämän jälkeen tulee muodostaa summa $x=11$.
• Valitaan kolikko $5$. Tämän jälkeen tulee muodostaa summa $x=8$.

Jos tiedossa on pienin kolikoiden määrä tapauksille $x=8$, $x=11$ ja $x=12$, saamme pienimmän kolikoiden määrän tapaukselle $x=13$ valitsemalla näistä pienimmän ja lisäämällä tulokseen yhden. Niinpä seuraavaksi tulee ratkaista kolme osaongelmaa $x=8$, $x=11$ ja $x=12$. Nämä osaongelmat voi ratkaista samalla tavalla jakamalla ne edelleen pienempiin osaongelmiin.

Voimme toteuttaa dynaamisen ohjelmoinnin algoritmin käytännössä käymällä läpi osaongelmat pienimmästä suurimpaan:

def min_coins(x, coins):
    result = {}

    result[0] = 0
    for s in range(1, x + 1):
        result[s] = s
        for c in coins:
            if s - c >= 0:
                result[s] = min(result[s], result[s - c] + 1)

    return result[x]

Funktio muodostaa sanakirjan result, johon tallennetaan jokaiselle summalle $0 \dots x$ pienin kolikoiden määrä, jolla summa voidaan muodostaa. Funktio merkitsee ensin, että summan $0$ muodostamiseen tarvitaan $0$ kolikkoa. Tämän jälkeen funktio laskee muiden tapausten vastaukset silmukalla. Jokaisen summan kohdalla funktio käy läpi kolikot ja valitsee vaihtoehdon, jossa kolikoiden määrä on pienin.

Huomaa, että koska yksi kolikoista on aina arvoltaan $1$, kaikki summat $0 \dots x$ voidaan muodostaa kolikoista. Silmukassa kohtaan result[s] asetetaan alkuarvo s, joka vastaa ratkaisua, jossa jokainen kolikko on $1$.

Funktiota voidaan käyttää näin:

print(min_coins(13, [1, 2, 5])) # 4
print(min_coins(13, [1, 4, 5])) # 3
print(min_coins(42, [1, 5, 6, 17])) # 5

Kun $x=13$ ja kolikot ovat $[1,2,5]$, funktio laskee seuraavat tulokset:

Tästä näkee, että summan $x=13$ muodostamiseen tarvitaan $4$ kolikkoa ja kaikissa pienemmissä tapauksissa riittää enintään $3$ kolikkoa.

Kun $x=13$ ja kolikot ovat $[1,4,5]$, tulokset ovat:

Tässä tapauksessa ahne algoritmi ei antaisi oikeaa vastausta, mutta dynaamisen ohjelmoinnin algoritmi toimii, koska se käy läpi kaikki tavat valita kolikot.

Algoritmin aikavaativuus on $O(nx)$, missä $n$ on kolikoiden määrä ja $x$ on muodostettava summa. Tämän ansiosta voidaan käsitellä tehokkaasti myös suuria tapauksia, mikä ei olisi mahdollista raa’an voiman algoritmeilla.

Optimiratkaisun muodostus

Laajennetaan seuraavaksi dynaamisen ohjelmoinnin algoritmia niin, että se etsii pienimpään ratkaisuun tarvittavat kolikot. Esimerkiksi kun $x=13$ ja kolikot ovat $[1,2,5]$, algoritmin tulisi palauttaa ratkaisu $[1,2,5,5]$ eikä vain ilmoittaa, että pienimmässä ratkaisussa on $4$ kolikkoa.

Tällainen algoritmi voidaan toteuttaa tallentamalla jokaiselle summalle $0 \dots x$ lista kolikoista, joilla summa voidaan muodostaa ja jossa kolikoiden määrä on mahdollisimman pieni. Tällöin listan pituus on yhtä suuri kuin summaa $x$ vastaava pienin kolikoiden määrä. Tämä voidaan toteuttaa seuraavasti:

def min_coins(x, coins):
    result = {}

    result[0] = []
    for s in range(1, x + 1):
        result[s] = [1] * s
        for c in coins:
            if s - c >= 0:
                new_result = result[s - c] + [c]
                if len(new_result) < len(result[s]):
                    result[s] = new_result

    return sorted(result[x])

Silmukassa lista new_result muodostetaan ottamalla pohjaksi lyhin lista, jonka kolikot muodostavat summan $s - c$. Tämän listan perään lisätään kolikko $c$, jolloin saadaan lyhin lista, jonka kolikot muodostavat summan $s$ ja jossa viimeinen kolikko on $c$. Jos lista on aiempaa lyhempi, siitä tulee ratkaisu summalle $s$.

Funktiota voidaan käyttää näin:

print(min_coins(13, [1, 2, 5])) # [1, 2, 5, 5]
print(min_coins(13, [1, 4, 5])) # [4, 4, 5]
print(min_coins(42, [1, 5, 6, 17])) # [1, 1, 6, 17, 17]

Ratkaisujen laskeminen

Dynaamisen ohjelmoinnin avulla voidaan myös laskea, montako erilaista ratkaisua tehtävään on olemassa. Esimerkiksi kun $x=13$ ja kolikot ovat $[1,2,5]$, mahdollisia ratkaisuja on yhteensä $634$. Tässä on joitakin mahdollisia ratkaisuja:

• $[1,2,5,5]$
• $[2,2,2,2,5]$
• $[1,1,1,5,5]$
• $[2,2,2,2,2,2,1]$
• $[1,1,1,1,1,1,1,1,1,1,1,1,1]$

Kaikkien ratkaisujen määrä voidaan etsiä melko samalla tavalla kuin pienimmän ratkaisun kolikkojen määrä. Haku voidaan toteuttaa seuraavasti:

def count_coins(x, coins):
    result = {}

    result[0] = 1
    for s in range(1, x + 1):
        result[s] = 0
        for coin in coins:
            if s - coin >= 0:
                result[s] += result[s - coin]

    return result[x]

Erona aiempaan funktioon min_coins verrattuna on, että funktio laskee minimien sijasta summia. Tapauksessa $x=0$ tulos on $1$, koska on yksi tapa muodostaa summa $0$ (ei valita mitään kolikkoja). Muissa tapauksissa funktio käy läpi vaihtoehdot, mikä on summan viimeinen kolikko, ja laskee mukaan nämä tapaukset.

Funktiota voidaan käyttää näin:

print(count_coins(13, [1, 2, 5])) # 634
print(count_coins(13, [1, 4, 5])) # 88
print(count_coins(42, [1, 5, 6, 17])) # 1103532

Huomaa, että funktio laskee erikseen kaikki tavat järjestää kolikot listaan. Esimerkiksi funktio laskee erikseen mukaan ratkaisut $[1,2,5,5]$, $[1,5,2,5]$ ja $[1,5,5,2]$, vaikka ne muodostuvat samoista kolikoista. Vaikeampi tehtävä, joka on myös mahdollista ratkaista dynaamisella ohjelmoinnilla, on laskea mukaan jokainen samojen kolikoiden yhdistelmä vain kerran.

Esimerkki: Alijonot

Tehtävä

Voimme lähestyä tehtävää dynaamisen ohjelmoinnin avulla laskemalla jokaiselle listan kohdalle, kuinka pitkä on pisin kyseiseen kohtaan päättyvä alijono. Esimerkissä laskettavat luvut ovat seuraavat:

Esimerkiksi pisin kohtaan $5$ päättyvä alijono on $[1,3,4]$, jonka pituus on $3$.

Seuraava funktio find_longest etsii annetun listan pisimmän nousevan alijonon dynaamisen ohjelmoinnin avulla:

def find_longest(items):
    result = {}

    max_len = 0
    for i in range(len(items)):
        result[i] = 1
        for j in range(i):
            if items[j] < items[i]:
                result[i] = max(result[i], result[j] + 1)
        max_len = max(max_len, result[i])

    return max_len

Funktio luo sanakirjan result ja laskee siihen jokaiseen kohtaan pisimmän nousevan alijonon pituuden listassa. Muuttuja i käy läpi listan kohdat ja muuttuja j käy läpi mahdolliset kohdat, jossa on alijonon edellinen luku. Jos edellinen luku on pienempi kuin nykyinen luku, alijonoa voidaan laajentaa. Muuttujassa max_len pidetään yllä pisimmän alijonon pituutta.

Funktiota voidaan käyttää näin:

print(find_longest([4, 1, 5, 6, 3, 4, 1, 8])) # 4

Tämän algoritmin aikavaativuus on $O(n^2)$, koska siinä on kaksi sisäkkäistä silmukkaa. Koska kaikkien alijonojen määrä on $O(2^n)$, tämä on merkittävä tehostus verrattuna siihen, että kaikki alijonot käytäisiin läpi.

Esimerkki: Sulkulausekkeet

Joskus raa’an voiman ratkaisu on yllättävän helppoa muuttaa dynaamisen ohjelmoinnin ratkaisuksi. Näin on seuraavassa tehtävässä:

Tehtävä

Edellisessä luvussa ratkaisimme tehtävän raa’an voiman avulla näin:

def count_sequences(n, d=0):
    if d < 0 or d > n:
        return 0
    if n == 0:
        return 1
    return count_sequences(n - 1, d + 1) + \
           count_sequences(n - 1, d - 1)

Tämän ratkaisun voi muuttaa tehokkaaksi dynaamisen ohjelmoinnin ratkaisuksi tallentamalla funktion tulokset muistiin sanakirjaan:

def count_sequences(n, d=0, result={}):
    if d < 0 or d > n:
        return 0
    if n == 0:
        return 1
    if (n, d) not in result:
        result[(n, d)] = count_sequences(n - 1, d + 1) + \
                         count_sequences(n - 1, d - 1)
    return result[(n, d)]

Tässä tapauksessa dynaamisen ohjelmoinnin osaongelmat ovat pareja muotoa $(n,d)$, missä $n$ on lisättävien sulkujen määrä ja $d$ on muodostetun lausekkeen syvyys. Sanakirja result sisältää vastaukset kaikille parametrien yhdistelmille, jotka funktio on jo laskenut. Funktio laskee vastauksen rekursiivisesti vain, jos sitä ei ole laskettu aiemmin, ja hakee vastauksen muuten suoraan sanakirjasta.

Alkuperäinen raa’an voiman funktio soveltui vain pienten tapausten laskemiseen, mutta dynaamisen ohjelmoinnin ansiosta voimme laskea myös suuria tapauksia. Esimerkiksi voimme laskea sulkulausekkeiden määrän, kun $n=100$:

print(count_sequences(100)) # 1978261657756160653623774456

Koska jokainen funktion kutsu vie aikaa $O(1)$ ja erilaisia parametrien yhdistelmiä on $O(n^2)$, algoritmin aikavaativuus on $O(n^2)$.

Tämä tehtävä on mahdollista ratkaista myös toisella tavalla dynaamisella ohjelmoinnilla niin, että funktiolla on pelkkä parametri $n$:

def count_sequences(n, result={}):
    if n == 0:
        return 1
    if n not in result:
        count = 0
        for i in range(2, n + 1, 2):
            count += count_sequences(i - 2) * \
                     count_sequences(n - i)
        result[n] = count
    return result[n]

Tässä ideana on käydä läpi kaikki tavat valita kohta, jossa on ensimmäistä alkusulkua ( vastaava loppusulku ). Jokaisessa tavassa näiden sulkujen väliin sekä näiden sulkujen jälkeen tulee jokin sulkulauseke, minkä ansiosta lausekkeiden määrä saadaan kertomalla väliin ja jälkeen tulevien lausekkeiden määrät.

Tässä algoritmissa jokainen funktion kutsu vie aikaa $O(n)$ ja erilaisia parametrien yhdistelmiä on $O(n)$. Myös tämän algoritmin aikavaativuus on siis $O(n^2)$, vaikka algoritmien logiikka on hyvin erilainen.

Sisäkkäinen rekursio

Rekursiolla toteutettu dynaaminen ohjelmointi voi aiheuttaa paljon sisäkkäistä rekursiota, mikä voi aiheuttaa ongelman koodin suorittamiseen. Esimerkiksi seuraava koodi ei toimi toivotulla tavalla:

print(count_sequences(2000)) # ?

Koodin suoritus aiheuttaa virheen ”RecursionError: maximum recursion depth exceeded in comparison” mikä tarkoittaa, että funktiota count_sequences kutsutaan liian monta kertaa rekursiivisesti.

Pythonissa sisäkkäisten rekursiokutsujen raja on usein oletuksena melko pieni, esimerkiksi 1000. Rajaa voidaan kuitenkin nostaa moduulin sys funktiolla setrecursionlimit seuraavasti:

import sys
sys.setrecursionlimit(5000)

Tämän jälkeen koodin suorittaminen onnistuu:

print(count_sequences(2000)) # 2046105521468021692642519982997827217179245642339057975844538099572176010191891863964968026156453752449015750569428595097318163634370154637380666882886375203359653243390929717431080443509007504772912973142253209352126946839844796747697638537600100637918819326569730982083021538057087711176285777909275869648636874856805956580057673173655666887003493944650164153396910927037406301799052584663611016897272893305532116292143271037140718751625839812072682464343153792956281748582435751481498598087586998603921577523657477775758899987954012641033870640665444651660246024318184109046864244732001962029120

Rekursiorajan kasvattaminen voi kuitenkin olla kyseenalainen ratkaisu, koska se saattaa aiheuttaa ongelmia Pythonin suoritusympäristössä. Toinen ratkaisu on muuttaa dynaamisen ohjelmoinnin toteutusta niin, että rekursion sijasta käytetäänkin silmukoita. Tarkastellaan esimerkkinä seuraavaa toteutusta:

def count_sequences(n, d=0, result={}):
    if d < 0 or d > n:
        return 0
    if n == 0:
        return 1
    if (n, d) not in result:
        result[(n, d)] = count_sequences(n - 1, d + 1) + \
                         count_sequences(n - 1, d - 1)
    return result[(n, d)]

Rekursio voidaan poistaa miettimällä, missä järjestyksessä funktio lisää osaongelmien vastaukset sanakirjaan result, ja toteuttamalla sitten vastaavan laskennan ilman rekursiota. Tässä tapauksessa laskenta voidaan toteuttaa näin:

def count_sequences(n):
    result = {}
    result[(0, 0)] = 1
    for i in range(1, n + 1):
        result[(0, i)] = 0
    for i in range(1, n + 1):
        for j in range(0, n + 1):
            result[(i, j)] = 0
            if j + 1 <= n:
                result[(i, j)] += result[(i - 1, j + 1)]
            if j - 1 >= 0:
                result[(i, j)] += result[(i - 1, j - 1)]
    return result[(n, 0)]

Tämän toteutuksen etuna on, että siinä ei ole rekursiota eikä sitä käyttäessä tarvitse huolehtia Pythonin rekursiorajasta. Kuitenkin huonona puolena tällaisessa toteutuksessa täytyy suunnitella itse, missä järjestyksessä osaongelmat käsitellään, eikä sitä voi jättää rekursion vastuulle.