Datastrukturer & Algoritmer, Datalogi C

Henning Christiansen 14/10-2001

Opgaver til forelÊsningen 15/10-2002

Opgave 14.1 og 14.2 fra bogen side 485

Opgave 1

Give eksempler p situationer i virkelighedens verden, hvor der naturligt optrÊder tÊtte grafer. I bogen hÊvdes det, at algoritmen for at finde korteste vej i en uvÊgtet graf er O(antal-kanter-i-grafen). Bogens algoritme er konstrueret, s den beregner alle korteste veje fra en given startknude og til alle andre knuder i grafen.

Vi er i denne opgave kun interesseret i at finde veje fra en knude A til en anden knude B, og der er nemt at optimere bogens algoritme til dette tilfÊlde: NÂr, blandt de veje algoritmen har konstrueret, der er fundet en vej til B, hopper vi ud.

Beskriv tidsforbruget ved store-O for den reviderede algoritmes gennemsnitlige tidsforbrug i tÊtte og tynde grafer.

Opgave 2

Sp¯rgsmÂl 2.1

Tegn et landkort med h¯jst 10 byer og nogle veje imellem; tag bÂde gamle landeveje, som g indtil byernes centrum og motorveje som gÂr udenom. SÊt nogle sandsynlige afstande p i km. Skriv disse data op i det format som bogens graf-program forventer, og afpr¯v programmet med Dijstras algoritme p eksempler for at f udskrevet kilometerafstande.

Sp¯rgsmÂl 2.2

Nu regner vi ikke i kilometer men i k¯retid. Der regnes med gennemsnitsfart p 100 km/t p motorvej og 60 km/t p landevej. Desuden koster det 10 min ekstra at passere et bycentrum. Skitser hvordan f¯lgende to mÂder at tilpasse programmets opf¯rsel til dette vil kunne foretages:

1. Der Êndres ikke i programmet, men der foretages en oversÊttelse af det oprindelige input, s det afspejler forudsÊtningerne i dette sp¯rgsmÂl (dvs. der konstrueres en ny graf, som s gives til programmet). TÊnk ikke pÂ, hvordan en sÂdan oversÊttelse skal implementeres, kun hvad den skal foretage. Aftest l¯sningsmetoden p dit landkort fra sp¯rgsmÂl 2.1 (evt. blot et udsnit).
2. Antag nu at input og intern reprÊsentation af grafen er stort set uÊndret. Hvordan skal algoritmen Êndres? Det er nok med en skitse, men afteste gerne hvis du har tid.