5.5 DRILL — Grafalgoritmer i pseudokode: mønstergjenkjenning

Åtte naboer i et gjenbruksnettverk låner
verktøy av hverandre. Låneforholdene går begge veier:

A: B, C
B: A, D
C: A, D, E
D: B, C, F
E: C, F
F: D, E, G
G: F, H
H: G

A vil vite hvor mange hun kan nå med en beskjed som får gå høyst to ledd.

a) Navngi problemet, og si hvilket mønster det hører til.
b) Skriv algoritmen. Oppgi antagelser om representasjon.
c) Kjør den for hånd og oppgi svaret.
d) Oppgi kjøretiden, med størrelsene definert.

Ni sykkelstativ i en bydel er koblet med
sykkelveier. Koblingene går begge veier:

A: B, D
B: A, C, E
C: B, F
D: A, E, G
E: B, D, F, H
F: C, E, I
G: D, H
H: E, G, I
I: F, H

En reparatør står ved A og rekker bare å kjøre to strekninger.

a) Hvor mange stativ utenom A rekker hun?
b) Vis kjøringen som en tabell, med køen for hvert steg.
c) En medstudent svarer: «kjør et fullt bredde-først-søk og tell etterpå
hvilke som har avstand høyst 2». Gir det riktig svar, og hva koster det?
d) Oppgi kjøretiden for din egen løsning.

Fem vaktrom i et sykehus ligger i en rundgang, slik
at hvert rom har nøyaktig to naborom:

A: B, E
B: A, C
C: B, D
D: C, E
E: A, D

En beskjed skal sendes ut lagvis fra A: først til alle som er ett rom unna,
så til alle som er to rom unna, og så videre.

a) Skriv algoritmen som deler rommene inn i lag etter avstand fra A.
b) Kjør den og oppgi lagene.
c) Hvorfor kan ikke dybde-først-søk brukes til dette?
d) Oppgi kjøretid.

Samme sykkelnett som i oppgave 2:

A: B, D
B: A, C, E
C: B, F
D: A, E, G
E: B, D, F, H
F: C, E, I
G: D, H
H: E, G, I
I: F, H

Denne gangen skal du ikke bruke rekursjon.

a) Skriv dybde-først-søk fra én node med en eksplisitt stakk.
b) Kjør den fra A, og vis stakken etter hvert steg.
c) Oppgi besøksrekkefølgen.
d) Oppgi kjøretiden — og forklar hvorfor den er en annen enn for et fullt
dybde-først-søk over hele grafen.

Elleve maskiner i et verksted er koblet sammen med
datakabler. Kablene går begge veier:

A: B
B: A
C: D
D: C, E
E: D
F: G, H
G: F, H
H: F, G
I: J
J: I
K: (ingen)

Driftsavdelingen vil vite hvor mange atskilte nettverk maskinene utgjør, slik
at de kan sette opp én ruter per nettverk.

a) Navngi problemet og skriv algoritmen.
b) Kjør den for hånd, og vis den ytre løkka node for node.
c) Oppgi svaret og kjøretiden.
d) Hva ville svaret vært hvis du glemte den ytre løkka og bare kjørte ett
dybde-først-søk fra A?

Et delt dokumentarkiv har seks mapper. En kobling
betyr at den ene mappen har en snarvei til den andre, og snarveiene virker begge
veier:

A: B, C
B: A, D, E
C: A, F
D: B
E: B
F: C

Rydderutinen skal beholde alt som kan nås fra A og slette resten.

a) Skriv det rekursive dybde-først-søket rydderutinen bruker.
b) Kjør det fra A. Vis kallstakken etter hvert steg.
c) Hvilke mapper slettes, og hva er den største dybden kallstakken når?
d) Hva ville svaret blitt hvis arkivet i stedet hadde sett ut som verkstedet i
oppgave 5, og rot-mengden fortsatt var {A}?

