Sist endret: 23.09.2016  
 

Praksisoppgave - Veibygging i Ogligogo 2

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 30.10.2017 15:00

Denne øvingen er ikke laget ferdig ennå.

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
veibygging.py, veibygging_heap.py, veibygging_kruskal.py, veibygging_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
veibygging.py Funksjonen mst(naboliste)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 5

Veibygging i Ogligogo 2

Det er ikke nødvendig å lese historien for å løse oppgaven.

Du har kanskje tenkt, hvis superhelter finnes, hvorfor forhindrer de ikke da flom, jordskjelv og sultkatastrofer, og hvorfor skaper de ikke fred i verden? De gjør faktisk det, men bare til en viss grad. For at superheltene ikke skal ødelegge handelsbalansen, og undergrave sitt eget yrke, har superheltforbundet bestemt at de ikke kan gripe inn i store katastrofer mer en en gang i året. Forbundet tar seg av fordeling av heltene til humanitære formål, og for andre gang har Algemannen og Kobra blitt tildelt veibygging i Ogligogo.

Etter å ha kruset rundt litt rundt i ørkenen i Algobilen, kommer heltene frem til hovedstaden Jokkmokk, hvor de blir tatt imot av presidenten.
- Velkommen til Ogligogo, helter, det er en ære å ta imot dere.
- Takk for invitasjonen, svarer Algemannen og tar presidenten i hånden.

Presidenten forklarer dem at de skal utbedre veiene mellom landsbyene i landet. Sanden på veiene som ble lagt ut i fjor har en tendens til å ødelegge limousinen hans. Dette året skal det legges hele steinblokker i stedet. Kobra tror at det er en umulig oppgave. - Er du sikker på at det finnes store nok steiner? Det kan bli fryktelig dyrt , sier Kobra.
- Jeg har en avtale om levering fra nabolandet, Mipp-Mipp, sier presidenten. Problemet er at prisene er skandaløse for de største steinene.
- Du er sjefen, så hvis du sier stein fra Mipp-mipp, så blir det stein fra Mipp-mipp, avslutter Algemannen. Vi får finne prøve å finne ut hvordan vi får knyttet sammen landet ditt uten å bruke store steiner, så kanskje du klarer å spare inn utgiftene på limousinreperasjoner.

Oppgave

Oppgaven i denne øvingen er å finne den dyreste kanten i et minimalt spenntre (MST) i en graf. Input er en naboliste for en graf, og du skal bygge et minimalt spenntre, og finne prisen på dette. Algoritmene til Prim og Kruskal står henholdsvis på side 570 og 568 i Cormen. Prims er lettest å implementere, og kan skrives med bruk av nabomatrise eller med nabolister og bruk av heap. Det første er enklest.

I input til programmet representerer hver linje nabolisten til noden med samme indeks (0-indeksert) som linjen. Kantene er separart med mellomrom, og hver kant er skrevet som NABO:PRIS. Nabolisten til node 0 vil stå på den første linjen, og være på formen

NABO0:PRIS0 NABO1:PRIS1 ... NABOk:PRISk

Denne grafen er urettet, og input i denne øvingen er slik at hvis det er oppført en kant fra u til v med pris k, er det også oppført en kant fra v til u med pris k. Du kan anta prisene alltid er heltall, og aldri større enn 1E10 - 1 eller mindre enn -1E10 + 1.

Output fra programmet ditt skal være prisen på den dyreste kanten i et minimalt spenntre i grafen.

Rammeverk

from sys import stdin

Inf = float(1e3000)

def mst(nm):
    # SKRIV DIN KODE HER


lines = []
for str in stdin:
    lines.append(str)
n = len(lines)
neighbour_matrix = [None] * n
node = 0
for line in lines:
    neighbour_matrix[node] = [Inf] * n
    for k in line.split():
        data = k.split(':')
        neighbour = int(data[0])
        weight = int(data[1])
        neighbour_matrix[node][neighbour] = weight
    node += 1
print (mst(neighbour_matrix))

Variabelbeskrivelse

Rammeverket i denne oppgaven oppretter variabelen 'nabomatrise'. Gitt input-eksempelet vil nabomatrisa se slik ut: [[inf, 5, 3, 7], [ 5, inf, inf, 1], [ 3, inf, inf, inf], [ 7, 1, inf, inf]] Den er en to-dimensjonal array, hvor nabomatrise[a][b] representerer vekten paa en eventuell kant mellom node a og b. Merk at hvis nabomatrise[a][b] == inf betyr dette at det ikke finnes en kant mellom de to nodene. Denne nabomatrisa blir sendt som parameter til funksjonen 'mst' (der den har navnet 'nm'). Obs: Husk aa returnere vekten til den dyreste kanten i det minimale spenntreet, dvs den kanten i det minimale spenntreet som har storst verdi i nabomatrisa.

Input-eksempel

1:5 2:3 3:7
0:5 3:1
0:3
0:7 1:1

Tilhørende output

5

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.

Godbit

Bit 1: Implementer Prims med både nabomatrise og heap. Generer deg testsett som viser at den ene er raskest på tette grafer, og den andre på spredte garfer. Hint: Denne implementasjonen av heap må være litt spesiell, fordi du underveis må forandre prisen på noder som befinner seg inne i heapen, og flytte disse opp eller ned.

Bit 2: Modifiser rammeverk til å approksimere tetthet for grafen før den leses inn i nabomatrise eller naboliste. Bruk denne approksimasjonen til å bestemme hvordan problemet skal løses.