Sist endret: 23.09.2016  
 

Praksisoppgave - Mumien

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 06.11.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
mumien.py, mumien_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
mumien.py Funksjonen beste_sti(nabomatrise, sannsynlighet)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 0-1-4-5

Oppgave

I denne oppgaven skal du finne den tryggeste veien gjennom en graf. Forskjellen fra et vanlig korteste-vei-problem er at kostnaden ligger i nodene i stedet for på kantene. Hver node har en oppgitt sannsynlighet, og den samlede sannsynligheten for en sti er produktet av sannsynlighetene til nodene den går gjennom. Målet er å finne en sti med høyest mulig sannsynlighet.

Første linje i input til programmet er antall noder i grafen. Neste linje angir sannsynlighetene for hver node som flyttall. Resten av input er linjer med nabolister for hver av nodene. Hvis en node ikke har noen naboer er dette representert ved en blank linje.

Output fra programmet skal være den tryggeste stien gjennom grafen. Nodene i stien skal listes opp i traverseringsrekkefølgen med en bindestrek mellom hver node. Startnode er alltid node 0, og sluttnode er alltid den siste noden. For eksempelet under er den beste stien 0-1-4-5, som gir sannsyligheten 1.0 * 0.9 * 0.8 * 1.0 = 0.720. Hvis det er helt usannsynlig å komme igjennom grafen, uansett hvilken sti man følger, er svaret bare 0.

Merk at også sannsynlighetene til startnoden og sluttnoden kan være mindre enn 1.

labyrint.png

Det er ikke tillatt å bruke den innebygde modulen heapq.

Rammeverk

from sys import stdin, stderr

def best_path(nm, prob):
    # SKRIV DIN KODE HER

n = int(stdin.readline())
probabilities = [float(x) for x in stdin.readline().split()]
neighbour_matrix = []
for line in stdin:
    neighbour_row = [0] * n
    neighbours = [int(neighbour) for neighbour in line.split()]
    for neighbour in neighbours:
        neighbour_row[neighbour] = 1
    neighbour_matrix.append(neighbour_row)
print (best_path(neighbour_matrix, probabilities))

Variabelbeskrivelse

Rammeverket i denne oppgaven gir to variabler. 'Nabomatrise'er en liste bestaaende av n lister med (antall noder) elementer. Elementet paa posisjon 'i' i liste 'j' (i,j < n) forteller oss om det eksisterer en kant fra node nummer 'i' til node nummer 'j'. En kant er representert med et 1-tall. 'Nabomatrise' for eksempelinputet vil bli: [[0, 1, 1, 0, 0, 0], [1, 0, 0, 1, 1, 0], [1, 0, 0, 1, 1, 0], [0, 1, 1, 0, 0, 1], [0, 1, 1, 0, 0, 1], [0, 0, 0, 1, 1, 0]] 'Sannsynligheter' er en liste av lengde n hvor hvert element i listen representerer sannsynligheten i den tilhorende noden. 'Sannsynligheter' for eksempelinputen vil bli: [1.0, 0.9, 0.3, 0.1, 0.8, 1.0]

Input-eksempel

6
1.0 0.9 0.3 0.1 0.8 1.0
1 2
0 3 4
0 3 4
1 2 5
1 2 5
3 4

Tilhørende output

0-1-4-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 Dijkstra med binærheap.

Bit 2: La programmet ditt velge Dijkstra med nabomatrise eller Dijkstra med binærheap ut ifra approksimert tetthet på grafen. (Hvis du har implementert bra med binærheap, er det ikke sikkert dette lønner seg i praksis, siden input er nabolister, og det koster litt å gjøre disse om til en nabomatrise.)

Bit 3: Implementer Dijkstra ved å starte både fra start- og sluttnoden samtidig. Dette vil kunne føre til at en mye mindre del av grafen faktisk undersøkes og kan dermed være raskere i praksis, selvom man ikke har noen garantier.