Kaikki materiaali (II-osa)

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]\).

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.

11. Lisää tietorakenteita

Tässä luvussa tutustumme kahteen tietorakenteeseen:

• Pakka (deque): Pakka on listarakenne, jossa alkioiden lisäykset ja poistot ovat tehokkaita sekä listan alussa että lopussa.
• Keko (heap): Keko on tietorakenne, jossa pystyy lisäämään tehokkaasti alkioita sekä etsimään ja poistamaan pienimmän tai suurimman alkion.

Molemmat tietorakenteet ovat saatavilla Pythonin standardikirjastossa, minkä ansiosta niitä voi käyttää kätevästi Python-ohjelmoinnissa.

Pakka

Pythonin tavallisessa listassa on tehokasta lisätä alkio listan loppuun metodilla append sekä poistaa alkio listan lopusta metodilla pop. Kuitenkaan ei ole tehokasta tapaa lisätä tai poistaa alkiota listan alussa.

Pakka (deque) on listarakenne, jossa lisäykset ja poistot ovat tehokkaita sekä listan alussa että lopussa. Pythonissa pakka on saatavilla moduulissa collections tietorakenteena deque, joka tarjoaa seuraavat metodit:

• append: lisää alkio listan loppuun
• pop: poista alkio listan lopusta
• appendleft: lisää alkio listan alkuun
• popleft: poista alkio listan alusta

Tuttujen metodien append ja pop lisäksi pakassa on siis myös metodit appendleft ja popleft, joilla voi lisätä ja poistaa alkion listan alussa. Kaikkien näiden metodien aikavaativuus on \(O(1)\).

Seuraava koodi esittelee pakan käyttämistä:

import collections

items = collections.deque()

items.append(1)
items.append(2)
items.appendleft(3)
items.append(4)
items.appendleft(5)

print(items) # deque([5, 3, 1, 2, 4])

print(items[0]) # 5
print(items[1]) # 3
print(items[-1]) # 4

Pakkaa voi indeksoida samaan tapaan kuin tavallista listaa. Pakan heikkoutena on kuitenkin, että alkion käsittely indeksin perusteella on hidasta. Tavallisessa listassa missä tahansa indeksissä olevaan alkioon pääsee käsiksi ajassa \(O(1)\), mutta pakassa listan keskellä olevan alkion käsittely vie aikaa \(O(n)\).

Pakka on toteutettu Pythonissa linkitettynä listana, minkä ansiosta on mahdollista lisätä ja poistaa alkioita tehokkaasti sekä listan alussa että lopussa.

Pino ja jono

Pino (stack) on tietorakenne, jossa pystyy lisäämään alkion listan loppuun sekä hakemaan tai poistamaan alkion listan lopusta. Jono (queue) on puolestaan tietorakenne, jossa pystyy lisäämään alkion listan loppuun sekä hakemaan tai poistamaan alkion listan alusta.

Pakan avulla pystyy toteuttamaan tehokkaasti sekä pinon että jonon, koska alkioita voi käsitellä tehokkaasti sekä listan alussa että lopussa. Seuraavat luokat Stack ja Queue toteuttavat pinon ja jonon:

import collections

class Stack:
    def __init__(self):
        self.stack = collections.deque()

    def push(self, x):
        self.stack.append(x)

    def top(self):
        return self.stack[-1]

    def pop(self):
        self.stack.pop()

class Queue:
    def __init__(self):
        self.queue = collections.deque()

    def push(self, x):
        self.queue.append(x)

    def top(self):
        return self.queue[0]

    def pop(self):
        self.queue.popleft()

Huomaa, että pinon voi toteuttaa helposti myös Pythonin tavallisen listan avulla, kuten teimme luvussa 6. Sen sijaan jonon toteutuksessa on aitoa hyötyä siitä, että pakkaa pystyy käsittelemään tehokkaasti sekä alussa että lopussa.

Keko

Keko (heap) on tietorakenne, jossa voi lisätä, hakea ja poistaa alkioita. Kekoon voi lisätä alkioita rajoituksetta, mutta siitä voi hakea ja poistaa vain pienimmän tai suurimman alkion, riippuen keon toteutuksesta.

Pythonissa moduuli heapq sisältää funktioita, joiden avulla listaa voi käsitellä kekona:

• heappush: lisää kekoon uusi alkio
• heappop: poista ja palauta keon pienin alkio

Molemmat funktiot toimivat ajassa \(O(\log n)\). Lisäksi listan ensimmäinen alkio on aina keon pienin alkio, joten sen pystyy hakemaan ajassa \(O(1)\).

Seuraava koodi esittelee keon käyttämistä Pythonissa:

import heapq

items = []

heapq.heappush(items, 4)
heapq.heappush(items, 2)
heapq.heappush(items, 3)
heapq.heappush(items, 1)
heapq.heappush(items, 5)

print(items[0]) # 1
heapq.heappop(items)
print(items[0]) # 2

Verrattuna hajautukseen keon etuna on, että siitä pystyy hakemaan ja poistamaan pienimmän tai suurimman alkion tehokkaasti. Hajautuksessa tämä ei ole mahdollista, koska alkioita ei ole järjestetty. Toisaalta keon heikkoutena on, että ei ole mahdollista etsiä keosta tehokkaasti muita kuin pienin tai suurin alkio.

Huomaa, että sama alkio voi esiintyä keossa monta kertaa. Esimerkiksi seuraava koodi lisää kekoon kolmesti luvun \(1\):

import heapq

items = []
heapq.heappush(items, 1)
heapq.heappush(items, 1)
heapq.heappush(items, 1)

print(items) # [1, 1, 1]

Moduulin heapq funktiot pitävät listan alkioita sopivassa järjestyksessä niin, että keon operaatiot pystytään toteuttamaan tehokkaasti.

Esimerkki: Liukuva ikkuna

Tehtävä

Voimme ratkaista tehtävän tehokkaasti keon avulla seuraavasti:

import heapq

def find_minima(items, k):
    n = len(items)
    heap = []
    result = []

    for i in range(n):
        heapq.heappush(heap, (items[i], i))
        while heap[0][1] <= i - k:
            heapq.heappop(heap)
        if i >= k - 1:
            result.append(heap[0][0])

    return result

Tämä algoritmi käy läpi listan ja lisää kekoon alkioita muotoa \((x,i)\): alkio \(x\) on kohdassa \(i\). Keosta voidaan hakea tehokkaasti pienin alkio, joka on kohdassa \(0\). Lisäksi jos havaitaan, että keon pienin alkio on jäänyt listan ulkopuolelle, se poistetaan keosta.

Tuloksena olevan algoritmin aikavaativuus on \(O(n \log n)\), koska jokainen alkio lisätään kekoon ja poistetaan keosta enintään kerran.

Muiden kielten toteutukset

Pakan toteuttamiseen on useita tapoja, ja C++:n ja Javan toteutuksissa myös alkioiden indeksointi on tehokasta. C++:ssa luokka std::deque toteuttaa pakan:

std::deque<int> items;

items.push_back(1);
items.push_back(2);
items.push_front(3);
items.push_back(4);
items.push_front(5);

Javassa on taulukkoon perustuva luokka ArrayDeque:

ArrayDeque<Integer> items = new ArrayDeque<>();

items.addLast(1);
items.addLast(2);
items.addFirst(3);
items.addLast(4);
items.addFirst(5);

Monissa kielissä kekoa käyttävän tietorakenteen nimi on prioriteettijono (priority queue). C++:ssa luokka std::priority_queue toteuttaa maksimikeon:

std::priority_queue<int> items;

items.push(1);
items.push(2);
items.push(3);

cout << items.top() << "\n"; // 3
items.pop();
cout << items.top() << "\n"; // 2

Javassa luokka PriorityQueue toteuttaa minimikeon:

PriorityQueue<Integer> items = new PriorityQueue<>();

items.add(1);
items.add(2);
items.add(3);

System.out.println(items.peek()); // 1
items.poll();
System.out.println(items.peek()); // 2

12. Binäärihakupuu

Binäärihakupuu (binary search tree) on tietorakenne, joka pitää yllä joukkoa alkioista. Sen perustoiminnot ovat samat kuin hajautuksessa: alkioita pystyy lisäämään, etsimään ja poistamaan tehokkaasti.

Binäärihakupuun keskeinen ero hajautukseen verrattuna on, että se säilyttää alkioita suuruusjärjestyksessä. Tämän ansiosta voidaan etsiä esimerkiksi tehokkaasti joukon pienin tai suurin alkio, mikä ei olisi mahdollista hajautuksen avulla.

Pythonin standardikirjastossa ei ole binäärihakupuun toteutusta, minkä vuoksi sen käyttäminen Pythonissa on hankalampaa kuin hajautuksen käyttäminen. Tässä luvussa toteutamme itse binäärihakupuun Pythonilla.

Joukko binääripuuna

Binäärihakupuu on binääripuu, jonka jokaisessa solmussa on yksi joukon alkioista. Esimerkiksi seuraava binäärihakupuu vastaa joukkoa \(\{2,3,5,7,8,9\}\):

Binäärihakupuun alkiot on järjestetty niin, että jokaisessa solmussa kaikki vasemman alipuun alkiot ovat pienempiä kuin solmun alkio ja vastaavasti kaikki oikean alipuun alkiot ovat suurempia kuin alkio. Esimerkiksi yllä olevassa kuvassa juuren vasemman alipuun alkiot \(2\) ja \(3\) ovat pienempiä kuin juuren alkio \(5\). Vastaavasti juuren oikean alipuun alkiot \(7\), \(8\) ja \(9\) ovat suurempia kuin juuren alkio \(5\).

Huomaa, että solmujen sijoittuminen binäärihakupuuhun voidaan valita muuten vapaasti, kunhan äsken mainittu järjestykseen liittyvä ehto pätee. Niinpä on erilaisia tapoja esittää tietty joukko binäärihakupuuna. Esimerkiksi seuraavat kaksi binäärihakupuuta vastaavat molemmat joukkoa \(\{1,2,3,4,5\}\):

Katsotaan seuraavaksi, miten binäärihakupuun avulla voidaan toteuttaa joukkoon liittyviä operaatioita.

Alkion etsiminen

Kun halutaan etsiä joukosta alkiota, lähdetään liikkeelle puun juuresta. Jos solmussa oleva alkio on pienempi kuin etsittävä alkio, siirrytään oikeaan lapseen. Jos solmussa oleva alkio on suurempi kuin etsittävä alkio, siirrytään vasempaan lapseen. Näin jatketaan, kunnes haluttu alkio on löytynyt tai solmulla ei ole lasta, johon tulisi siirtyä. Jälkimmäinen tapaus tarkoittaa, ettei etsittävää alkiota ole joukossa.

Esimerkiksi alkio \(7\) voidaan löytää puusta kulkemalla seuraavaa reittiä:

Alkion etsiminen alkaa juuresta, jossa on alkio \(5\). Koska tämä on pienempi kuin etsittävä alkio \(7\), siirrytään oikeaan lapseen. Tässä solmussa on alkio \(8\), joka on suurempi kuin etsittävä alkio \(7\). Niinpä haku jatkuu vasempaan lapseen, josta löytyy etsittävä alkio \(7\).

Alkion lisääminen

Joukkoon voidaan lisätä alkio etsimällä ensin alkiota joukosta. Jos alkio löytyy, sitä ei lisätä, koska sama alkio voi esiintyä joukossa vain kerran. Jos alkiota ei löydy, puuhun lisätään uusi solmu siihen kohtaan, johon haku olisi edennyt seuraavaksi, ja uusi alkio sijoitetaan siihen.

Esimerkiksi alkio \(4\) voidaan lisätä joukkoon seuraavasti:

