Sist endret: 23.09.2016  
 

Praksisoppgave - Veibygging i Ogligogo 2

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 30.10.2017 15:00

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

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.