Kurssiaiheet 10, 11 ja 12

Kurssiaihe 10

Itseopiskelu

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

Aiheiden opetusvideot ja kalvot:

Graafit

Graafit: video

Leveys-ensin-haku (BFS)

Leveys-ensin-haku: video

Syvyys-ensin-haku (DFS)

Syvyys-ensin-haku: video

Graafien toteuttaminen

Graafien toteuttaminen: video

kaikkien videoiden 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 leveys-ensin-haku (BFS) olisi hyödyllinen?

Kun halutaan löytää lyhyin reitti yhdestä tietystä solmusta kaikkiin muihin solmuihin.

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

Kun halutaan löytää graafin lyhyin silmukka.

Kun halutaan löytää solmu, jolla on eniten naapurisolmuja.

Kysymys 2

Oletetaan, että suunnatulla graafilla on 4 solmua, \(s\), \(a\), \(b\) ja \(c\). Oletetaan myös, että graafilla on kaikki mahdolliset kaaret paitsi 2, kaari solmusta \(s\) solmuun \(a\) ja kaari solmusta \(a\) solmuun \(b\). Mitkä ovat etäisyydet solmusta \(s\) kaikkiin muihin solmuihin?

etäisyydet solmusta \(s\) solmuun \(a\) 2, solmusta \(s\) solmuun \(b\) 2, solmusta \(s\) solmuun \(c\) 1

etäisyydet solmusta \(s\) solmuun \(a\) 1, solmusta \(s\) solmuun \(b\) 2, solmusta \(s\) solmuun \(c\) 1

etäisyydet solmusta \(s\) solmuun \(a\) 2, solmusta \(s\) solmuun \(b\) 1, solmusta \(s\) solmuun \(c\) 2

etäisyydet solmusta \(s\) solmuun \(a\) 2, solmusta \(s\) solmuun \(b\) 1, solmusta \(s\) solmuun \(c\) 1

Kysymys 3

Oletetaan, että BFS-algoritmi aloittaa solmusta \(s\). Oletetaan, että \(x\) on toinen solmu ja on olemassa reitti solmusta \(s\) solmuun \(x\). Miksi BFS-algoritmi määrittää eri värejä solmulle \(x\)?

Se tekee niin seuratakseen, kuinka monta naapurisolmua solmulla \(x\) on.

Se tekee niin seuratakseen, onko reitti solmusta \(s\) solmuun \(x\) löydetty ja onko \(x\) täysin käsitelty.

Se tekee niin varmistaakseen, että kun BFS on lopettanut, kahdella naapurisolmulla ei ole samaa väriä.

Se tekee niin varmistaakseen, että BFS:n käyttämässä jonossa ei ole kahta samanväristä solmua.

Kysymys 4

Oletetaan, että suunnattu graafi syötetään BFS-algoritmiin. Oletetaan myös, että BFS-algoritmi aloittaa solmusta \(s\) ja on olemassa reitti solmusta \(s\) jokaiseen muuhun solmuun. Kun BFS-algoritmi on lopettanut, mitkä seuraavista ovat totta? (Huomaa: useampi kuin yksi väite voi olla totta.)

BFS:n käyttämässä jonossa on kaikki solmut.

BFS:n tuloksista voidaan muodostaa reitti solmusta \(s\) mihin tahansa muuhun solmuun.

BFS varmistaa, että kahdella solmulla ei ole samaa väriä, kun BFS on lopettanut.

BFS on laskenut positiivisen etäisyyden kaikille solmuille lukuunottamatta solmua \(s\).

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

Kysymys 1

Dijkstran algoritmi muistuttaa eniten mitä seuraavista algoritmeista?

syvyys ensin haku

esijärjestyksen läpikäynti

leveys ensin haku

lisäysjärjestäminen

Kysymys 2

Oletetaan, että Dijkstran algoritmi käyttää solmua \(s\) lähtösolmuna. Kun Dijkstran algoritmin prioriteettijonosta poimitaan solmu \(v\), jolla on prioriteetti \(v.prior\), mikä on prioriteetin \(v.prior\) merkitys?

Kaarien lukumäärä sillä reitillä solmusta \(s\) solmuun \(v\), jolla on vähiten kaaria, on \(v.prior\).

Ei ole muuta solmua, johon on olemassa reitti solmusta \(s\), jonka kokonaiskustannus on yhtä suuri kuin \(v.prior\).

On olemassa vain yksi reitti solmusta \(s\) solmuun \(v\), jonka kokonaiskustannus on yhtä suuri kuin \(v.prior\).

Halvimman reitin kokonaiskustannus solmusta \(s\) solmuun \(v\) on \(v.prior\).

Kysymys 3

Oletetaan, että Dijkstran algoritmi käyttää solmua \(s\) lähtösolmuna. Mikä on proseduurin Relax tehtävä?

Kun uusi reitti solmusta \(s\) johonkin toiseen solmuun on löydetty, `` Relax`` tarkistaa, onko tämän uuden reitin kokonaiskustannus pienempi kuin halvimman reitin kokonaiskustannus, joka on tähän mennessä löydetty.

Relax vähentää kaikkien prioriteettijonossa tällä hetkellä olevien solmujen prioriteetteja.

Kun solmu \(x\) on poimittu prioriteettijonosta, Relax poistaa graafista kaikki kaaret, jotka kuuluvat halvimpaan reittiin solmusta \(s\) solmuun \(x\).

Kun graafin kaari kohdataan ensimmäisen kerran, Relax lisää kaaren prioriteettijonoon, jos kaaren paino on pienempi kuin kaikkien muiden prioriteettijonon elementtien prioriteetit.

Kysymys 4

Dijkstran algoritmissa jokaiseen solmuun \(x\) liittyy monia suureita tai muuttujia. Mikä seuraavista ei muutu Dijkstran algoritmin suorittamisen aikana?

solmun \(x\) paikka prioriteettijonossa

solmuun \(x\) liittyvä prioriteetti

solmu, joka tulee välittömästi ennen solmua \(x\) reitillä lähtösolmusta solmuun \(x\)

solmun \(x\) naapurisolmujen lukumäärä

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.

Kysymys 1

Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.

Kysymys 2

Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?

Painotetut graafit

Dijkstran algoritmi

A-tähti algoritmi

Graafihakujen tehokkuus

Kysymys 3

Oliko videoiden sisällössä jotain erityisen vaikeaa? Entä mielenkiintoista? Jotain josta haluaisit oppia lisää?

Lisäinformaatiota aiheesta:

Verkkosivu, jossa voit visualisoida eri graafihakualgoritmien edistymistä

Viikko11 - Sanasto

Kurssiaiheiden palautettavat kotitehtävät

Tällä viikolla palautettavat tehtävät

Palautusta lähetetään...