Alkion \(4\) etsiminen alkaa juuresta, jossa on alkio \(5\). Tästä siirrytään vasempaan lapseen, jossa on alkio \(3\). Tästä tulisi siirtyä oikeaan lapseen, mutta solmulla ei ole oikeaa lasta. Tämä tarkoittaa, ettei alkiota \(4\) ole vielä puussa ja se tulee lisätä solmun oikeaksi lapseksi. Tämän ansiosta alkio löytyy, kun sitä etsitään myöhemmin.

Pienin alkio

Joukon pienin alkio löytyy lähtemällä liikkeelle juuresta ja etenemällä solmun vasempaan lapseen niin kauan, kuin tämä on mahdollista. Kun tämä ei ole enää mahdollista, pienin alkio on löytynyt.

Suurin alkio

Tässä voidaan menetellä vastaavasti kuin pienimmän alkion etsimisessä, mutta joka vaiheessa siirrytään solmun oikeaan lapseen.

Pienin suurempi alkio

Tavoitteena on löytää pienin alkio, joka on suurempi kuin \(x\). Lähdetään liikkeelle juuresta ja siirrytään vasempaan lapseen aina, kun solmun alkio on suurempi kuin \(x\), ja muuten oikeaan lapseen. Haku päättyy, kun siirtyminen ei ole mahdollista. Haluttu alkio on pienin alkiota \(x\) suurempi alkio kaikista alkioista, joiden kautta reitti kulki.

Suurin pienempi alkio

Tavoitteena on löytää suurin alkio, joka on pienempi kuin \(x\). Tässä voidaan toimia käänteisesti edelliseen kohtaan verrattuna: siirrytään oikeaan lapseen aina, kun solmun alkio on pienempi kuin \(x\). Haluttu alkio on suurin alkiota \(x\) pienempi alkio reitillä olleista alkioista.

Alkion poistaminen

Kun joukosta halutaan poistaa alkio, etsitään ensin alkiota vastaava solmu puusta. Tässä on kolme mahdollista tapausta:

• Solmulla ei ole lapsia. Tällöin solmu voidaan poistaa suoraan puusta.
• Solmulla on yksi lapsi. Tällöin voidaan poistaa solmu puusta ja siirtää sen tilalle solmun ainoa lapsi.
• Solmulla on kaksi lasta. Tällöin etsitään pienin alkiota suurempi alkio ja vaihdetaan keskenään näiden solmujen alkiot. Tämän jälkeen alkio on helppoa poistaa, koska sen solmulla on enintään yksi lapsi.

Seuraava kuva näyttää esimerkin, jossa halutaan poistaa alkio \(5\). Koska alkion \(5\) solmulla on kaksi lasta, vaihdetaan ensin keskenään alkiot \(5\) ja \(7\). Tämän jälkeen alkio \(5\) on helppoa poistaa, koska sillä ei ole lasta.

Huomaa, että kahden lapsen tapauksessa pienimmän alkiota suuremman alkion etsiminen takaa, että uudella solmulla ei voi olla kahta lasta. Niinpä uuden solmun pystyy aina poistamaan helposti.

Toteutus Pythonilla

Aletaan seuraavaksi toteuttaa binäärihakupuuta Pythonilla. Tavoitteena on saada aikaan luokka TreeSet, jota voidaan käyttää seuraavasti:

s = TreeSet()

s.add(1)
s.add(2)
s.add(3)

print(2 in s) # True
print(4 in s) # False

print(s) # [1, 2, 3]

Tässä metodi add lisää alkion joukkoon, operaattori in ilmoittaa, onko alkio joukossa, ja joukon merkkijonoesityksenä on lista sen alkioista.

Seuraava luokka Node sisältää tiedon puussa olevasta solmusta:

class Node:
    def __init__(self, value):
        self.value = value
        self.left = None
        self.right = None

Jokaiseen solmuun liittyy kolme tietoa: solmussa olevan alkion arvo (value) sekä viittaus solmun vasempaan ja oikeaan lapseen (left ja right).

Luokka TreeSet sisältää varsinaisen binäärihakupuun toteutuksen. Tässä on pohja luokalle:

class TreeSet:
    def __init__(self):
        self.root = None

Metodi __init__ luo muuttujan root, jossa on viittaus puun juureen. Alussa puussa ei ole yhtään solmua, minkä vuoksi root on None.

Alkion lisääminen

Seuraava metodi add lisää alkion joukkoon:

    def add(self, value):
        if not self.root:
            self.root = Node(value)
            return

        node = self.root
        while True:
            if node.value == value:
                return
            if node.value > value:
                if not node.left:
                    node.left = Node(value)
                    return
                node = node.left
            else:
                if not node.right:
                    node.right = Node(value)
                    return
                node = node.right

Jos puu on tyhjä, alkio lisätään sen juureksi uuteen solmuun ja metodi päättyy. Muuten metodi etsii paikan alkiolle juuresta alkaen.

Jos solmun alkio on sama kuin lisättävä alkio, metodi päättyy, koska alkio on jo lisätty. Jos solmun alkio on suurempi kuin lisättävä alkio, haku jatkuu vasemmalle, ja jos solmun alkio on pienempi kuin lisättävä alkio, haku jatkuu oikealle. Jos solmulla ei ole lasta, johon haun tulisi jatkua, uusi alkio lisätään kyseiseksi lapseksi ja metodi päättyy.

Alkion etsiminen

Seuraava metodi __contains__ tarkastaa, onko joukossa tiettyä alkiota. Metodia __contains__ kutsutaan, kun koodissa on operaattori in.

    def __contains__(self, value):
        if not self.root:
            return False

        node = self.root
        while node:
            if node.value == value:
                return True
            if node.value > value:
                node = node.left
            else:
                node = node.right

        return False

Jos puu on tyhjä, alkiota ei ole varmasti puussa, ja metodi palauttaa heti False. Muuten metodi etsii alkiota juuresta alkaen samaan tapaan kuin lisäämisessä. Jos alkio löytyy jossain vaiheessa, metodi palauttaa True. Jos haku etenee puun ulkopuolelle, metodi palauttaa lopuksi False.

Merkkijonoesitys

Seuraava metodi __repr__ muodostaa joukon merkkijonoesityksen, joka sisältää joukon alkiot listana.

    def __repr__(self):
        items = []
        self.traverse(self.root, items)
        return str(items)

    def traverse(self, node, items):
        if not node:
            return
        self.traverse(node.left, items)
        items.append(node.value)
        self.traverse(node.right, items)

Metodi __repr__ hyödyntää metodia traverse, joka käy läpi puun alkiot ja lisää ne listalle. Metodi käy ensin läpi vasemman alipuun, lisää sitten solmun alkion listalle ja käy sen jälkeen vielä läpi oikean alipuun. Tämän ansiosta lista sisältää lopuksi joukon alkiot suuruusjärjestyksessä.

Muut operaatiot

Tässä toteutuksessa ei ole vielä metodeja pienimpien ja suurimpien alkioiden etsimiseen eikä alkion poistamiseen. Näiden metodien toteuttaminen kuuluu tämän viikon tehtäviin.

Tasapainoisuus

Binäärihakupuun operaatiot käyvät läpi reittejä puun juuresta puun lehtiin. Tämän vuoksi puun tehokkuus riippuu siitä, miten pitkiä nämä reitit voivat olla. Pisimmän reitin pituus on yhtä suuri kuin puun korkeus \(h\), joten binäärihakupuun operaatioiden tehokkuus voidaan ilmoittaa muodossa \(O(h)\).

Binäärihakupuu ei sellaisenaan ole vielä tehokas tietorakenne, koska puun korkeus saattaa olla suuri. Esimerkiksi jos puuhun lisätään \(n\) alkiota järjestyksessä \(1,2,\dots,n\), kaikki alkiot menevät samaan ketjuun ja puun korkeus on \(n-1\). Tällöin puun operaatiot vievät aikaa \(O(n)\).

Kuitenkin binäärihakupuu voidaan toteuttaa niin, että alkiot jakautuvat tasaisesti puun eri puolille ja puun korkeus on aina luokkaa \(\log n\). Tällöin puun operaatiot toimivat tehokkaasti ja vievät aikaa vain \(O(\log n)\). Tällaista binäärihakupuuta kutsutaan tasapainoiseksi (balanced).

Tasapainoinen binäärihakupuu on toteutettu niin, ettei puun korkeus kasva liian suureksi. Esimerkiksi AVL-puu on tasapainoinen binäärihakupuu, jossa jokaisen solmun vasemman ja oikean alipuun korkeuksien ero saa olla enintään \(1\). Tämän ehdon ansiosta puun korkeus on aina luokkaa \(\log n\). Jotta ehto säilyisi voimassa, puun rakennetta muutetaan tarvittaessa alipuiden kiertojen avulla.

Esimerkki: Hotelli

Seuraavassa on esimerkki tehtävästä, joka voidaan ratkaista tehokkaasti binäärihakupuun avulla:

Tehtävä

Oletetaan, että käytössä on luokka TreeSet, jossa on seuraavat metodit:

• add(x): lisää alkio x joukkoon
• next(x): palauta pienin alkio, joka on suurempi kuin x (tai None jos alkiota ei ole olemassa)
• remove(x): poista alkio x joukosta

Näiden metodien avulla tehtävä voidaan ratkaista seuraavasti:

def find_rooms(sizes, requests):
    rooms = TreeSet()
    counter = 0
    for size in sizes:
        counter += 1
        rooms.add((size, counter))

    result = []
    for request in requests:
        room = rooms.next((request, 0))
        if room == None:
            result.append(0)
        else:
            rooms.remove(room)
            result.append(room[0])

    return result

Funktio luo joukon rooms ja lisää sinne kaikki saatavilla olevat huoneet. Koska usealla huoneella voi olla sama koko mutta joukossa voi esiintyä vain kerran sama alkio, jokainen huone lisätään parina, jossa ensimmäinen alkio on huoneen koko ja toinen alkio on laskurin antama huoneen numero. Esimerkin tapauksessa joukkoon lisätään parit (2, 1), (4, 2), (4, 3) ja (8, 4).

Tämän jälkeen funktio käy läpi ryhmien koot ja lisää listalle result tiedot kunkin ryhmän saaman huoneen koosta. Metodilla next etsitään pienin alkio, joka on suurempi kuin (request, 0). Koska minkään huoneen numero ei ole 0, metodi löytää pienimmän huoneen, jonka koko on ainakin request.

Funktio vie aikaa \(O(n \log n + m \log n)\) olettaen, että binäärihakupuu on tasapainoinen ja sen operaatiot vievät aikaa \(O(\log n)\).

Miksi ei Pythonissa?

Binäärihakupuu on saatavilla valmiina monissa ohjelmointikielissä, mutta se puuttuu Pythonin standardikirjastosta. Miksi näin on?

Syy lienee siinä, että Pythonin kehittäjien näkemyksen mukaan binäärihakupuu ei ole niin usein tarvittava tietorakenne, että sen tulisi olla kielen standardikirjastossa. Pythonissa keskeisessä asemassa ovat hajautukseen perustuvat tietorakenteet (set ja dict), jotka riittävät monissa tapauksissa.

Usein binäärihakupuun sijasta voidaan käyttää juuri hajautusta ja mahdollisesti lisäksi järjestämistä tai kekoa. Monissa tehtävissä yksi mahdollinen tehokas ratkaisu on käyttää binäärihakupuuta, mutta tehtävän voi ratkaista myös jotenkin muulla tavalla tehokkaasti ilman binäärihakupuuta.

Jos kuitenkin Pythonissa tarvitsee binäärihakupuuta, saatavilla on monia valmiita standardikirjaston ulkopuolisia toteutuksia. Näiden käyttäminen voi olla järkevämpää kuin itse toteutetun binäärihakupuun käyttäminen.

