Kurssiviikko 11

Itseopiskelu¶

Viikon aiheet: (i) Painotetut graafit (ii) Halvimmat reitit: Dijkstran algoritmi (iii) Halvimmat reitit: A-tähti ja heuristiikat (iv) Graafihakujen tehokkuus

Aiheiden opetusvideot ja kalvot:

Painotetut graafit ja niiden toteuttaminen¶

Kysymys 1

Painotettu graafi eroaa tavallisesta graafista siinä, että …

jokaiseen solmuun liittyy paino, jonka merkitys on, kuinka kallista on käydä läpi kyseinen solmu

jokaisella kaarella on paino, ja painoja voidaan käyttää halvimman (tai lyhimmän) reitin etsimiseen jostakin tietystä solmusta johonkin toiseen tiettyyn solmuun

painotetussa graafissa ei saa olla silmukoita

jokaisella solmulla on paino, jonka merkitys on suurin määrä kaaria, jotka voivat tulla kyseiseen solmuun tai poistua siitä

Kysymys 2

Oletetaan, että C++:ssa jokaiselle solmulle \(x\) yhtenäisessä painotetussa graafissa käytämme seuraavaa vektoria naapurisolmujen ja kunkin kaaren painon tallentamiseen.

std::vector< std:pair<Node*,Weight>> to_neighbours;

Oletetaan, että käytämme solmun \(N\) vektoria to_neighbours. Mitä a sisältää sen jälkeen, kun seuraava rivi on laskettu?

auto a = to_neighbours[0].second;

aina nolla

osoitin solmun \(N\) toiseen naapurisolmuun

solmun \(N\) ja sen ensimmäisen naapurisolmun yhdistävän kaaren paino

solmun \(N\) naapurisolmujen lukumäärä, joiden paino on nolla

Dijkstran algoritmi¶

A-tähti algoritmi¶

Kysymys 1

Oletetaan, että on olemassa suunnattu painotettu graafi ja lähtösolmu \(s\). Mikä seuraavista kuvaa yhtä tapaa, jolla A-tähden algoritmi ja Dijkstran algoritmi eroavat toisistaan?

A-tähti löytää kalleimman reitin solmusta \(s\) tiettyyn maalisolmuun, kun taas Dijkstran algoritmi löytää halvimman reitin solmusta \(s\) yhteen tai useampaan muuhun solmuun.

A-tähti löytää halvimman reitin solmusta \(s\) yhteen tiettyyn maalisolmuun. Dijkstran algoritmi voi löytää halvimmat reitit solmusta \(s\) kaikkiin muihin solmuihin.

A-tähti toimii vain, kun syötegraafissa ei ole silmukoita. Dijkstran algoritmilla ei ole tätä rajoitusta.

A-tähti löytää halvimman reitin solmusta \(s\) toiseen maalisolmuun, vaikka tällaista reittiä ei ole olemassa. Dijkstran algoritmi vaatii tällaisen reitin olemassaolon.

Kysymys 2

A-tähti algoritmissa lasketaan jotain, jota ei lasketa Dijkstran algoritmissa. Mikä se on?

A-tähti tarvitsee kaksi prioriteettijonoa: yksi, josta voidaan poimia pienimmän prioriteetin omaava alkio nopeasti, ja toinen, josta voidaan poimia suurimman prioriteetin omaava alkio nopeasti. Dijkstran algoritmi tarvitsee vain yhden prioriteettijonon.

A-tähti algoritmissa lasketaan yläraja kaarien lukumäärälle halvimmalla reitillä lähtösolmusta maalisolmuun. Dijkstran algoritmi ei tarvitse tätä ylärajaa.

A-tähti algoritmissa lasketaan halvimman reitin kustannusten alaraja jostain tietystä solmusta maalisolmuun. Dijkstran algoritmi ei tarvitse tätä alarajaa.

A-tähti algoritmissa lasketaan halvimman reitin kustannusten yläraja jostain tietystä solmusta maalisolmuun. Dijkstran algoritmi ei tarvitse tätä ylärajaa.

Lisäinformaatiota aiheesta:

Verkkosivu, jossa voit visualisoida eri graafihakualgoritmien edistymistä

Viikko11 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiviikko 11¶

Itseopiskelu¶

Painotetut graafit ja niiden toteuttaminen¶

Halvimmat reitit: Dijkstran algoritmi¶

Halvimmat reitit: A-tähti ja heuristiikat¶

Graafihakujen tehokkuus¶

Painotetut graafit ja niiden toteuttaminen¶

Dijkstran algoritmi¶

A-tähti algoritmi¶

Viikkoharjoitusten palautettavat kotitehtävät¶