Sist endret: 23.09.2016  
 

Praksisoppgave - Mumien

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 06.11.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:
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

Mumien

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

Algemannen og Kobra står ved inngangen til en pyramide i Egypt. Steinblokken som sperret for inngangen er sprengt i stykker, og et sett med fotspor størrelse 42 leder innover den støvete, mørke gangen.

I et håp om at festen skulle vare litt lenger, fikk de gamle faraoene mumifisert seg, slik at de skulle ta seg bra ut lengst mulig. Det de ikke tenkte på er at det er fryktelig kjipt å ligge innsnurpet i bandasjer i en steinkiste i tusenvis av år. Denne uken har dr. Gewalt fått den slemme idéen å vekke opp en mumie for å se om han er sinna. Kanskje er han sinna nok til å ødelegge verden.

Algemannen og Kobra lister seg innover gangen med hver sin fakkel. Etter en liten stund finner de en vegg med uthogde tegninger.
- Kobra, dette må være et kart over pyramiden. Du er herved utnevnt til kartleser, sier Algemannen.
- Men jeg kan jo ikke egyptisk, svarer Kobra.
- Det er jo bare tegninger av folk og dyr som gjør sømmelige ting, det kan da umulig være så vanskelig å forstå. Ta det rommet her borte for eksempel, her er det bilder av masse skorpioner. Det kan vel bare bety en ting.
- Skal vi labbe i vei da? ymter Kobra frempå.
- Vent litt. Hva er det som står der nede? Det er bilde av et rynkete fjes, en implikasjonspil, en knapp, enda en implikasjonspil, og noe som ser ut som en eksplosjon. Hva kan det bety montro?
- Kanskje det betyr at andre rynkete skapninger "trykker på knappene" til mumien, og gjør han "glad", foreslår Kobra.
- Hmm, jeg tror nok det er enklere enn som så, Kobra. Det må nok bety at hvis det viser seg at faraoen har blitt rynkete, må noen vennligst trykke på "spreng mumien"-knappen, slik at den stakkars faraoen blir spart for et rynkete liv, forklarer Algemannen.
- Å, nei! Vi har et kjempeproblem!
- Javel?
- Vel, egentlig ikke. Jeg er bare glad i å si akkurat det.
- La oss bruke kartet og finne veien frem til "spreng mumien"-knappen før dr. Gewalt finner mumien.
- Vi trenger vel ikke gå gjennom rommene med slanger og skorpioner, gjør vi det? spør Kobra.
- Nei, vi vil vel ikke skitne til draktene våre, vil vi det? La oss ta veien med høyest mulig sannsylighet for ikke å bli bitt av slanger og skorpioner.

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.