Muiden kielten toteutukset

C++:ssa tietorakenteet std::set ja std::map toteuttavat binäärihakupuuhun perustuvan joukon ja hakemiston. Esimerkiksi seuraava koodi luo joukon, lisää sinne funktiolla insert sekä etsii funktiolla upper_bound pienimmän annettua alkiota suuremman alkion.

std::set<int> items;

items.insert(1);
items.insert(3);
items.insert(6);
items.insert(8);

auto it = items.upper_bound(4);
std::cout << *it << "\n"; // 6

Javassa vastaavat tietorakenteet ovat TreeSet ja TreeMap. Esimerkiksi seuraava koodi vastaa äskeistä C++-koodia:

TreeSet<Integer> items = new TreeSet<>();

items.add(1);
items.add(3);
items.add(6);
items.add(8);

int item = items.higher(4);
System.out.println(item); // 6

JavaScript noudattaa Pythonin linjaa siinä, että kielen standardikirjastossa ei ole binäärihakupuun toteutusta.

13. Suunnatut verkot

Tähän mennessä olemme olettaneet, että verkon kaaria voi kulkea molempiin suuntiin eli verkko on suuntaamaton (undirected). Esimerkiksi seuraava verkko on suuntaamaton:

Tässä luvussa tarkastelemme tilannetta, jossa verkko on suunnattu (directed). Tällöin kaarissa on nuolet, jotka osoittavat, kumpaan suuntaan kaarta voi kulkea. Esimerkiksi seuraava verkko on suunnattu:

Suunnattuja verkkoja voi käsitellä melko samalla tavalla kuin suuntaamattomia, mutta kaarten suunnat muuttavat joitakin asioita. Tutustumme tässä luvussa algoritmeihin, jotka liittyvät erityisesti suunnattujen verkkojen käsittelyyn.

Suunnatun verkon esittäminen

Suunnattu verkko voidaan esittää ohjelmoinnissa samaan tapaan vieruslistoina kuin suuntaamaton verkko, mutta kaaret lisätään verkkoon vain toiseen suuntaan. Seuraava luokka soveltuu suunnatun verkon esittämiseen:

class Graph:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in self.nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)

Koska verkko on suunnattu, metodi add_edge lisää solmun a vieruslistalle solmun b, mutta se ei lisää solmun b vieruslistalle solmua a. Vieruslista siis sisältää solmut, joihin pääsee kulkemalla kaarta haluttuun suuntaan.

Nyt äskeinen esimerkkiverkko voidaan luoda näin:

g = Graph([1, 2, 3, 4, 5])

g.add_edge(1, 2)
g.add_edge(2, 4)
g.add_edge(2, 5)
g.add_edge(3, 1)
g.add_edge(4, 1)
g.add_edge(4, 5)

Suunnatun verkon käsittelyyn voidaan käyttää syvyyshakua ja leveyshakua samaan tapaan kuin suuntaamattoman verkon käsittelyyn. Koska kaaret on lisätty vain yhteen suuntaan, haut kulkevat verkossa kaarien suuntien mukaisesti.

Topologinen järjestys

Suunnatun verkon topologinen järjestys (topological sort) on solmujen järjestys, joka toteuttaa seuraavan ehdon: jos solmusta \(a\) pääsee solmuun \(b\), niin solmu \(a\) on ennen solmua \(b\) järjestyksessä.

Tarkastellaan esimerkkinä seuraavaa verkkoa:

Yksi mahdollinen topologinen järjestys tälle verkolle on \([4,1,5,2,3,6]\). Seuraavassa kuvassa verkon solmut on aseteltu topologiseen järjestykseen, jolloin kaikki kaaret kulkevat vasemmalta oikealle.

Topologinen järjestys on mahdollista muodostaa, kun verkossa ei ole sykliä (cycle) eli verkko on syklitön (acyclic). Sykli on verkossa oleva polku, joka palaa takaisin lähtösolmuun. Sykli estää topologisen järjestyksen muodostamisen, koska mikään syklin solmuista ei voi esiintyä ennen muita järjestyksessä.

Suunnatut syklittömät verkot ovat käteviä monissa sovelluksissa. Niistä käytetään joskus englanniksi termiä dag, joka tulee sanoista directed acyclic graph.

Topologisen järjestyksen muodostaminen

Topologinen järjestys voidaan muodostaa suorittamalla verkossa syvyyshakuja. Verkon solmuilla on kolme mahdollista tilaa muodostamisen aikana:

• Tila 0: haku ei ole vielä käynyt solmussa
• Tila 1: solmun käsittely on aloitettu
• Tila 2: solmun käsittely on saatu loppuun

Algoritmin alussa jokaisen solmun tila on 0. Algoritmi käy läpi verkon solmut ja aloittaa syvyyshaun jokaisesta solmusta, jonka tila on 0. Kun haku saapuu solmuun, solmun tilaksi tulee 1. Kun haku on käynyt läpi kaikki solmusta lähtevät kaaret, solmun tilaksi tulee 2.

Algoritmi muodostaa listan, joka sisältää verkon solmut. Kukin solmu lisätään listalle siinä vaiheessa, kun solmun tilaksi tulee 2. Algoritmin päätteeksi tämä lista käännettynä ympäri on yksi verkon topologinen järjestys.

Jos verkossa on sykli, tämä havaitaan algoritmin aikana siitä, että haku päätyy kaarta pitkin solmuun, jonka tilana on 1. Tällöin verkossa on sykli eikä topologisen järjestyksen muodostaminen ole mahdollista.

Seuraavassa on algoritmin toteutus Pythonilla:

class TopologicalSort:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in self.nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def visit(self, node):
        if self.state[node] == 1:
            self.cycle = True
            return
        if self.state[node] == 2:
            return

        self.state[node] = 1
        for next_node in self.graph[node]:
            self.visit(next_node)

        self.state[node] = 2
        self.order.append(node)

    def create(self):
        self.state = {}
        for node in self.nodes:
            self.state[node] = 0

        self.order = []
        self.cycle = False

        for node in self.nodes:
            if self.state[node] == 0:
                self.visit(node)

        if self.cycle:
            return None
        else:
            self.order.reverse()
            return self.order

Algoritmia voidaan käyttää näin:

t = TopologicalSort([1, 2, 3, 4, 5, 6])

t.add_edge(1, 2)
t.add_edge(2, 3)
t.add_edge(3, 6)
t.add_edge(4, 1)
t.add_edge(4, 5)
t.add_edge(5, 2)
t.add_edge(5, 3)

print(t.create()) # [4, 5, 1, 2, 3, 6]

Huomaa, että algoritmin antama topologinen järjestys \([4,5,1,2,3,6]\) on eri kuin aiemmin esimerkkinä ollut topologinen järjestys \([4,1,5,2,3,6]\). Tämä johtuu siitä, että verkolla voi olla useita topologisia järjestyksiä ja algoritmi löytää yhden niistä.

Miksi algoritmi toimii?

Algoritmin toiminnan voi perustella sillä, että kun verkossa on kaari solmusta \(a\) solmuun \(b\), solmun \(a\) tilaksi tulee 2 myöhemmin kuin solmun \(b\) tilaksi tulee 2. Niinpä algoritmi lisää solmun \(a\) listaan myöhemmin kuin solmun \(b\).

Tämän ansiosta kun lista käännetään lopuksi, solmu \(a\) on topologisessa järjestyksessä ennen solmua \(b\). Tämä takaa, että kaikki kaaret kulkevat vasemmalta oikealle topologisessa järjestyksessä.

Jos verkossa on sykli, haku päätyy jossain vaiheessa johonkin syklissä olevista solmuista ja kulkee kaaria eteenpäin niin, että se päätyy uudestaan samaan solmuun. Niinpä algoritmi onnistuu tunnistamaan tilanteen, jossa verkossa on sykli.

Dynaaminen ohjelmointi

Suunnattujen syklittömien verkkojen käsittelyyn voidaan käyttää dynaamista ohjelmointia. Dynaamisella ohjelmoinnilla voidaan vastata esimerkiksi seuraaviin polkuihin liittyviin kysymyksiin:

• Montako erilaista polkua on solmusta \(a\) solmuun \(b\)?
• Mikä on pienin määrä kaaria polulla solmusta \(a\) solmuun \(b\)?
• Mikä on suurin määrä kaaria polulla solmusta \(a\) solmuun \(b\)?

Kun verkossa ei ole syklejä, verkkoa voidaan käsitellä kätevästi dynaamisen ohjelmoinnin avulla. Tarkastellaan esimerkkinä polkujen määrän laskemista seuraavassa verkossa:

Tässä verkossa on \(3\) erilaista polkua solmusta \(4\) solmuun \(3\):

• \(4 \rightarrow 1 \rightarrow 2 \rightarrow 3\)
• \(4 \rightarrow 5 \rightarrow 2 \rightarrow 3\)
• \(4 \rightarrow 5 \rightarrow 3\)

Kun halutaan laskea polut solmusta \(4\) solmuun \(3\), laskenta voidaan jakaa kahteen osaongelmaan:

• Polun ensimmäinen kaari on \(4 \rightarrow 1\). Tässä tapauksessa lasketaan mukaan polut solmusta \(1\) solmuun \(3\).
• Polun ensimmäinen kaari on \(4 \rightarrow 5\). Tässä tapauksessa lasketaan mukaan polut solmusta \(5\) solmuun \(3\).

Solmusta \(1\) on \(1\) polku solmuun \(3\) ja solmusta \(5\) on \(2\) polkua solmuun \(3\), joten polkuja solmusta \(4\) solmuun \(3\) on yhteensä \(1+2=3\).

Yleisemmin kun halutaan laskea polkujen määrä solmusta \(x\) solmuun \(y\), voidaan käydä läpi kaikki solmut, joihin pääsee kaarella solmusta \(x\). Kun lasketaan yhteen kaikissa näissä solmuissa polkujen määrät solmuun \(y\), saadaan tuloksena polkujen määrä solmusta \(x\) solmuun \(y\). Koska verkossa ei ole syklejä, määrät voidaan laskea dynaamisella ohjelmoinnilla.

Seuraava koodi toteuttaa algoritmin Pythonilla:

class CountPaths:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in self.nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)

    def count_from(self, node):
        if node in self.result:
            return self.result[node]

        path_count = 0
        for next_node in self.graph[node]:
            path_count += self.count_from(next_node)

        self.result[node] = path_count
        return path_count

    def count_paths(self, x, y):
        self.result = {y: 1}
        return self.count_from(x)

Algoritmia voidaan käyttää näin:

c = CountPaths([1, 2, 3, 4, 5, 6])

c.add_edge(1, 2)
c.add_edge(2, 3)
c.add_edge(3, 6)
c.add_edge(4, 1)
c.add_edge(4, 5)
c.add_edge(5, 2)
c.add_edge(5, 3)

print(c.count_paths(4, 3)) # 3

Tässä dynaaminen ohjelmointi on toteutettu tallentamalla sanakirjaan result jokaisesta solmusta polkujen määrä kohdesolmuun. Jos polkujen määrä on jo laskettu, sitä ei lasketa uudestaan, minkä ansiosta algoritmi toimii tehokkaasti.

Ongelmien esittäminen verkkoina

Dynaaminen ohjelmointi voidaan yleensäkin nähdä suunnattujen syklittömien verkkojen käsittelynä. Tarkastellaan esimerkkinä seuraavaa tehtävää, joka ratkaistiin dynaamisella ohjelmoinnilla luvussa 10:

Tehtävä

Tämä ongelma voidaan esittää verkkona, jossa jokainen solmu vastaa rahamäärää \(0,1,\dots,x\) ja solmusta \(a\) on kaari solmuun \(b\), jos rahamäärästä \(a\) pääsee yhdellä kolikolla rahamäärään \(b\). Kun kolikot ovat \([1,3,4]\) ja \(x=6\), verkko on seuraava:

