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

Halvimmat reitit: Dijkstran algoritmi

Halvimmat reitit: A-tähti ja heuristiikat

Painotetut graafit ja niiden toteuttaminen

Painotettu graafi eroaa tavallisesta graafista siinä, että …

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;

Dijkstran algoritmi

Dijkstran algoritmi muistuttaa eniten mitä seuraavista algoritmeista?
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?
Oletetaan, että Dijkstran algoritmi käyttää solmua \(s\) lähtösolmuna. Mikä on proseduurin Relax tehtävä?
Dijkstran algoritmissa jokaiseen solmuun \(x\) liittyy monia suureita tai muuttujia. Mikä seuraavista ei muutu Dijkstran algoritmin suorittamisen aikana?

A-tähti algoritmi

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 algoritmissa lasketaan jotain, jota ei lasketa Dijkstran algoritmissa. Mikä se on?
Muotoile kurssin kannalta keskeinen kysymys, johon tämän viikon videot antavat vastauksen.
Minkä videon aiheesta pitäisi erityisesti keskustella keskustelutilaisuudessa?
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

Viikkoharjoitusten palautettavat kotitehtävät

Tällä viikolla palautettavat tehtävät