9. Hakuongelmat

Monet algoritmiset ongelmat ovat luonteeltaan hakuongelmia, joissa on joukko mahdollisia ratkaisuja ja tavoitteena on löytää jollain tavalla optimaalinen ratkaisu tai laskea halutunlaisten ratkaisujen määrä.

Yleispätevä tapa ratkaista hakuongelmia on toteuttaa raakaan voimaan (brute force) perustuva haku, joka käy läpi kaikki ratkaisut yksi kerrallaan. Tämän menetelmän etuna on, että se tuottaa varmasti oikean vastauksen, mutta toisaalta haku voi olla liian hidas, jos ratkaisujen määrä on suuri.

Jos tavoitteena on löytää optimaalinen ratkaisu, tilanteeseen voi sopia ahne algoritmi (greedy algorithm), joka muodostaa ratkaisun tehokkaasti jonkin logiikan perusteella käymättä läpi kaikkia vaihtoehtoja. Kuitenkin riskinä ahneessa algoritmissa on, että se ei tuota optimaalista ratkaisua kaikissa tapauksissa.

Edistyneempi tekniikka hakuongelmissa on dynaaminen ohjelmointi (dynamic programming), jota voidaan käyttää sekä optimaalisen ratkaisun etsimiseen että ratkaisujen määrän laskemiseen. Tutustumme dynaamiseen ohjelmointiin tarkemmin seuraavassa luvussa.

Ratkaisujen läpikäynti

Hakuongelmia voidaan ratkaista raa’alla voimalla käymällä läpi kaikki mahdolliset ratkaisut yksi kerrallaan. Läpikäynnin aikana voidaan valikoida ratkaisut, jotka täyttävät tietyt ehdot tai ovat jollain tavalla optimaalisia.

Raa’an voiman algoritmi voidaan toteuttaa usein niin, että se käy läpi kaikki tavat muodostaa sopivanlainen yhdistelmä syötteenä annetuista alkioista. Seuraavassa on kolme tavallista tilannetta:

Kaikki yhdistelmät

Syötteenä on $n$ alkiota ja halutaan muodostaa kaikki yhdistelmät, joissa valitaan $m$ kertaa jokin alkioista. Tällaisia yhdistelmiä on yhteensä $n^m$.

Esimerkiksi jos alkiot ovat $[1,2,3]$ ja $m=2$, yhdistelmät ovat $[1,1]$, $[1,2]$, $[1,3]$, $[2,1]$, $[2,2]$, $[2,3]$, $[3,1]$, $[3,2]$ ja $[3,3]$.

Pythonissa yhdistelmät voidaan muodostaa moduulin itertools funktion product avulla. Funktiolle annetaan listana valittavana olevat alkiot sekä parametrin repeat kautta valintojen määrä. Funktiota voidaan käyttää näin:

import itertools

for repetition in itertools.product([1, 2, 3], repeat=2):
    print(repetition)

(1, 1)
(1, 2)
(1, 3)
(2, 1)
(2, 2)
(2, 3)
(3, 1)
(3, 2)
(3, 3)

Permutaatiot

Syötteenä on $n$ alkiota ja halutaan muodostaa kaikki alkoiden permutaatiot eli erilaiset järjestykset. Permutaatioiden määrä on $n!$.

Esimerkiksi jos alkiot ovat $[1,2,3]$, permutaatiot ovat $[1,2,3]$, $[1,3,2]$, $[2,1,3]$, $[2,3,1]$, $[3,1,2]$ ja $[3,2,1]$.

Pythonissa listan alkioiden permutaatiot voidaan käydä läpi moduulin itertools funktion permutations avulla näin:

import itertools

for permutation in itertools.permutations([1, 2, 3]):
    print(permutation)

Koodin tulostus on seuraava:

(1, 2, 3)
(1, 3, 2)
(2, 1, 3)
(2, 3, 1)
(3, 1, 2)
(3, 2, 1)

Kombinaatiot

Syötteenä on $n$ alkiota ja halutaan muodostaa kaikki $m$ alkion osajoukot eli kaikki erilaiset tavat valita $m$ alkiota. Tällaisten kombinaatioiden määrä on $n \choose m$.

Esimerkiksi jos alkiot ovat $[1,2,3,4]$ ja $m=2$, kombinaatiot ovat $[1,2]$, $[1,3]$, $[1,4]$, $[2,3]$, $[2,4]$ ja $[3,4]$.