Tässä verkossa jokainen polku solmusta \(0\) solmuun \(x\) tarkoittaa yhtä tapaa, miten rahamäärä voidaan muodostaa. Niinpä polkujen määrä solmusta \(0\) solmuun \(x\) on yhtä suuri kuin erilaisten tapojen määrä. Voisimme siis käyttää melkein suoraan äskeistä luokkaa CountPaths tehtävän ratkaisemiseen.

Vahva yhtenäisyys

Suunnatussa verkossa yhtenäisyyden käsite on mutkikkaampi kuin suuntaamattomassa verkossa, koska kahden solmun välillä ei ole välttämättä polkua, vaikka solmut olisivat samassa komponentissa.

Esimerkiksi seuraavassa kuvassa vasemmassa verkossa on polku mistä tahansa solmusta mihin tahansa solmuun, mutta oikeassa verkossa ei ole esimerkiksi polkua solmusta \(2\) solmuun \(1\).

Suunnattu verkko on vahvasti yhtenäinen (strongly connected), jos mistä tahansa solmusta on polku mihin tahansa solmuun. Äskeisessä kuvassa vasen verkko on vahvasti yhtenäinen, kun taas oikea verkko ei ole vahvasti yhtenäinen.

Suunnatun verkon vahvasti yhtenäinen komponentti (strongly connected component) on maksimaalinen joukko solmuja, jossa mistä tahansa solmusta on polku mihin tahansa solmuun. Verkko voidaan jakaa aina vahvasti yhtenäisiin komponentteihin. Tarkastellaan esimerkkinä seuraavaa verkkoa:

Tässä tapauksessa vahvasti yhtenäiset komponentit ovat:

Seuraava kuva esittää vahvasti yhtenäiset komponentit verkkona, jossa jokainen solmu vastaa yhtä komponenttia:

Tässä komponentit ovat \(A=\{1,2\}\), \(B=\{3,6,7\}\), \(C=\{4\}\) ja \(D=\{5\}\).

Tällainen komponenteista muodostuva verkko on aina syklitön ja se tuo näkyviin verkon syvärakenteen eli miten verkossa pystyy liikkumaan solmuista toisiinsa.

Kosarajun algoritmi

Verkon vahvasti yhtenäiset komponentit voidaan etsiä tehokkaasti Kosarajun algoritmilla. Algoritmi etsii komponentit kahdessa vaiheessa, joissa se käy läpi verkon solmut syvyyshaun avulla.

Algoritmin ensimmäinen vaihe luo listan solmuista samalla tavalla kuin topologisen järjestyksen muodostamisessa. Erona on kuitenkin, että algoritmi ei pidä muistissa solmujen tiloja eikä välitä verkossa mahdollisesti olevista sykleistä.

Algoritmin toinen vaihe suoritetaan käänteisessä verkossa, jossa jokaisen kaaren suunta on käänteinen. Algoritmi käy läpi ensimmäisessä vaiheessa muodostetun solmujen listan käänteisessä järjestyksessä ja aloittaa haun jokaisesta solmusta, jota ei ole vielä käsitelty. Jokainen tällainen haku muodostaa yhden vahvasti yhtenäisen komponentin.

Algoritmi voidaan toteuttaa Pythonilla seuraavasti:

class Kosaraju:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in self.nodes}
        self.reverse = {node: [] for node in self.nodes}

    def add_edge(self, a, b):
        self.graph[a].append(b)
        self.reverse[b].append(a)

    def visit(self, node, phase):
        if node in self.visited:
            return
        self.visited.add(node)

        if phase == 1:
            graph = self.graph
        if phase == 2:
            graph = self.reverse

        for next_node in graph[node]:
            self.visit(next_node, phase)

        if phase == 1:
            self.order.append(node)

    def count_components(self):
        self.visited = set()
        self.order = []

        for node in self.nodes:
            self.visit(node, 1)

        self.order.reverse()
        self.visited.clear()

        count = 0
        for node in self.order:
            if node not in self.visited:
                count += 1
                self.visit(node, 2)

        return count

Algoritmia voidaan käyttää näin:

k = Kosaraju([1, 2, 3, 4, 5, 6, 7])

k.add_edge(1, 2)
k.add_edge(1, 4)
k.add_edge(2, 1)
k.add_edge(2, 5)
k.add_edge(3, 2)
k.add_edge(3, 7)
k.add_edge(5, 4)
k.add_edge(6, 3)
k.add_edge(6, 5)
k.add_edge(7, 6)

print(k.count_components()) # 4

Tässä metodi count_components laskee vahvasti yhtenäisten komponenttien määrän. Esimerkkiverkossa metodi löytää \(4\) vahvasti yhtenäistä komponenttia.

Miksi algoritmi toimii?

Kosarajun algoritmin toisessa vaiheessa syvyyshaku lisää vahvasti yhtenäiseen komponenttiin kaikki solmut, joihin pääsee alkusolmusta ja joita ei ole vielä lisätty toiseen komponenttiin. Miten on varmaa, että tuloksena on vahvasti yhtenäinen komponentti eikä siihen tule ylimääräisiä solmuja?

Tarkastellaan jotain alkuperäisen verkon kaarta \(a \rightarrow b\), joka johtaa vahvasti yhtenäisestä komponentista toiseen. Solmun \(b\) komponentin solmut lisätään listalle ennen solmun \(a\) komponentin solmuja, joten käänteisessä verkossa solmun \(a\) komponentin solmut ovat ennen solmun \(b\) komponentin solmuja. Algoritmin toisessa vaiheessa solmun \(a\) komponentti muodostetaan ensin. Koska kaaret on käännetty, kaaresta \(a \rightarrow b\) on tullut kaari \(b \rightarrow a\), minkä ansiosta solmun \(a\) komponentista ei ajauduta solmun \(b\) komponenttiin.

Koska yllä oleva päättely toimii kaikissa kaarissa, jotka johtavat komponentista toiseen, algoritmi muodostaa komponentit oikein eikä niihin tule ylimääräisiä solmuja.

14. Lyhimmät polut

Tässä luvussa tarkastelemme lyhimpien polkujen etsimistä verkossa, joka on painotettu (weighted) eli jokaisella kaarella on paino. Tällaisessa verkossa polun pituus on summa polulla olevien kaarten painoista.

Seuraavassa kuvassa on esimerkki painotetusta verkosta:

Jokaisen kaaren yhteydessä on ilmoitettu kaaren paino. Tässä verkossa esimerkiksi polun \(1 \rightarrow 3 \rightarrow 2\) pituus on \(1+4=5\), koska kaaren \(1 \rightarrow 3\) paino on \(1\) ja kaaren \(3 \rightarrow 2\) paino on \(4\).

Olemme käyttäneet aiemmin leveyshakua verkon lyhimpien polkujen etsimiseen, mutta algoritmi ei sovellu käytettäväksi painotetuissa verkoissa. Tässä luvussa tutustumme kolmeen algoritmiin, joilla voidaan etsiä lyhimpiä polkuja painotetuissa verkoissa.

Bellman-Ford-algoritmi

Bellman-Ford-algoritmi laskee, mikä on etäisyys (eli lyhimmän polun pituus) annetusta alkusolmusta kuhunkin verkon solmuun. Algoritmi pitää yllä kullekin solmulle arviota solmun etäisyydestä. Alussa alkusolmun etäisyys on \(0\) ja jokaisen muun solmun etäisyys on \(\infty\).

Algoritmi muodostuu \(n-1\) kierroksesta, missä \(n\) on verkon solmujen määrä. Jokaisella kierroksella algoritmi käy läpi kaikki verkon kaaret ja koettaa pienentää etäisyyksiä kaarten avulla. Kun algoritmi käsittelee kaaren \(a \rightarrow b\), se tarkastaa, saadaanko kaaren avulla pienempi etäisyys solmun \(a\) kautta solmuun \(b\). Jos etäisyys on pienempi, algoritmi merkitsee muistiin uuden etäisyyden.

Algoritmin suorituksen jälkeen etäisyydet ovat lopullisia ja ne vastaavat lyhimpien polkujen pituuksia alkusolmusta verkon solmuihin.

Bellman-Ford-algoritmi voidaan toteuttaa seuraavasti:

class BellmanFord:
    def __init__(self, nodes):
        self.nodes = nodes
        self.edges = []

    def add_edge(self, node_a, node_b, weight):
        self.edges.append((node_a, node_b, weight))

    def find_distances(self, start_node):
        distances = {}
        for node in self.nodes:
            distances[node] = float("inf")
        distances[start_node] = 0

        num_rounds = len(self.nodes) - 1
        for _ in range(num_rounds):
            for edge in self.edges:
                node_a, node_b, weight = edge
                new_distance = distances[node_a] + weight
                if new_distance < distances[node_b]:
                    distances[node_b] = new_distance

        return distances

Lista nodes sisältää verkon solmut, ja lista edges sisältää verkon kaaret. Sanakirja distances sisältää etäisyydet alkusolmusta verkon solmuihin. Joka kierroksella algoritmi käy läpi listan edges ja koettaa pienentää etäisyyksiä kaarten avulla. Jos uusi etäisyys on pienempi kuin vanha etäisyys, algoritmi päivittää sen sanakirjaan distances.

Seuraava koodi etsii algoritmin avulla etäisyydet solmusta \(1\) alkaen:

b = BellmanFord([1, 2, 3, 4, 5])

b.add_edge(1, 2, 8)
b.add_edge(1, 3, 1)
b.add_edge(2, 5, 5)
b.add_edge(3, 2, 4)
b.add_edge(3, 4, 2)
b.add_edge(4, 2, 1)
b.add_edge(4, 5, 3)

distances = b.find_distances(1)
print(distances) # {1: 0, 2: 4, 3: 1, 4: 3, 5: 6}

Tässä tapauksessa etäisyydet ja niitä vastaavat polut ovat:

Algoritmin tutkiminen

Algoritmin toiminnasta saa paremman kuvan lisäämällä siihen tulostuksen aina, kun algoritmi muuttaa etäisyyttä:

                if new_distance < distances[node_b]:
                    print("update", node_a, node_b, new_distance)
                    distances[node_b] = new_distance

Tämän jälkeen algoritmin tulostus äskeisessä verkossa on seuraava:

update 1 2 8
update 1 3 1
update 2 5 13
update 3 2 5
update 3 4 3
update 4 2 4
update 4 5 6

Tässä jokainen rivi näyttää yhden algoritmin tekemän muutoksen etäisyyksiin. Ensimmäinen muutos on, että solmun \(2\) etäisyydeksi tulee \(8\). Tässä käytetään kaarta \(1 \rightarrow 2\), jonka paino on \(8\). Koska etäisyys solmuun \(1\) on \(0\), tämän kaaren avulla saadaan uusi etäisyys \(8\), joka korvaa vanhan etäisyyden \(\infty\).

Yllä oleva tulostus näyttää myös, miten etäisyys solmuun voi muuttua useita kertoja algoritmin aikana. Esimerkiksi etäisyys solmuun \(2\) on ensin \(\infty\), sitten \(8\) kaaren \(1 \rightarrow 2\) kautta, sitten \(5\) kaaren \(3 \rightarrow 2\) kautta ja lopulta \(4\) kaaren \(4 \rightarrow 2\) kautta.

Algoritmin analyysi

Bellman-Ford-algoritmi on löytänyt ensimmäisen kierroksen jälkeen kaikki lyhimmät polut, joissa on yksi kaari. Toisen kierroksen jälkeen se on löytänyt kaikki lyhimmät polut, joissa on enintään kaksi kaarta. Yleisemmin \(k\) kierroksen jälkeen algoritmi on löytänyt kaikki lyhimmät polut, joissa on enintään \(k\) kaarta.

