Kurssiaiheet 10, 11 ja 12¶

Itseopiskelu¶

Viikon aiheet: (i) Graafit (ii) Leveys-ensin-haku (BFS), (iii) Syvyys-ensin-haku (DFS), (iv) Graafien toteuttaminen

Aiheiden opetusvideot ja kalvot:

Kysymys 1

Mitkä seuraavista väitteistä ovat totta?

Jos on reitti solmusta \(x\) solmuun \(y\), niin on olemassa kaari solmusta \(x\) solmuun \(y\).

Jos suuntaamattomassa graafissa on olemassa reitti solmusta \(x\) solmuun \(y\), niin on olemassa myös reitti solmusta \(y\) solmuun \(x\).

Suuntaamattomalla graafilla voi olla silmukka, mutta suunnatulla graafilla ei.

Jos suunnatussa graafissa on olemassa kaari solmusta \(x\) solmuun \(y\), niin kaaren solmusta \(y\) solmuun \(x\) on oltava olemassa.

Jokainen puu on graafi, mutta kaikki graafit eivät ole puita.

Kysymys 2

Mitkä seuraavista väitteistä yhtenäisestä graafista ovat totta?

Yhtenäisessä graafissa on olemassa kaari jokaisesta solmusta \(x\) jokaiseen muuhun solmuun \(y\).

Yhtenäisessä vähintään kahden solmun graafissa jokaiseen solmuun on kytketty vähintään yksi kaari.

Graafissa, joka ei ole yhtenäinen, on olemassa ainakin yksi solmu, johon ei ole kytketty yhtään kaarta.

Jos graafi on yhtenäinen ja ei ole olemassa kaarta solmusta \(x\) solmuun \(y\), niin reitillä solmusta \(x\) solmuun \(y\) on vähintään 2 kaarta.

Kysymys 1

Kun tutkitaan suunnattua graafia, missä seuraavista tilanteista syvyys-ensin-haku (DFS) olisi hyödyllinen?

Kun halutaan löytää kaikki reitit tietystä solmusta toiseen tiettyyn solmuun.

Kun halutaan selvittää, onko suunnatussa graafissa silmukoita vai ei.

Kun halutaan löytää pisin reitti tietystä solmusta toiseen tiettyyn solmuun.

Kun halutaan löytää kaikki tietyn pituiset reitit tietystä solmusta toiseen tiettyyn solmuun.

Kysymys 2

DFS-algoritmissa käytetään pinoa. Oletetaan, että \(x\) ja \(y\) ovat kaksi eri solmua suunnatussa graafissa. Minkä säännön mukaan DFS-pino toimii?

Jos \(x\) on pinon päällimmäinen solmu ja halutaan lisätä pinoon solmu \(y\), \(x\) on ensin poistettava pinosta.

Jos on olemassa kaari solmusta \(x\) solmuun \(y\), niin \(x\) ja \(y\) eivät saa olla pinossa samanaikaisesti.

Jos \(x\) ja \(y\) ovat molemmat pinossa samanaikaisesti ja solmu \(x\) on lisätty pinoon ennen solmua \(y\), niin \(x\) poistetaan pinosta ennen solmua \(y\).

Jos \(x\) ja \(y\) ovat molemmat pinossa samanaikaisesti ja solmu \(x\) on lisätty pinoon ennen solmua \(y\), niin \(y\) poistetaan pinosta ennen solmua \(x\).

Kysymys 1

Oletetaan, että graafi tallennetaan C++:ssa. Oletetaan, että solmun tiedot tallennetaan struct:ssa, jossa solmun naapurisolmut tallennetaan joko vector-säiliössä tai unordered_set-säiliössä. Missä tilanneessa on järkevämpi käyttää unordered_set-säiliötä?

Kun jokaisella graafin solmulla on korkeintaan 1 naapurisolmu ja naapurisolmu ei koskaan muutu.

Kun usein lisätään kaareja graafiin tai poistetaan kaareja graafista.

Kun minkä tahansa solmun naapurisolmut aina käsiteltävä tietyssä järjestyksessä.

Kun jokaiselle solmulle annetaan nimi, joka ei koskaan muutu.

Kysymys 2

Kun tallennetaan graafi C++:ssa, mikä seuraavista väitteistä on totta?

On aina käytettävä STL-kirjaston säiliötä nimeltä std::graph-structure.

On aina oltava mahdollista antaa solmulle väri.

On vain yksi oikea tapa tallentaa solmun naapurisolmut.

Kaikkien solmujen naapurisolmut on tallennettava.

Lisäinformaatiota aiheesta:

Viikko10 - Sanasto

Viikkoharjoitusten palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

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¶

video: Painotetut graafit

C++ koodi

Halvimmat reitit: Dijkstran algoritmi¶

video: Dijkstra

Halvimmat reitit: A-tähti ja heuristiikat¶

video: A-tähti

Graafihakujen tehokkuus¶

video: Graafihakujen tehokkuus

kaikkien videoiden kalvot (sivut 25-42):

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

Kurssiaiheiden palautettavat kotitehtävät¶

Tällä viikolla palautettavat tehtävät

Kurssiaiheet 10, 11 ja 12¶

Kurssiaihe 10¶

Itseopiskelu¶

Graafit¶

Leveys-ensin-haku (BFS)¶

Syvyys-ensin-haku (DFS)¶

Graafien toteuttaminen¶

Viikkoharjoitusten palautettavat kotitehtävät¶

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¶

Kurssiaiheiden palautettavat kotitehtävät¶