Sist endret: 23.09.2016  
 

Praksisoppgave - Skumlehulen

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 20.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:
skumlehulen.py, skumlehulen_tweak.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
skumlehulen.py Funksjonen antallIsolerteStier(kapasiteter, startrom utganger)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 2
input_eksempel_02.txt 2

Skumlehulen

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

"Algemannen! Algemannen! Du må våkne!", roper Kobra og haler og drar i en søvndysset superhelt. Kobra er for en gangs skyld den som er tidligst ute av loppekassen og har oppdaget tre brev som har kommet i løpet av natten. Algemannen snur seg langsomt og meddeler hånlig: "Jeg trenger ikke våkne. Som du vet, Kobra, så sover ikke superhelter. Vi er alltid våkne på jakt etter nye eventyr.". Kobra finner dette utsagnet noe usannsynlig, men er mer opptatt av å få fram sitt budskap.

Algemannen blir med ett mer oppmerksom når han får høre hvem de tre brevene er fra. Det er nemlig tre prinsesser som er avsenderne: Den smukke prinsesse Peach av Storbritania, den elegante prinsesse Pomme av Frankrike og deres noe mindre glamorøse norske kollega, prinsesse Pæra. Essensen i de tre brevene er den samme. Av hensyn til travle studenter gjengir vi her derfor bare ett av dem:

 

Kjære Superhelt!

Jeg er stengt inne i en mørk labyrint av dr Gewalt og klarer ikke finne veien ut. Jeg hører det er noen andre som skriker her også. Det høres ut som prinsesse Pomme og prinsesse Peach. Jeg MÅ finne en vei ut, men orker ikke møte på de to snerpete mångo-prinsessene! Kan du hjelpe meg? Vær så snill!

Hilsen
Hennes kongelige høyhet,
Prinsesse Pæra

 

Algemannen føler seg overbevist om at dr Gewalt har gjemt dem i den beryktede "skumlehulen" sin. Der har Kobra og Algemannen vært før og Kobra finner raskt fram et kart de laget den gangen. Heldivis finnes det tre utganger fra hulen. Nå gjenstår det bare å sjekke om alle tre prinsessene kan komme seg ut fortest mulig uten å møte på hverandre.

Oppgave

I denne øvingen får du gitt en graf, et sett med startnoder, og et sett med sluttnoder. Programmet ditt skal finne ut hvor mange stier det går an å lage fra startnodene til sluttnoder uten at disse krysser. En sti fra en startnode kan gå til hvilken som helst sluttnode, men forskjellige stier kan ikke møtes i samme sluttnode. For å finne ut hvor mange stier det kan gå gjennom en graf, må du bruke maks flyt. Siden du i dette problemet har mange startnoder (sources) og mange sluttnoder (sinks), må du lage en super-source med kant til alle startnoder, og en super-sink med kant fra all sluttnodene.

To stier som er innom samme node krysser. Det vil si at du må tilordne en kapasitet til nodene. Dette kan du gjøre ved å splitte nodene. For hver node v, lager du nodene v1 og v2. Så lager du en kant fra v1 til v2. Hvis det går en kant fra u til v, lager du en kant fra u2 til v1, og hvis det går en kant fra v til w, lager du en kant fra v2 til w1. Da vil det ikke kunne gå mer enn en flyt gjennom v. Sett bort fra dette oppfører v1 og v2 seg til sammen som v gjorde i den opprinnelige grafen.

Første linje i input er antall noder, antall startnoder, og antall sluttnoder. Så kommer en linje med alle startnodene, og en linje med alle sluttnodene. Deretter kommer en nabomatrise, hvor "1" betyr at det går en kant, og "0" betyr at det ikke går en kant. Programmet ditt skal skrive ut maksimalt antall stier fra startnoder til sluttnoder uten at noen av dem møtes i noen av nodene.

Rammeverk

from sys import stdin, stderr

# Capacities is the original capacity-matrix, which contains n x n elemensts (where n is the amount of nodes)
# start_room is an array with the indexes to the nodes which corresponds to the start rooms.
# Exits is an array with the indexes to the nodes which corresponds to the exits.

def isolated_paths_count(capacities, start_rooms, exits):
    # You can use the method find_flow_path to simplify the problem
    # SKRIV DIN KODE HER

# Finds a path from the source_node to the drain_node
# with available capacity in a flow-network with flow F and capacity C.
# Returns an array where the first element is the index to omne of the start nodes,
# last element is the index to one of the exits and the elements between
# are the indexes of the nodes along the path, in the correct order.
# Example: A path from the start node 4 to node 3, node 9, node 7 and finally
# to the exit 12 will be represented as [4,3,9,7,12].


def find_flow_path(source, drain, F, C):
    n = len(F)
    discovered = [False] * n
    parent = [None] * len(F)
    queue = [source]
    while queue:
        node = queue.pop(0)
        if node == drain:
            # The drain is found, create an array of passed nodes.
            path = []
            i = node
            while True:
                path.append(i)
                if i == source:
                    break
                i = parent[i]
            path.reverse()
            return path;
        for neighbour in range(n):
            if not discovered[neighbour] and F[node][neighbour] < C[node][neighbour]:
                queue.append(neighbour);
                discovered[neighbour] = True;
                parent[neighbour] = node;
    return None

noder, _, _ = [int(x) for x in stdin.readline().split()]
start_rooms = [int(x) for x in stdin.readline().split()]
exits = [int(x) for x in stdin.readline().split()]
adjacency_matrix = []
for linje in stdin:
    naborad = [int(nabo) for nabo in linje.split()]
    adjacency_matrix.append(naborad)
print(isolated_paths_count(adjacency_matrix, start_rooms, exits))

Variabelbeskrivelse

Rammeverket i denne oppgaven gir tre variabler. 'kapasiteter' er en todimensjonal liste som representerer nabomatrisen til grafen du skal finne stier i. Tallet på posisjon [i,j] indikerer hvor stor kapasitet kanten mellom node i og j har. I denne oppgaven vil disse kun være 1 eller 0, det vil si kant eller ingen kant. For eksempelinputet vil denne matrisen være: [[0, 0, 1, 0, 0, 0], [0, 0, 0, 1, 0, 0], [0, 0, 0, 0, 0, 1], [0, 0, 0, 0, 1, 1], [0, 0, 0, 0, 0, 0], [0, 0, 0, 0, 0, 0]] 'startrom' er en liste over hvilke noder som er startnoder. For eksempelinputet vil denne lista være: [0, 1] 'utganger' er en liste over hvilke noder som er sluttnoder. For eksempelinputet vil denne lista være [4,5] I tillegg gis en funksjon, 'finnFlyststi', som dere kan bruke for å finne flytforøkende stier. Denne tar følgende argumenter: kilde: Indeks til den noden som er kilde (source) i flytnettverket. sluk: Indeks til den noden som er sluk (drain) i flytnettverket. F: En matrise som indikerer flyten som går i flytnettverket. For eksempel vil verdien 2 på posisjon [i, j] si at det for øyeblikket går to flytenheter langs kanten fra i til j. C: En matrise med kapasitetene i flytnettverket. Merk at dette er total kapasitet, ikke residualkapasitet. Funksjonen returnerer en flytforøkende sti, representert som en liste med noder. Hvis en slik sti ikke finnes, returnerer den None i stedet.

Input-eksempel

6 2 2
0 1
4 5
0 0 1 0 0 0
0 0 0 1 0 0
0 0 0 0 0 1
0 0 0 0 1 1
0 0 0 0 0 0
0 0 0 0 0 0

Tilhørende output

2

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