Ni deltakere på et kurs skal deles i to grupper.
Noen par har jobbet sammen før og skal derfor havne i hver sin gruppe. Parene:

A: B, D
B: A, C, E
C: B, F
D: A, E, G
E: B, D, F, H
F: C, E, I
G: D, H
H: E, G, I
I: F, H

a) Navngi problemet og skriv algoritmen.
b) Kjør den fra A, og vis køen for hvert steg.
c) Oppgi de to gruppene, eller si at det er umulig.
d) Oppgi kjøretid, og forklar i én setning hvorfor algoritmen aldri trenger å
prøve seg fram.

Sju vakter skal settes opp i to skift. Sju
par tåler ikke å gå på samme skift:

A: B, C
B: A, D
C: A, D
D: B, C, E
E: D, F, G
F: E, G
G: E, F

a) Er det mulig? Kjør algoritmen og vis hvert steg til svaret er avgjort.
b) Hvis det er umulig: hvilken kant avslører det, og hvorfor er den
uunngåelig?
c) Hva er den minste endringen i konfliktlista som ville gjort oppsettet
mulig?
d) Hva er kjøretiden, og hvor mye av grafen rakk algoritmen å se på før den
svarte?

Sju sportsklubber har avtaler om utlån av
spillere. En avtale X -> Y betyr at X kan låne ut til Y, men ikke omvendt:

A: B
B: C
C: D, F
D: E
E: A
F: G
G: F

a) Hvilke grupper av klubber kan låne spillere til hverandre begge veier,
eventuelt via mellomledd?
b) Hvor få klubber må en spiller starte i for å kunne nå alle sju gjennom en
kjede av utlån?
c) Oppgi kjøretid, og forklar hvorfor den er lavest mulig.

Merk: i denne oppgaven skal du svare uten pseudokode, i klar prosa. Det er
en tillatt svarform, og fasiten viser hvordan den ser ut når den gir full
uttelling.

Ni artikler på et nettsted lenker til
hverandre. Lenkene går én vei:

A: B
B: C
C: B, D
D: A, E
E: F
F: G
G: E
H: D, I
I: H

a) Finn gruppene der alle artiklene når hverandre begge veier.
b) Hvor få artikler må forsiden lenke til for at en leser skal kunne nå alle
ni?
c) Fra hvilke artikler når man alle de andre, og fra hvilke når man færrest?
d) Skriv algoritmen som besvarer b), og oppgi kjøretid.

Ni tjenester i et driftssystem varsler
hverandre. En kant X -> Y betyr at X sender varsel videre til Y:

A: B
B: C
C: A, G
D: A, E
E: F
F: D, I
G: H
H: C
I: (ingen)

a) Finn gruppene der varsler kan gå rundt og tilbake.
b) Hvor få tjenester må et varsel settes i gang fra for å nå alle ni?
c) Hvilke grupper sender ikke varsel videre til noen andre gruppe?
d) En besvarelse svarer på b) med «to — det er to grupper som ikke sender
videre». Hva er galt, og hva koster feilen?

En oppgave lyder: «Gitt en rettet graf av
nettsider med lenker. Skriv en algoritme som avgjør om det finnes en side som kan
nå alle de andre. Oppgi kjøretid.» En besvarelse har levert dette:

Procedure Finn(G)
  for hver node v i G:
      lag et nytt sett S
      gjoer et soek fra v og legg alt du finner i S
      hvis alt som ikke er v ligger i S og ogsaa v selv ligger der
      eller v ikke ligger der men alle andre gjoer det
      saa er v et svar og vi kan returnere v med en gang
      ellers gaar vi videre til neste v
  det finnes ikke noe svar
  Kjoeretid: O(|V| + |E|)

a) Er algoritmen riktig?
b) Er kjøretiden riktig oppgitt? Regn den ut.
c) Hvor står besvarelsen i poengtrappen, og hvorfor?
d) Skriv en løsning som står øverst i trappen. Navngi problemet, oppgi
antagelser og kjøretid.