Kun verkossa on \(n\) solmua, jokaisessa lyhimmässä polussa on enintään \(n-1\) kaarta. Tämä johtuu siitä, että jos polussa olisi \(n\) tai enemmän kaaria, polku kävisi monta kertaa samassa solmussa. Tällainen polku ei kuitenkaan voisi olla lyhin polku, koska ei olisi järkevää käydä samassa solmussa useita kertoja. Niinpä Bellman-Fordin algoritmi on löytänyt \(n-1\) kierroksen jälkeen lyhimmän polun jokaiseen verkon solmuun.

Koska algoritmi suorittaa \(n-1\) kierrosta ja käy läpi jokaisella kierroksella \(m\) kaarta, algoritmin aikavaativuus on \(O(nm)\).

Negatiiviset syklit

Bellman-Ford-algoritmi ei anna mielekästä tulosta, jos verkossa on negatiivinen sykli. Negatiivinen sykli tarkoittaa sykliä, jossa kaarten yhteispaino on negatiivinen. Tällaista sykliä kulkemalla polkuja voi lyhentää loputtomasti, jolloin lyhimmän polun käsite ei ole hyvin määritelty.

Seuraavassa on esimerkki tilanteesta, jossa verkossa on negatiivinen sykli:

b = BellmanFord([1, 2, 3, 4])

b.add_edge(1, 2, 1)
b.add_edge(2, 3, 1)
b.add_edge(3, 2, -2)
b.add_edge(2, 4, 1)

distances = b.find_distances(1)
print(distances) # {1: 0, 2: -2, 3: 0, 4: -1}

Verkossa on kaari \(2 \rightarrow 3\) painolla \(1\) sekä kaari \(3 \rightarrow 2\) painolla \(-2\). Kun kuljetaan näitä kaaria edestakaisin, polun pituus vähenee aina \(1\):llä. Tämän takia polun pituus solmusta \(1\) mihin tahansa muuhun solmuun saadaan miten pieneksi tahansa eikä algoritmi anna mielekästä tulosta.

Bellman-Ford-algoritmin avulla voidaan kuitenkin havaita verkossa oleva negatiivinen sykli. Tämä voidaan tehdä suorittamalla algoritmia \(n\) kierrosta tavallisen \(n-1\) kierroksen sijasta. Jos verkossa on negatiivinen sykli, johon pääsee alkusolmusta, tämän huomaa siitä, että jokin etäisyys muuttuu vielä viimeisellä kierroksella.

Dijkstran algoritmi

Dijkstran algoritmi etsii Bellman-Ford-algoritmin tavoin lyhimmät polut alkusolmusta kaikkiin muihin solmuihin. Dijkstran algoritmin etuna on, että se on selvästi Bellman-Ford-algoritmia tehokkaampi suurilla verkoilla. Algoritmia voidaan käyttää kuitenkin vain silloin, kun verkossa ei ole negatiivisen painoisia kaaria.

Dijkstran algoritmin lähtökohta on sama kuin Bellman-Ford-algoritmilla: jokaisella solmulla on muistissa etäisyys niin, että lähtösolmun etäisyys on \(0\) ja kaikkien muiden solmujen etäisyys on \(\infty\). Tämän jälkeen algoritmi pienentää etäisyyksiä, kunnes jokaisen solmun pienin etäisyys on löytynyt.

Algoritmi ottaa joka vaiheessa käsittelyyn solmun, jossa se ei ole vielä käynyt ja jonka etäisyys on mahdollisimman pieni. Tässä tilanteessa algoritmi on löytänyt kyseisen solmun pienimmän etäisyyden eikä etäisyys enää muutu. Algoritmi käy läpi solmusta lähtevät kaaret ja pienentää niiden avulla etäisyyksiä muihin solmuihin. Tämän jälkeen algoritmi merkitsee solmun käydyksi eikä palaa siihen enää uudestaan.

Kun algoritmi on käynyt läpi kaikki verkon solmut, jokaisen solmun etäisyys vastaa lyhimmän polun pituutta alkusolmusta kyseiseen solmuun.

Dijkstran algoritmi voidaan toteuttaa seuraavasti:

import heapq

class Dijkstra:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {node: [] for node in nodes}

    def add_edge(self, node_a, node_b, weight):
        self.graph[node_a].append((node_b, weight))

    def find_distances(self, start_node):
        distances = {}
        for node in self.nodes:
            distances[node] = float("inf")
        distances[start_node] = 0

        queue = []
        heapq.heappush(queue, (0, start_node))

        visited = set()
        while queue:
            node_a = heapq.heappop(queue)[1]
            if node_a in visited:
                continue
            visited.add(node_a)

            for node_b, weight in self.graph[node_a]:
                new_distance = distances[node_a] + weight
                if new_distance < distances[node_b]:
                    distances[node_b] = new_distance
                    new_pair = (new_distance, node_b)
                    heapq.heappush(queue, new_pair)

        return distances

Verkko on tallennettu vieruslistoina niin, että jokainen vieruslistan alkio on pari, jossa on kaaren kohdesolmu ja paino. Algoritmi muodostaa sanakirjan distances samaan tapaan kuin Bellman-Ford-algoritmi.

Koska algoritmin tulee ottaa käsittelyyn solmu, jonka etäisyys on pienin, algoritmissa on käytössä keko queue, jonka avulla haluttu solmu voidaan löytää tehokkaasti. Keon jokainen alkio on pari, jossa on solmun etäisyys ja solmun tunnus. Algoritmi ottaa keosta käsittelyyn solmun, jonka etäisyys on pienin. Jos algoritmi ei ole vielä käynyt solmussa, se päivittää etäisyyksiä ja lisää päivitetyt solmut kekoon.

Huomaa, että sama solmu saattaa esiintyä keossa useita kertoja eri etäisyyksillä. Tämä ei kuitenkaan haittaa, koska algoritmi käsittelee solmun vain silloin, kun se valitaan ensimmäisen kerran keosta.

Algoritmia voidaan käyttää näin:

d = Dijkstra([1, 2, 3, 4, 5])

d.add_edge(1, 2, 8)
d.add_edge(1, 3, 1)
d.add_edge(2, 5, 5)
d.add_edge(3, 2, 4)
d.add_edge(3, 4, 2)
d.add_edge(4, 2, 1)
d.add_edge(4, 5, 3)

distances = d.find_distances(1)
print(distances) # {1: 0, 2: 4, 3: 1, 4: 3, 5: 6}

Algoritmin analyysi

Dijkstran algoritmi ottaa joka vaiheessa käsittelyyn solmun, jonka etäisyys on mahdollisimman pieni. Tämän jälkeen solmun etäisyys ei enää muutu, koska algoritmi käsittelee jokaisen solmun vain kerran.

Algoritmin toiminta perustuu oletukseen, ettei verkossa ole negatiivisia kaaria. Tällöin pienimmän etäisyyden solmu on turvallinen valinta, koska solmuun ei voi olla lyhempää polkua jonkin toisen vielä käsittelemättömän solmun kautta. Jos tällainen polku olisi, toisen solmun etäisyyden tulisi olla pienempi kuin käsiteltävän solmun etäisyyden, mikä ei ole mahdollista.

Algoritmin aikavaativuus on \(O(n + m \log m)\). Aikavaativuus \(O(n)\) tulee siitä, että algoritmi käy läpi verkon solmut. Aikavaativuus \(O(m \log m)\) puolestaan tulee siitä, että algoritmi laittaa kutakin kaarta kohden enintään yhden alkion kekoon ja poistaa alkion myöhemmin keosta.

Negatiiviset kaaret

Seuraava koodi havainnollistaa, miksi Dijkstran algoritmi ei välttämättä anna oikeaa tulosta, jos verkossa on negatiivinen kaari:

d = Dijkstra([1, 2, 3, 4])

d.add_edge(1, 2, 3)
d.add_edge(2, 3, -4)
d.add_edge(1, 3, 1)
d.add_edge(3, 4, 1)

distances = d.find_distances(1)
print(distances) # [0, 3, -1, 2]

Tässä lyhin polku solmusta \(1\) solmuun \(4\) on \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\), jonka pituus on \(3-4+1=0\). Kuitenkin Dijkstran algoritmi valitsee polun \(1 \rightarrow 3 \rightarrow 4\), jonka pituus on \(2\). Algoritmi antaa väärän tuloksen, koska jälkimmäinen polku näyttää lyhemmältä, kun katsotaan vain kaaria \(1 \rightarrow 2\) ja \(1 \rightarrow 3\). Algoritmi ei pysty ottamaan huomioon, että negatiivinen kaaren paino \(-4\) lyhentää polkua.

Lyhimmän polun muodostaminen

Tähän mennessä olemme käyttäneet Bellman-Ford-algoritmia ja Dijkstran algoritmia etäisyyksien laskemiseen. Algoritmeilla voi kuitenkin myös muodostaa lyhimmän polun alkusolmusta loppusolmuun. Tämän voi tehdä tallentamalla etäisyyden muuttuessa tiedon siitä, minkä kaaren avulla etäisyys muuttui. Tämän jälkeen lyhimmän polun pystyy muodostamaan kulkemalla polun käänteisesti.

Muutetaan esimerkkinä Bellman-Ford-algoritmin toteutusta niin, että se palauttaa etäisyyksien sijasta lyhimmän polun:

    def shortest_path(self, start_node, end_node):
        distances = {}
        for node in self.nodes:
            distances[node] = float("inf")
        distances[start_node] = 0
        previous = {}
        previous[start_node] = None

        for _ in range(len(self.nodes) - 1):
            for edge in self.edges:
                node_a, node_b, weight = edge
                new_distance = distances[node_a] + weight
                if new_distance < distances[node_b]:
                    distances[node_b] = new_distance
                    previous[node_b] = node_a

        if distances[end_node] == float("inf"):
            return None

        path = []
        node = end_node
        while node:
            path.append(node)
            node = previous[node]

        path.reverse()
        return path

Metodi luo sanakirjan previous, johon tallennetaan jokaisesta solmusta edellinen solmu lyhimmällä polulla. Tämän sanakirjan avulla lyhin polku voidaan muodostaa käänteisesti algoritmin suorituksen jälkeen. Metodi muodostaa polun listaan path ja kääntää tämän listan ympäri ennen listan palauttamista.

Seuraava koodi esittelee metodin käyttämistä:

b = BellmanFord([1, 2, 3, 4, 5])

b.add_edge(1, 2, 8)
b.add_edge(1, 3, 1)
b.add_edge(2, 5, 5)
b.add_edge(3, 2, 4)
b.add_edge(3, 4, 2)
b.add_edge(4, 2, 1)
b.add_edge(4, 5, 3)

path = b.shortest_path(1, 5)
print(path) # [1, 3, 4, 5]

Tässä metodi etsii lyhimmän polun solmusta \(1\) solmuun \(5\). Metodin tuloksena on polku \([1,3,4,5]\), jonka pituus on \(6\).

Myös Dijkstran algoritmia voisi muuttaa vastaavalla tavalla niin, että se etsii lyhimmän polun alkusolmusta loppusolmuun.

Floyd-Warshall-algoritmi

Floyd-Warshall-algoritmi etsii etäisyydet verkon kaikkien solmuparien välillä. Toisin kuin muut tämän luvun algoritmit, Floyd-Warshall-algoritmi etsii yhdellä kertaa etäisyydet kaikista solmuista alkaen eikä sille anneta alkusolmua. Algoritmia voidaan käyttää millä tahansa verkolla, kunhan verkossa ei ole negatiivista sykliä.