Pythonissa listan alkioiden kombinaatiot voidaan käydä läpi moduulin itertools funktion combinations avulla näin:

import itertools

for combination in itertools.combinations([1, 2, 3, 4], 2):
    print(combination)

Koodin tulostus on seuraava:

(1, 2)
(1, 3)
(1, 4)
(2, 3)
(2, 4)
(3, 4)

Esimerkki: Järjestykset

Tehtävä

Tehtävä voidaan ratkaista algoritmilla, joka käy läpi alkioiden $1 \dots n$ permutaatiot ja tarkastaa jokaisesta permutaatiosta, täyttääkö se halutun vaatimuksen eli vierekkäin ei ole kahta peräkkäistä lukua. Jos vaatimus täyttyy, permutaatio on yksi mahdollinen ratkaisu ja ratkaisujen määrä kasvaa yhdellä.

Algoritmi voidaan toteuttaa seuraavasti funktiona count_orders:

import itertools

def count_orders(n):
    items = range(1, n + 1)
    count = 0

    for order in itertools.permutations(items):
        if valid_order(order):
            count += 1

    return count

def valid_order(order):
    for i in range(len(order) - 1):
        if abs(order[i] - order[i + 1]) == 1:
            return False
    return True

Funktio count_orders käy läpi kaikki permutaatiot luvuista $1 \dots n$. Jokaisen permutaation kohdalla kutsutaan funktiota valid_order, joka ilmoittaa, onko järjestys kelvollinen. Ratkaisujen määrä lasketaan muuttujaan count, jonka funktio count_orders palauttaa lopuksi.

Esimerkiksi count_orders(4) antaa halutun tuloksen $2$. Funktion toimintaa voidaan tarkastella lähemmin muuttamalla sitä niin, että se myös tulostaa kaikki löydetyt ratkaisut:

    for order in itertools.permutations(items):
        if valid_order(order):
            print(order)
            count += 1

Tämän muutoksen jälkeen kutsu count_orders(4) tulostaa seuraavat rivit:

(2, 4, 1, 3)
(3, 1, 4, 2)

Algoritmin aikavaativuus on $O(n! n)$, koska se käy läpi $n!$ permutaatiota ja jokaisen permutaation tarkastaminen vie aikaa $O(n)$. Koska $n!$ kasvaa nopeasti, algoritmi toimii tehokkaasti vain, jos $n$ on pieni.

Seuraava taulukko näyttää, miten ratkaisujen määrä ja koodin suoritusaika testikoneella muuttuvat $n$:n kasvaessa:

Kun $n$ on $10$ tai suurempi, laskenta alkaa viedä paljon aikaa, koska tarkastettavien permutaatioiden määrä $n!$ on suuri.

Esimerkki: Sulkulausekkeet

Tehtävä

Tehtävä voidaan ratkaista algoritmilla, joka muodostaa kaikki mahdolliset yhdistelmät suluista ( ja ) ja laskee niistä mukaan kelvolliset sulkulausekkeet. Algoritmi voidaan toteuttaa seuraavasti funktiona count_sequences:

import itertools

def count_sequences(n):
    count = 0
    for sequence in itertools.product("()", repeat=n):
        if valid_sequence(sequence):
            count += 1
    return count

def valid_sequence(sequence):
    depth = 0
    for bracket in sequence:
        if bracket == "(":
            depth += 1
        if bracket == ")":
            depth -= 1
        if depth < 0:
            return False
    return depth == 0

Funktio count_sequences käy läpi kaikki mahdolliset sulkuyhdistelmät. Funktio käyttää apunaan funktiota product, joka valitsee $n$ kertaa sulun ( tai ).

Funktio valid_sequence tarkastaa, onko sille annettu yhdistelmä kelvollinen sulkulauseke. Funktio käy läpi merkit vasemmalta oikealle ja pitää yllä muuttujassa depth tietoa sisäkkäisten sulkujen syvyydestä. Sulkulauseke on kelvollinen, jos syvyys ei ole koskaan negatiivinen ja on lopuksi nolla.

Esimerkiksi count_sequences(6) antaa tuloksen $5$. Huomaa, että sulkulauseke voi olla kelvollinen vain silloin, kun $n$ on parillinen.

Algoritmin aikavaativuus on $O(2^n n)$, koska se käy läpi $2^n$ sulkuyhdistelmää ja jokaisen yhdistelmää tarkastaminen vie aikaa $O(n)$. Seuraava taulukko näyttää ratkaisujen määrän ja koodin suoritusajan testikoneella:

Verrattuna edellisen esimerkin permutaatioiden laskemiseen algoritmilla pystyy käsittelemään hieman suurempia $n$:n arvoja. Permutaatioissa tehokkaan laskennan rajana on tapaus $n=10$, mutta tässä päästään tapaukseen $n=20$. Syynä tähän on, että $2^n$ kasvaa hitaammin kuin $n!$. Kuitenkin tapauksesta $n=20$ alkaen myös tämä algoritmi hidastuu selvästi.

Haun tehostaminen

Kahdessa äskeisessä esimerkissä haku toteutettiin niin, että se muodostaa kaikki mahdolliset ratkaisut ja tarkastaa kunkin ratkaisun kohdalla, onko ratkaisu kelvollinen. Tämä on toimiva tapa, mutta haku saattaa tehdä turhaa työtä käydessään läpi ratkaisuja, jotka eivät ole kelvollisia.

Tarkastellaan esimerkkinä sulkulausekkeiden määrän laskemista. Kun algoritmi käy läpi kaikki suluista muodostuvat yhdistelmät, mukana on paljon yhdistelmiä, jotka eivät ole kelvollisia. Esimerkiksi mikään sululla ) alkava yhdistelmä ei ole kelvollinen, joten ainakin puolet muodostetuista sulkuyhdistelmistä ei ole kelvollisia. Todellisuudessa kelvollisten yhdistelmien määrä on vielä selvästi pienempi: esimerkiksi tapauksessa $n=20$ käydään läpi $2^{20}=1048576$ sulkuyhdistelmää, mutta niistä vain $16796$ eli noin joka sadas on kelvollinen.

Tällaisessa algoritmissa on myös toinen hidastava tekijä: vaikka tavoitteena on vain laskea sulkulausekkeiden määrä, haku muodostaa kaikki sulkulausekkeet. Tämä voi olla turhaa työtä, koska algoritmin tulee vain palauttaa sulkulausekkeiden määrä eikä näyttää, millaisia sulkulausekkeet ovat.

Seuraavassa on tehokkaammin toteutettu hakualgoritmi:

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ä funktio ei käytä moduulia itertools ratkaisujen muodostamiseen, vaan se käy läpi ratkaisut suoremmin rekursiivisesti. Ideana on, että jokainen rekursiivinen kutsu lisää sulkulausekkeen loppuun uuden sulun. Parametri n ilmaisee, montako sulkua ratkaisuun tulee vielä lisätä, ja parametri d pitää yllä tietoa sulkujen syvyydestä (alussa syvyys on $0$). Joka vaiheessa on kaksi vaihtoehtoa: sulku ( kasvattaa syvyyttä ja sulku ) pienentää syvyyttä.

Algoritmi tarkkailee joka vaiheessa, että muodosteilla olevasta sulkulausekkeesta tulee kelvollinen. Tämä on toteutettu kahden ehdon avulla: jos syvyys menee negatiiviseksi (d < 0) tai syvyys on suurempi kuin lisättävien sulkujen määrä (d > n), haku keskeytetään. Jos kaikki sulut on lisätty (n == 0), yksi kelvollinen sulkulauseke on tullut valmiiksi.

Huomaa, että algoritmin muistissa ei ole tietoa sulkulausekkeen sisällöstä vaan vain lisättävien sulkujen määrä sekä syvyys. Esimerkiksi jos lasketaan pituuden $8$ sulkulausekkeita ja muodosteilla oleva lauseke alkaa ((), tätä tilannetta vastaava funktion kutsu on count_sequences(5, 1).

Tällä tavalla toteutettu tehostettu algoritmi on selvästi nopeampi kuin alkuperäinen algoritmi. Esimerkiksi tapauksessa $n=20$ alkuperäinen algoritmi vie aikaa 0.69 sekuntia, kun taas tehostettu algoritmi vie aikaa vain 0.02 sekuntia. Tehostetun algoritmin avulla voidaan laskea tehokkaasti seuraavat tulokset:

Kuitenkin tapauksesta $n=26$ alkaen myös tehostettu algoritmi alkaa hidastua. Tämä on tyypillinen ilmiö raakaan voimaan perustuvissa algoritmeissa: algoritmeja on mahdollista tehostaa eri tavoilla, mutta tehostamisen ansiosta voidaan käsitellä vain hieman suurempia tapauksia kuin aiemmin.

Palaamme tähän tehtävään vielä seuraavassa luvussa, jossa teemme toisenlaisen ratkaisun dynaamisen ohjelmoinnin avulla. Dynaamisen ohjelmoinnin avulla saamme laskettua ratkaisujen määrän silmänräpäyksessä tapauksessa $n=100$.

Ahneet algoritmit

Ahne algoritmi (greedy algorithm) on tehokas menetelmä, jonka avulla optimaalinen ratkaisu ongelmaan voidaan löytää ilman kaikkien ratkaisujen läpikäyntiä. Ahneet algoritmit ovat usein yksinkertaisia, mutta voi olla vaikeaa perustella, miksi ahne algoritmi toimii oikein kaikissa tapauksissa.

Tarkastellaan esimerkkinä seuraavaa tehtävää:

Tehtävä

Voimme ratkaista tehtävän raa’alla voimalla käymällä läpi kaikki mahdolliset kolikoiden yhdistelmät. Seuraava funktio find_coins ilmoittaa, mikä on pienin määrä kolikkoja, joilla voidaan muodostaa summa $x$.

def find_coins(x):
    solutions = [[]]

    for solution in solutions:
        if sum(solution) == x:
            return len(solution)
        for coin in [1, 2, 5]:
            solutions.append(solution + [coin])

Funktio muodostaa listaan solutions kolikoiden yhdistelmiä järjestyksessä kolikoiden määrän mukaan. Kun löytyy ensimmäinen yhdistelmä, jossa kolikoiden summa on $x$, funktio palauttaa tämän yhdistelmän kolikoiden määrän.

Esimerkiksi tapauksessa $x=13$ funktio käy läpi ensin kaikki yhdistelmät, joissa on $1$, $2$ tai $3$ kolikkoa. Missään näistä yhdistelmistä kolikkojen summa ei ole $13$. Tämän jälkeen funktio käy läpi yhdistelmät, joissa on $4$ kolikkoa, ja löytää ratkaisun $[1,2,5,5]$, jossa kolikoiden määrä on $13$. Tämän perusteella pienin mahdollinen kolikoiden määrä on $4$, jonka funktio palauttaa.

Tällainen algoritmi on toimiva, mutta laskenta vie kauan aikaa, jos tarvittava kolikoiden määrä on suuri. Ongelmana on, että funktio käy läpi suuren määrän ratkaisuja, joissa kolikoiden summa ei ole oikea. Esimerkiksi tapaus $x=100$ on jo liian suuri, jotta algoritmi voisi ratkaista sen tehokkaasti.

Tehtävä on mahdollista ratkaista tehokkaammin ahneella algoritmilla, joka käy läpi kolikot suurimmasta pienimpään ja ottaa mukaan kutakin kolikkoa mahdollisimman paljon. Esimerkiksi tapauksessa $x=13$ algoritmi aloittaa kolikosta $5$ ja ottaa kaksi kolikkoa. Tämän jälkeen algoritmi ottaa yhden kolikon $2$ ja vielä yhden kolikon $1$. Tuloksena on optimaalinen yhdistelmä $[1,2,5,5]$.

Seuraava koodi toteuttaa ahneen algoritmin:

def find_coins(x):
    count = 0
    for coin in [5, 2, 1]:
        while coin <= x:
            x -= coin
            count += 1
    return count

Tämä algoritmi on tehokas, koska se ei käy läpi kaikkia yhdistelmiä vaan muodostaa optimaalisen ratkaisun suoraan. Algoritmin avulla voidaan esimerkiksi laskea silmänräpäyksessä, että tapauksessa $x=12345$ pienin kolikoiden määrä on $2469$. Tämän laskeminen ei olisi mitenkään mahdollista raa’an voiman algoritmilla, joka ei selviä edes tapauksesta $x=100$.

Miksi algoritmi toimii?

Ahneen algoritmin suunnittelussa vaikea vaihe on usein perustella, miksi algoritmi antaa oikean vastauksen kaikissa tapauksissa. Ahne algoritmi ei käy läpi kaikkia yhdistelmiä vaan muodostaa vastauksen suoraan, jolloin on riskinä, että se muodostaa ratkaisun, joka ei olekaan optimaalinen.

Miten tiedämme kolikkotehtävässä, että ahne algoritmi muodostaa aina optimaalisen ratkaisun, jossa on pienin mahdollinen määrä kolikkoja?

Äkkiseltään voi vaikuttaa selvältä, että on hyvä strategia valita mahdollisimman suuria kolikkoja, mutta asia ei ole näin yksinkertainen. Jos tehtävää muutetaan hieman niin, että kolikot ovatkin $1$, $4$ ja $5$, ahne algoritmi ei toimi. Tällöin tapauksessa $x=13$ optimaalinen ratkaisu on $[4,4,5]$ (kolme kolikkoa), mutta ahne algoritmi tuottaa ratkaisun $[1,1,1,5,5]$ (viisi kolikkoa). Tässä tilanteessa ahneen algoritmin virhe on valita ratkaisuun toinen kolikko $5$. Ahneen algoritmin toimivuus riippuu siis siitä, mitä kolikkoja summan muodostamiseen voidaan käyttää.

Todistetaan nyt, että ahne algoritmi antaa aina optimaalisen vastauksen, kun kolikot ovat $1$, $2$ ja $5$. Oletetaan, että jäljellä oleva summa on ainakin $5$ ja ratkaisuun ei valita kolikkoa $5$. Tällöin summa täytyy muodostaa kolikoiden $1$ ja $2$ avulla ja kolikkoja tarvitaan ainakin kolme. Kuitenkin jos ratkaisussa on kolme kolikkoa, joista jokainen on $1$ tai $2$, ratkaisu ei ole optimaalinen:

• Jos kolikot ovat $1,1,1$, parempi ratkaisu olisi $1,2$
• Jos kolikot ovat $1,1,2$, parempi ratkaisu olisi $2,2$
• Jos kolikot ovat $1,2,2$, parempi ratkaisu olisi $5$
• Jos kolikot ovat $2,2,2$, parempi ratkaisu olisi $1,5$

Tämä aiheuttaa ristiriidan ja ratkaisuun tulee valita kolikko $5$, eli kolikko $5$ on aina optimaalinen valinta, kun jäljellä oleva summa on ainakin $5$.

Tarkastellaan vielä tilannetta, jossa jäljellä oleva summa on alle $5$ ja ainakin $2$. Tällöin voidaan päätellä vastaavasti, että ratkaisuun tulee valita kolikko $2$. Muuten ratkaisussa olisi ainakin kahdesti kolikko $1$, mikä ei ole optimaalista, koska kaksi kolikkoa $1$ voidaan korvata yhdellä kolikolla $2$. Tämän perusteella algoritmi, joka ottaa kolikoita järjestyksessä $5,2,1$ antaa aina optimaalisen tuloksen.

Algoritmien tutkiminen

Seuraava testiohjelma vertailee raa’an voiman ja ahneen algoritmin antamia tuloksia kolikkotehtävässä. Tarkoituksena on löytää tilanne, jossa ahne algoritmi antaa väärän tuloksen, jos tällainen tilanne on olemassa.

coins = [1, 4, 5]

def find_coins_brute(x):
    solutions = [[]]

    for solution in solutions:
        if sum(solution) == x:
            return len(solution)
        for coin in coins:
            solutions.append(solution + [coin])

def find_coins_greedy(x):
    count = 0
    for coin in reversed(coins):
        while coin <= x:
            x -= coin
            count += 1
    return count

x = 1
while True:
    result_brute = find_coins_brute(x)
    result_greedy = find_coins_greedy(x)

    if result_brute != result_greedy:
        print("different answer for", x, "coins")
        print("brute:", result_brute)
        print("greedy:", result_greedy)
        break

    x += 1

Koodin alussa lista coins määrittelee käytettävissä olevat kolikot. Funktio find_coins_brute etsii vastauksen raa’alla voimalla ja funktio find_coins_greedy etsii vastauksen ahneesti. Ohjelma käy läpi $x$:n arvoja $1,2,3,\dots$ ja ilmoittaa, jos funktiot antavat eri vastauksen jollain arvolla.

Kun kolikot ovat $1,4,5$, ohjelma löytää seuraavan tapauksen:

different answer for 8 coins
brute: 2
greedy: 4

Tämä tarkoittaa, että $x=8$ on pienin tapaus, jossa ahne algoritmi antaa väärän vastauksen, kun kolikot ovat $1,4,5$. Tässä tapauksessa raa’an voiman algoritmin ratkaisu on $[4,4]$, kun taas ahneen algoritmin ratkaisu on $[1,1,1,5]$.