Algoritmi käsittelee verkkoa vierusmatriisina (adjacency matrix), jossa rivin \(a\) sarakkeessa \(b\) ilmoitetaan kaaren pituus solmusta \(a\) solmuun \(b\). Jos \(a=b\), pituus on \(0\), ja jos verkossa ei ole kaarta solmusta \(a\) solmuun \(b\), pituus on \(\infty\).

Tarkastellaan esimerkkinä seuraavaa verkkoa:

Tämän verkon sisältö voidaan esittää vierusmatriisina seuraavasti:

Esimerkiksi rivin \(3\) sarakkeessa \(2\) on luku \(4\), koska verkossa on solmusta \(3\) solmuun \(2\) kaari, jonka pituus on \(4\).

Floyd-Warhall-algoritmi muodostaa etäisyysmatriisin, jossa rivin \(a\) sarake \(b\) ilmaisee lyhimmän polun pituuden solmusta \(a\) solmuun \(b\). Etäisyysmatriisin pohjana on verkon vierusmatriisi, joka sisältää niiden polkujen pituudet, joissa on enintään yksi kaari.

Algoritmi muodostuu kolmesta sisäkkäisestä silmukasta, joista jokainen käy läpi verkon solmut. Ensimmäinen silmukka valitsee välisolmun \(k\) ja sisemmät silmukat käyvät läpi polkuja, joissa polun osana on solmu \(k\). Jos polun pituus lyhenee kulkemalla solmun \(k\) kautta, algoritmi merkitsee uuden pituuden muistiin.

Algoritmi voidaan toteuttaa seuraavasti:

class FloydWarshall:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {}
        for a in self.nodes:
            for b in self.nodes:
                distance = 0 if a == b else float("inf")
                self.graph[(a, b)] = distance

    def add_edge(self, a, b, w):
        self.graph[(a, b)] = min(self.graph[(a, b)], w)

    def find_distances(self):
        distances = self.graph.copy()

        for k in self.nodes:
            for a in self.nodes:
                for b in self.nodes:
                    distance = min(distances[(a, b)],
                                   distances[(a, k)] +
                                   distances[(k, b)])
                    distances[(a, b)] = distance

        return distances

Sanakirja graph sisältää vierusmatriisin. Alussa etäisyys solmusta \(a\) solmuun \(b\) on \(0\), jos \(a=b\), ja muuten \(\infty\). Kun verkkoon lisätään kaari, sanakirjaan merkitään kaaren paino. Jos sama kaari lisätään monta kertaa eri painoilla, sanakirjaan jää talteen pienin kyseisen kaaren paino.

Metodi find_distances muodostaa etäisyysmatriisin vierusmatriisin perusteella. Metodi muodostuu kolmesta sisäkkäisestä silmukasta, jotka käyvät läpi verkon solmut. Kun välisolmu on \(k\), algoritmi käy läpi tilanteet, jossa polkua solmusta \(a\) solmuun \(b\) voidaan lyhentää kulkemalla solmun \(k\) kautta.

Seuraava koodi testaa algoritmia:

f = FloydWarshall([1, 2, 3, 4, 5])

f.add_edge(1, 2, 8)
f.add_edge(1, 3, 1)
f.add_edge(2, 5, 5)
f.add_edge(3, 2, 4)
f.add_edge(3, 4, 2)
f.add_edge(4, 2, 1)
f.add_edge(4, 5, 3)

distances = f.find_distances()

print(distances[(1, 4)]) # 3
print(distances[(2, 1)]) # inf
print(distances[(3, 5)]) # 5

Tämä tarkoittaa, että etäisyys solmusta \(1\) solmuun \(4\) on \(3\), verkossa ei ole polkua solmusta \(2\) solmuun \(1\) ja etäisyys solmusta \(3\) solmuun \(5\) on \(5\).

Tässä tapauksessa metodin find_distances palauttama etäisyysmatriisi on seuraava:

Algoritmin analyysi

Kun välisolmuna on \(k\), algoritmi muodostaa lyhimmät polut, joissa polun osana on solmu \(k\) ja kaikki muut välisolmut ovat solmuja väliltä \(1 \dots k-1\). Koska \(k\) on vuorollaan \(1,2,\dots,n\), algoritmi saa laskettua lopulta kaikki solmujen etäisyydet verkossa.

Algoritmin aikavaativuus on \(O(n^3)\), koska se muodostuu kolmesta sisäkkäisestä silmukasta, jotka käyvät läpi verkon solmut.

Miten valita algoritmi?

Dijkstran algoritmi on usein hyvä valinta lyhimpien polkujen etsimiseen. Algoritmi on tehokas, ja sovelluksissa voidaan usein olettaa, että verkossa ei ole negatiivisia kaaria. Esimerkiksi jos kaarten painot kuvaavat teiden pituuksia tai yhteyksien hintoja, nämä arvot eivät yleensä voi olla negatiivisia.

Bellman-Ford-algoritmi toimii myös silloin, kun verkossa on negatiivisia kaaria, kunhan verkossa ei ole negatiivista sykliä. Algoritmin huonona puolena on, että se on hidas, jos verkko on suuri. Floyd-Warshall-algoritmi on kätevä silloin, kun halutaan laskea etäisyydet kaikkien solmujen välillä.

15. Komponentit ja virittävät puut

Tähän mennessä olemme käsitelleet verkkoalgoritmeja, jotka laskevat jotain käymällä läpi verkon kaikki solmut ja kaaret. Tällaiset algoritmit ovat kuitenkin hitaita tilanteessa, jossa verkkoon tulee jatkuvasti muutoksia.

Tässä luvussa tutustumme union-find-rakenteeseen, jonka avulla voidaan pitää tehokkaasti yllä tietoa verkon komponenteista, kun verkkoon lisätään kaaria. Voimme esimerkiksi selvittää tehokkaasti, ovatko solmut samassa komponentissa tai montako komponenttia verkossa on.

Tutustumme myös Kruskalin algoritmiin, joka käyttää union-find-rakennetta verkon pienimmän virittävän puun muodostamiseen. Virittävä puu on verkon kaarten osajoukko, joka yhdistää kaikki verkon solmut toisiinsa.

Union-find-rakenne

Union-find-rakenne on tietorakenne, joka pitää yllä kokoelmaa alkioista. Aluksi jokainen alkio on omassa joukossaan, ja joukkoja voidaan yhdistää. Tietorakenne tarjoaa kaksi tehokasta operaatiota:

• Määritä, mihin joukkoon alkio kuuluu
• Yhdistä kaksi joukkoa samaksi joukoksi

Union-find-rakenne on toteutettu niin, että jokaisessa joukossa yksi alkioista on joukon edustaja. Kaikista muista joukon alkioista on viittaus edustajaan suoraan tai muiden alkioiden kautta. Näiden viittausten avulla voidaan selvittää sen joukon edustaja, johon tietty alkio kuuluu.

Tarkastellaan esimerkkinä union-find-rakennetta, joka sisältää alkiot \(1,2,\dots,8\). Seuraavassa kuvassa joukot ovat \(\{1,4\}\), \(\{2,5,6\}\) sekä \(\{3,7,8\}\):

Tässä joukkojen edustajat ovat \(1\), \(5\) ja \(3\). Kaikista muista alkioista päästään viittausten avulla edustajiin. Esimerkiksi alkiosta \(2\) päästään edustajaan polkua \(2 \rightarrow 5\) ja alkiosta \(8\) päästään edustajaan polkua \(8 \rightarrow 7 \rightarrow 3\).

Kaksi alkiota kuuluvat samaan joukkoon, jos niillä on yhteinen edustaja. Esimerkiksi solmut \(2\) ja \(6\) kuuluvat samaan joukkoon, koska molempien joukkojen edustaja on \(5\). Solmut \(2\) ja \(3\) puolestaan kuuluvat eri joukkoihin, koska solmun \(2\) joukon edustaja on \(5\) ja solmun \(3\) joukon edustaja on \(3\).

Kun kaksi joukkoa yhdistetään, toisen joukon edustaja asetetaan viittaamaan toisen joukon edustajaan, josta tulee koko uuden joukon edustaja. Esimerkiksi seuraava kuva näyttää, miten joukot \(\{1,4\}\) ja \(\{2,5,6\}\) voidaan yhdistää:

Tässä joukon \(\{1,4\}\) edustaja \(1\) asetetaan viittaamaan joukon \(\{2,5,6\}\) edustajaan \(5\). Tämän seurauksena syntyy uusi joukko \(\{1,2,4,5,6\}\), jonka edustaja on \(5\). Yhdistämisen jälkeen kaikista uuden joukon alkioista pääsee polkua pitkin joukon edustajaan \(5\). Esimerkiksi alkiosta \(4\) päästään edustajaan polkua \(4 \rightarrow 1 \rightarrow 5\).

Union-find-rakenteen tehokkuus riippuu siitä, miten nopeasti tietyn alkion edustaja voidaan löytää. Mitä lyhempiä viittausten muodostamat polut ovat, sitä tehokkaammin edustajat voidaan löytää. Polkujen pituutta voidaan rajata toteuttamalla joukkojen yhdistämiset niin, että ne eivät tuota pitkiä polkuja.

Kun kaksi joukkoa yhdistetään, on kaksi tapaa valita, kumman joukon edustaja alkaa viitata toisen joukon edustajaan. Tehokkuuden kannalta hyvä valinta on, että pienemmän joukon edustaja alkaa viitata suuremman joukon edustajaan. Tällöin jokaisen polun pituus on luokkaa \(O(\log n)\) ja minkä tahansa solmun edustaja voidaan löytää tehokkaasti.

Union-find-rakenne voidaan toteuttaa seuraavasti:

class UnionFind:
    def __init__(self, nodes):
        self.link = {node: None for node in nodes}
        self.size = {node: 1 for node in nodes}

    def find(self, x):
        while self.link[x]:
            x = self.link[x]
        return x

    def union(self, a, b):
        a = self.find(a)
        b = self.find(b)
        if a == b: return

        if self.size[a] > self.size[b]:
            a, b = b, a
        self.link[a] = b
        self.size[b] += self.size[a]

Sanakirja link ilmoittaa kustakin solmusta, mihin solmuun se viittaa. Jos solmu ei viittaa mihinkään, viittauksen kohdalla on None. Sanakirja size puolestaan kertoo jokaisen joukon edustajasolmulle, kuinka suuri kyseinen joukko on.

Metodi find etsii solmun x edustajan kulkemalla viittausten muodostamaa polkua. Metodi union yhdistää joukot, joihin kuuluvat solmut a ja b. Metodi etsii ensin joukkojen edustajat. Jos solmut ovat jo samassa joukossa, metodi ei tee mitään. Muuten metodi asettaa pienemmän joukon edustajan viittaamaan suuremman joukon edustajaan ja päivittää suuremman joukon edustajaan liittyvän koon.

Seuraava koodi esittelee luokan käyttämistä:

u = UnionFind([1, 2, 3, 4, 5, 6, 7, 8])

u.union(1, 4)
u.union(2, 5)
u.union(5, 6)
u.union(3, 7)
u.union(7, 8)

print(u.find(1)) # 4
print(u.find(2)) # 5
print(u.find(3)) # 7
print(u.find(4)) # 4
print(u.find(5)) # 5
print(u.find(6)) # 5
print(u.find(7)) # 7
print(u.find(8)) # 7

Tässä tapauksessa joukon \(\{1,4\}\) edustaja on \(4\), joukon \(\{2,5,6\}\) edustaja on \(5\) ja joukon \(\{3,7,8\}\) edustaja on \(7\).

Esimerkki: Uudet tiet

Tehtävä

Tehtävä voidaan ratkaista seuraavasti union-find-rakenteen avulla:

class NewRoads:
    def __init__(self, n):
        self.uf = UnionFind(range(1, n + 1))

    def add_road(self, a, b):
        self.uf.union(a, b)

    def has_route(self, a, b):
        return self.uf.find(a) == self.uf.find(b)

Ideana on, että union-find-rakenteen joukot vastaavat verkon komponentteja. Aluksi jokainen alkio on omassa joukossaan, mikä tarkoittaa, että jokainen solmu on omassa komponentissaan.

Metodi add_road kutsuu metodia union, joka yhdistää verkon komponentit. Metodi has_route puolestaan kutsuu kummallekin alkiolle metodia find. Alkiot kuuluvat samaan komponenttiin, jos find antaa niille saman edustajan.

Tässä ratkaisussa kummankin metodin add_road ja has_route aikavaativuus on \(O(\log n)\).

Puut verkoissa

Suuntaamaton verkko on puu (tree), jos verkko on yhtenäinen ja syklitön. Esimerkiksi seuraava verkko on puu:

Toisin kuin aiemmin tällä kurssilla käsitellyissä puissa, tässä tapauksessa puussa ei ole juurta eikä solmuilla ole lapsia eikä vanhempia. Kuitenkin puussa on lehtiä: lehtiä ovat kaikki solmut, joiden aste on \(1\) eli joihin liittyy vain yksi kaari. Esimerkiksi yllä olevassa puussa lehtiä ovat solmut \(1\), \(2\) ja \(5\).

Kun verkko on puu ja siinä on \(n\) solmua, siinä on aina tasan \(n-1\) kaarta. Jos puusta poistetaan kaari, se ei ole enää yhtenäinen. Jos taas puuhun lisätään kaari, se ei ole enää syklitön.

Verkon virittävä puu (spanning tree) on puu, joka sisältää verkon solmut ja jonkin osajoukon sen kaarista. Seuraavassa kuvassa on vasemmalla verkko ja oikealla yksi sen virittävistä puista:

Verkolle voidaan muodostaa yleensä useita erilaisia virittäviä puita, koska on monia tapoja valita kaaria niin, että tuloksena on puu.

Kun verkko on painotettu, virittävän puun paino saadaan laskemalla yhteen puuhun valittujen kaarten painot. Tarkastellaan esimerkkinä seuraavaa kuvaa, jossa on painotettu verkko ja kaksi sen virittävää puuta:

Ensimmäisen virittävän puun paino on \(4+1+2+5=12\), ja toisen virittävän puun paino on \(2+1+2+5=10\).

Tässä tapauksessa toinen virittävä puu on verkon pienin virittävä puu (minimum spanning tree) eli virittävä puu, jonka paino on pienin mahdollinen. Myös pienimmän virittävän puun valintaan voi olla useita mahdollisuuksia.

Kruskalin algoritmi

Kruskalin algoritmi on union-find-rakennetta käyttävä algoritmi, jolla voidaan muodostaa verkon pienin virittävä puu. Algoritmi käy läpi verkon kaaret painojärjestyksessä ja valitsee virittävään puuhun mukaan kaikki kaaret, jotka eivät aiheuta sykliä.

Esimerkiksi äskeisen verkon tapauksessa algoritmi käy läpi kaaret seuraavassa järjestyksessä:

Algoritmi ottaa mukaan puuhun ensin kaaret \(2-3\), \(1-2\) ja \(2-4\). Kaari \(1-3\) ei tule mukaan, koska se aiheuttaisi syklin. Sitten mukaan tulee vielä kaari \(4-5\), jonka lisäämisen jälkeen pienin virittävä puu on valmis.

Jos kahdella kaarella on sama paino, Kruskalin algoritmi voi käsitellä ne kummassa tahansa järjestyksessä.

Kruskalin algoritmi voidaan toteuttaa tehokkaasti union-find-rakenteen avulla, koska sen avulla voidaan tarkastaa, tuleeko kaari lisätä mukaan virittävään puuhun. Jos kaaren päissä olevat solmut ovat eri komponenteissa, kaari lisätään virittävään puuhun eikä se aiheuta sykliä.

Seuraava luokka toteuttaa Kruskalin algoritmin:

class Kruskal:
    def __init__(self, nodes):
        self.nodes = nodes
        self.edges = []

    def add_edge(self, node_a, node_b, weight):
        self.edges.append((node_a, node_b, weight))

    def construct(self):
        self.edges.sort(key=lambda x: x[2])

        uf = UnionFind(self.nodes)
        edges_count = 0
        tree_weight = 0

        for edge in self.edges:
            node_a, node_b, weight = edge
            if uf.find(node_a) != uf.find(node_b):
                uf.union(node_a, node_b)
                edges_count += 1
                tree_weight += weight

        if edges_count != len(self.nodes) - 1:
            return None
        return tree_weight

Metodi construct muodostaa pienimmän virittävän puun ja palauttaa puun painon. Metodi järjestää ensin kaarilistan kaarten painojen mukaan. Tämän jälkeen metodi käy läpi kaaret ja valitsee kaaret puuhun union-find-rakenteen avulla. Kun kaari valitaan puuhun, sen paino lisätään puun painoon.

Virittävä puu on mahdollista muodostaa vain, kun verkko on yhtenäinen. Tämän vuoksi metodi pitää myös kirjaa siitä, montako kaarta on lisätty puuhun. Jos lopussa kaarten määrä on pienempi kuin \(n-1\), verkko ei ole yhtenäinen eikä puuta voinut muodostaa. Tällöin metodi palauttaa arvon None.

Luokkaa voidaan käyttää seuraavasti:

k = Kruskal([1, 2, 3, 4, 5])

k.add_edge(1, 2, 2)
k.add_edge(1, 3, 4)
k.add_edge(2, 3, 1)
k.add_edge(2, 4, 2)
k.add_edge(3, 5, 7)
k.add_edge(4, 5, 5)

print(k.construct()) # 10

Miksi algoritmi toimii?

Kruskalin algoritmi muodostaa virittävän puun ahneesti kaarten painojärjestyksen perusteella. Miksi algoritmi tuottaa varmasti pienimmän virittävän puun?

Tarkastellaan tilannetta, jossa seuraavana järjestyksessä oleva kaari on \(a-b\) ja solmut \(a\) ja \(b\) ovat eri komponenteissa. Jos kaarta \(a-b\) ei valita puuhun, täytyy valita myöhemmin jokin toinen kaari, joka liittää solmut \(a\) ja \(b\) samaan komponenttiin.

Kuitenkin myöhemmin valittu kaari voidaan korvata kaarella \(a-b\) niin, että tuloksena on edelleen virittävä puu. Koska myöhemmin valitun kaaren paino on yhtä suuri tai suurempi kuin kaaren \(a-b\) paino, tämä ei lisää virittävän puun painoa. Niinpä on turvallista valita kaari \(a-b\) puuhun.

Minimointi vs. maksimointi

Verkkojen käsittelyssä minimointi ja maksimointi voivat olla hyvin erilaisia ongelmia. Esimerkiksi lyhin polku kahden verkon solmun välillä voidaan etsiä luvun 14 algoritmeilla, mutta miten voitaisiin löytää pisin polku, joka käy enintään kerran kussakin solmussa?

Mahdollinen tapa etsiä pisin polku olisi muuttaa kaikki kaarten painot negatiivisiksi ja etsiä uudessa verkossa lyhin polku. Tämä ei ole kuitenkaan toimiva tapa, koska uudessa verkossa voisi olla negatiivisia syklejä eivätkä algoritmit pystyisi käsittelemään sitä. Itse asiassa pisimmän polun etsimiseen ei tunneta mitään tehokasta algoritmia.

Virittävien puiden etsimisessä tilanne on kuitenkin toinen, koska suurin virittävä puu (eli virittävä puu, jonka paino on suurin mahdollinen) on helppoa muodostaa muuttamalla kaarten painot negatiivisiksi ja rakentamalla pienin virittävä puu uudessa verkossa. Sama tulos saadaan muuttamalla Kruskalin algoritmia niin, että kaaret käydään läpi käänteisessä painojärjestyksessä.

16. Maksimivirtaus

Tämän luvun tavoitteena on muodostaa suunnatussa verkossa virtaus (flow) alkusolmusta (source) loppusolmuun (sink). Jokaisella verkon kaarella on kapasiteetti (capacity), joka ilmaisee, paljonko virtausta kaaren kautta voi kulkea enintään.

Virtaus tulee muodostaa niin, että alkusolmusta lähtevä virtaus on yhtä suuri kuin loppusolmuun tuleva virtaus, ja kaikissa muissa solmuissa solmuun tuleva virtaus ja solmusta lähtevä virtaus on yhtä suuri. Kaikissa kaarissa virtauksen tulee olla enintään yhtä suuri kuin kaaren kapasiteetin.

Verkon maksimivirtaus (maximum flow) on suurin mahdollinen virtaus. Seuraava kuva näyttää esimerkin maksimivirtauksesta solmusta \(1\) solmuun \(5\).

Tässä merkintä \(x/c\) tarkoittaa, että kaaren kapasiteetti on \(c\) ja siitä on käytetty \(x\). Esimerkiksi kaaren \(1 \rightarrow 2\) kapasiteetti on \(4\) ja koko kapasiteetti on käytetty. Vastaavasti kaaren \(1 \rightarrow 3\) kapasiteetti on \(6\) ja siitä on käytetty \(3\).

Tässä verkossa maksimivirtaus on \(7\), joka on solmusta \(1\) lähtevä virtaus ja solmuun \(5\) tuleva virtaus. Kaikissa muissa solmuissa tuleva ja lähtevä virtaus on sama. Esimerkiksi solmussa \(2\) tuleva virtaus ja lähtevä virtaus on \(4\).

Ford-Fulkerson-algoritmi

Tavallinen tapa muodostaa verkon maksimivirtaus on käyttää Ford-Fulkerson-algoritmia. Siinä verkko esitetään erityisessä muodossa, jossa jokaista kaarta kohden verkkoon lisätään toinen vastakkaiseen suuntaan kulkeva kaari, jonka kapasiteetti on alussa \(0\). Esimerkkiverkossa alkutilanne on seuraava:

Algoritmi lisää verkkoon virtausta etsimällä polkuja alkusolmusta loppusolmuun. Tällaista polkua kutsutaan nimellä täydennyspolku (augmenting path). Alussa virtaus on \(0\), ja virtaus kasvaa algoritmin aikana.

Algoritmi etsii joka vaiheessa täydennyspolun, jossa jokaisen kaaren kapasiteetti on positiivinen. Tällainen polku lisää virtausta \(x\):llä, missä \(x\) on pienin kapasiteetti polulla. Tämän jälkeen algoritmi pienentää jokaisen polun kaaren kapasiteettia \(x\):llä ja kasvattaa jokaisen vastakkaisen kaaren kapasiteettia \(x\):llä.

Algoritmi muodostaa täydennyspolkuja ja lisää virtausta, kunnes polun muodostaminen ei ole enää mahdollista. Kun näin tapahtuu, algoritmi päättyy ja sen muodostama virtaus on verkon maksimivirtaus.

Esimerkkiverkossa maksimivirtaus voidaan muodostaa seuraavasti kahdessa vaiheessa:

Ensimmäisessä vaiheessa algoritmi muodostaa täydennyspolun \(1 \rightarrow 2 \rightarrow 3 \rightarrow 5\). Pienin kapasiteetti polulla on \(4\), joten polku lisää virtausta \(4\):llä. Jokaisen polun kaaren kapasiteetti pienenee \(4\):llä ja jokaisen vastakkaisen kaaren kapasiteetti kasvaa \(4\):llä.

Toisessa vaiheessa algoritmi muodostaa täydennyspolun \(1 \rightarrow 3 \rightarrow 2 \rightarrow 4 \rightarrow 5\). Pienin kapasiteetti tällä polulla on \(3\), joten polku lisää virtausta \(3\):lla. Kaarten kapasiteetit muuttuvat vastaavasti kuin ensimmäisessä vaiheessa.

Huomaa, että toisessa vaiheessa polku kulkee kaarta \(3 \rightarrow 2\), joka on verkkoon lisätty vastakkainen kaari. Tätä kaarta on mahdollista kulkea, koska kaareen tuli kapasiteettia ensimmäisessä vaiheessa. Kulkemalla vastakkaisia kaaria algoritmi pystyy tällä tavalla peruuttamaan aiemmin muodostettua virtausta.

Näiden vaiheiden jälkeen verkossa ei ole mitään täydennyspolkua, jossa jokainen kapasiteetti olisi positiivinen. Tällöin algoritmi pysähtyy ja maksimivirtaus on löytynyt. Tässä tapauksessa maksimivirtaus on \(4+3=7\).

Algoritmin toteutus

Ford-Fulkerson-algoritmi voidaan toteuttaa seuraavasti:

class MaximumFlow:
    def __init__(self, nodes):
        self.nodes = nodes
        self.graph = {}
        for i in self.nodes:
            for j in self.nodes:
                self.graph[(i, j)] = 0

    def add_edge(self, node_a, node_b, capacity):
        self.graph[(node_a, node_b)] += capacity

    def add_flow(self, node, sink, flow):
        if node in self.seen:
            return 0
        self.seen.add(node)
        if node == sink:
            return flow
        for next_node in self.nodes:
            if self.flow[(node, next_node)] > 0:
                new_flow = min(flow, self.flow[(node, next_node)])
                inc = self.add_flow(next_node, sink, new_flow)
                if inc > 0:
                    self.flow[(node, next_node)] -= inc
                    self.flow[(next_node, node)] += inc
                    return inc
        return 0

    def construct(self, source, sink):
        self.flow = self.graph.copy()
        total = 0
        while True:
            self.seen = set()
            add = self.add_flow(source, sink, float("inf"))
            if add == 0:
                break
            total += add
        return total

Tässä toteutuksessa kaarten kapasiteetit tallennetaan matriisiin, jossa on paikka jokaiselle mahdolliselle kaarelle verkossa. Tämän ansiosta verkkoon ei tarvitse lisätä erikseen vastakkaisia kaaria.

Metodi construct muodostaa maksimivirtauksen ja palauttaa sen suuruuden. Metodi add_flow suorittaa syvyyshaun, joka lisää virtausta. Metodi etsii täydennyspolun, jossa jokainen kapasiteetti on positiivinen. Polun löytymisen jälkeen metodi muuttaa kaarten kapasiteetteja. Metodin palautusarvo ilmaisee, paljonko virtaus kasvaa.

Algoritmia voidaan käyttää näin esimerkkiverkossa:

m = MaximumFlow([1, 2, 3, 4, 5])

m.add_edge(1, 2, 4)
m.add_edge(1, 3, 6)
m.add_edge(2, 3, 8)
m.add_edge(2, 4, 3)
m.add_edge(3, 5, 4)
m.add_edge(4, 5, 5)

print(m.construct(1, 5)) # 7

Minimileikkaus

Ford-Fulkerson-algoritmi on ahne algoritmi, koska se muodostaa täydennyspolkuja, kunnes polkua ei voi enää muodostaa. Miten voidaan tietää, että algoritmin tuloksena on maksimivirtaus?

Algoritmin toiminnan ymmärtämistä helpottaa tarkastella asiaa toisen ongelman kautta. Verkon leikkaus (cut) tarkoittaa joukkoa kaaria, joiden poistaminen estää kulkemisen alkusolmusta loppusolmuun. Verkon minimileikkaus (minimum cut) on puolestaan yhteispainoltaan pienin leikkaus.

Tässä on esimerkkiverkon minimileikkaus, joka estää kulkemisen alkusolmusta \(1\) loppusolmuun \(5\):

Tässä tapauksessa minimileikkaus sisältää kaaret \(2 \rightarrow 4\) ja \(3 \rightarrow 5\), joiden yhteispaino on \(3+4=7\). Kun nämä kaaret poistetaan verkosta, siinä ei ole enää polkua alkusolmusta \(1\) loppusolmuun \(5\).

Esimerkkiverkon maksimivirtaus ja minimileikkaus ovat molemmat \(7\), eikä tämä ole sattumaa: maksimivirtaus ja minimileikkaus ovat aina yhtä suuret. Ongelmat siis liittyvät toisiinsa, ja tämän avulla voidaan perustella, miksi Ford-Fulkerson-algoritmi toimii oikein.

Kun verkossa on mikä tahansa leikkaus, joka estää kulkemisen alkusolmusta loppusolmuun, tämä antaa ylärajan verkossa olevan virtauksen suuruudelle. Tämä johtuu siitä, että virtauksen täytyy edetä alkusolmun komponentista loppusolmun komponenttiin. Niinpä verkon virtaus on enintään yhtä suuri kuin verkon leikkaus.

Toisaalta voidaan näyttää, että maksimivirtaus vastaa verkossa olevaa leikkausta. Tämä voidaan havaita tarkastelemalla solmuja, joihin maksimivirtauksen muodostamisen jälkeen päästään alkusolmusta positiivisia kaaria. Esimerkkiverkossa nämä solmut ovat seuraavat:

Kun tarkastellaan näiden solmujen ulkopuolelle johtavia alkuperäisen verkon kaaria, näiden kaarten kapasiteettina täytyy olla \(0\), koska kaaria ei voi enää kulkea. Niinpä kaarten kapasiteetti on käytetty kokonaan ja niiden yhteiskapasiteetti on yhtä suuri kuin verkon maksimivirtaus. Toisaalta kaaret muodostavat myös leikkauksen, koska ne jakavat verkon kahteen osaan.

Koska verkon virtaus on enintään yhtä suuri kuin verkon leikkaus ja tässä tapauksessa on löydetty virtaus, joka on yhtä suuri kuin leikkaus, tämä tarkoittaa, että kyseinen virtaus on maksimivirtaus ja kyseinen leikkaus on minimileikkaus.

Esimerkki: Vankilapako

Tehtävä

Tämä tehtävä voidaan ratkaista muodostamalla verkko, jonka solmut ovat risteyksiä ja kaaret ovat teitä. Valitaan alkusolmuksi vankilan risteys, loppusolmuksi sataman risteys ja jokaisen kaaren painoksi \(1\). Tämän verkon minimileikkaus ilmaisee, mitkä tiet poliisin tulee sulkea.

Tehtävää voisi myös laajentaa niin, että jokaisen tien sulkemisesta aiheutuu tietty haitta ja poliisi haluaa sulkea tiet niin, että yhteishaitta on mahdollisimman pieni. Tällöin haitan voisi esittää antamalla sen kaaren painoksi.

Täydennyspolkujen valinta

Ford-Fulkerson-algoritmin tehokkuus riippuu siitä, millä tavalla täydennyspolut valitaan. Jokainen polku kasvattaa virtausta ainakin \(1\):llä, minkä ansiosta algoritmi muodostaa enintään \(f\) polkua, missä \(f\) on verkon maksimivirtaus.

Yhden polun muodostaminen vie syvyyshaulla aikaa \(O(m)\), missä \(m\) on verkon kaarten määrä, joten algoritmille saadaan aikavaativuus \(O(mf)\).

Joissakin tapauksissa jokainen polku saattaa todella kasvattaa virtausta \(1\):llä, jolloin algoritmi joutuu muodostamaan suuren määrän polkuja. Tällainen tilanne on esimerkiksi seuraavassa verkossa:

Tässä kaaren kapasiteetti \(Z\) on jokin suuri luku. Algoritmi voi päätyä muodostamaan vuorotellen polkuja \(1 \rightarrow 2 \rightarrow 3 \rightarrow 4\) ja \(1 \rightarrow 3 \rightarrow 2 \rightarrow 4\), jotka kääntävät solmujen \(2\) ja \(3\) välisen kaaren suuntaa. Jokainen polku lisää virtausta \(1\):llä. Koska verkon maksimivirtaus on \(2Z\), algoritmi muodostaa yhteensä \(2Z\) polkua, mikä on hidasta.

Tehokkaampi algoritmi saadaan, kun algoritmi valitsee aina polun, jossa kaarten määrä on mahdollisimman pieni. Tämä voidaan toteuttaa etsimällä polku syvyyshaun sijasta leveyshaulla. Tuloksena oleva algoritmi tunnetaan nimellä Edmonds-Karp-algoritmi. Voidaan osoittaa, että tällöin algoritmi muodostaa enintään \(O(nm)\) polkua ja algoritmin aikavaativuus on \(O(nm^2)\).

Yllä olevassa verkossa Edmonds-Karp-algoritmi muodostaa vain kaksi kahden kaaren täydennyspolkua: esimerkiksi ensin \(1 \rightarrow 2 \rightarrow 4\) ja sitten \(1 \rightarrow 3 \rightarrow 4\). Molemmat polut lisäävät virtausta \(Z\):llä, minkä jälkeen algoritmi päättyy.

Maksimiparitus

Tarkastellaan suuntaamatonta verkkoa, joka on kaksijakoinen (bipartite), mikä tarkoittaa, että verkon solmut voidaan jakaa kahteen ryhmään niin, että verkossa on kaaria vain ryhmästä toiseen mutta ei ryhmien sisäisesti.

Verkon maksimiparitus (maximum matching) on suurin mahdollinen kaarten joukko, jossa pätee, että jokainen solmu kuuluu enintään yhteen kaareen. Seuraava kuva näyttää esimerkin kaksijakoisen verkon maksimiparituksesta:

Tässä solmut ovat jakautuneet kahteen ryhmään niin, että toinen ryhmä sisältää solmut \(\{1,2,3,4\}\) ja toinen ryhmä sisältää solmut \(\{5,6,7\}\). Verkon maksimiparitus sisältää \(3\) kaarta, ja se voidaan muodostaa kaarista \(1-6\), \(3-5\) ja \(4-7\).

Kaksijakoisen verkon maksimiparitus voidaan etsiä maksimivirtauksen avulla rakentamalla verkko seuraavasti:

Ideana on muuttaa kaksijakoinen verkko suunnatuksi ja lisätä siihen alkusolmu ja loppusolmu. Alkusolmusta on kaari jokaiseen vasemman ryhmän solmuun ja jokaisesta oikean ryhmän solmusta on kaari loppusolmuun. Lisäksi vasemman ryhmän solmusta on kaari oikean ryhmän solmuun, jos näiden solmujen välillä on kaari alkuperäisessä verkossa. Jokaisen kaaren painona on \(1\).

Tämän verkon maksimivirtaus on yhtä suuri kuin alkuperäisen verkon maksimiparitus. Tämä johtuu siitä, että jokainen virtaukseen kuuluva polku kulkee jonkin alkuperäisen verkon kaaren kautta. Lisäksi kaarten painojen ansiosta jokainen solmu voi kuulua enintään yhteen polkuun.

Esimerkki: Tanssiaiset

Tehtävä

Tämä tehtävä voidaan ratkaista muodostamalla verkko, jossa jokaista opiskelijaa vastaa solmu ja kahden solmun välillä on kaari, jos opiskelijat ovat eri kampuksilta ja suostuvat tanssimaan toistensa kanssa. Tämä verkko on kaksijakoinen, koska kaksi saman kampuksen opiskelijaa ei voi muodostaa tanssiparia.

Koska verkko on kaksijakoinen, sen maksimiparitus eli suurin mahdollinen tanssiparien määrä voidaan löytää maksimivirtauksen avulla lisäämällä verkkoon alkusolmu ja loppusolmu sekä sopivat kaaret.