TDT4120: Algoritmer og datastrukturer
Denne siden baserer seg på mine tanker og tolkninger av emnet Algoritmer og datatrukturer. Informasjonen presentert på denne siden baserer seg på forelesninger på NTNU, samtaler med medstudenter, mange youtube-videoer og Introduction to Algorithms, fourth edition; av Cormen Thomas og H. Leiserson Charles E.
Emnebeskrivelse
Algdat går ut på å forstå algoritmer, både hvordan man designer og analyserer dem. Dette kan virke som et overveldende fag, med mange problemer som ligner på IQ-tester. Det som fungerte for meg var å gå nøye igjennom øvingene (mange av oppgavene er eksamens-oppgaver), samt sitte mye hos studass. Det er mye som skal læres, men det viktigste er å ha oversikt over de kjente algoritmene og metodene.
Temaer
Dette forventes at du kan fra før
Monotone funksjoner
En funksjon f(n) er monoton økende dersom m ≤ n impliserer f(m) ≤ f(n).
En funksjon f(n) er monoton synkende dersom m ≤ n impliserer f(m) ≥ f(n).
En funksjon er strengt økende derom m < n impliserer f(m) < f(n).
En funksjon strengt synkende dersom m < n impliserer f(m) > f(n).
Modulær aritmetikk
I modulær aritmetikk er nøkkelbegrepet “modulus”, som er det positive heltallet som vi deler andre tall med. Det er vanlig å representere modulær aritmetikk med symbolet “mod” eller “%”
a mod n gir os restene av a/n.
a mod n = a-n ⌊a/n⌋
Eksempel:
5 mod 3 = 2
29 mod 4 = 1
Hvis a mod n = b mod n => a=b (mod n)
Modulær aritmetikk
I modulær aritmetikk er nøkkelbegrepet “modulus”, som er det positive heltallet som vi deler andre tall med. Det er vanlig å representere modulær aritmetikk med symbolet “mod” eller “%”
a mod n gir os restene av a/n.
a mod n = a-n ⌊a/n⌋
Eksempel:
5 mod 3 = 2
29 mod 4 = 1
Hvis a mod n = b mod n => a=b (mod n)
Eksponenter
a0 = 1
a1 = a
a-1 = 1/a
(am)n = am*n
(am)*(an)= am+n
lim (a->∞) (nb)/(an) = 0
Floors og ceilings
Gulvet og taket til et tall er matematiske funksjoner som hjelper med å avrunde et tall til nærmeste heltall på forskjellige måter:
Gulvfunksjon (⌊x⌋):
– Gulvet til et tall ⌊x⌋, også kjent som avrundingsfunksjonen mot ned, gir det største heltallet som er mindre enn eller lik det gitte tallet x.
– For eksempel, ⌊3.7⌋ = 3 og ⌊4.2⌋ = 4.
Takfunksjon (⌈x⌉):
– Taket til et tall ⌈x⌉, også kjent som avrundingsfunksjonen mot opp, gir det minste heltallet som er større enn eller lik det gitte tallet x.
– For eksempel, ⌈3.7⌉ = 4 og ⌈4.2⌉ = 5.
Disse funksjonene følger noen regler:
⌊n⌋ = n = ⌈n⌉
Logaritmer
Fakultet
n! = 1*2*3…*n-1*n
Stirlings approximation
Introduksjon, algoritmer, problemer og kjøretid
En algoritme er en veldefinert prosedyre som tar en mengde med verdier som input, og skaper noen verdier som output i en viss tidsperiode. En algoritme en en sekvens med steg som transformerer input til output.
Det er også et redskap for å løse en kjent problem. Et problem er en relasjon mellom input og output.
Eksempel på et kjent problem er sorting problem, altså å sortere en sekvens med tall.
En instans av et problem er inputen.
Datastrukturer er en måte å lagre og organisere data, som gjøre det lett tilgjengelig og mulig å endre.
Vi skal kunne kjenne et sett med klassiske algoritmer og kjenne et sett med klassiske problemer. Men vi har noen problemer vi ikke har noen klassiske algoritmer på.
Vi skal også kunne analysere og designe algoritmer.
Forutse ressursene som algoritmer trenger for å kjøre. Ressurser kan være både minne, rekkevidde, tid og andre ting.
Kort sagt, RAM er en grunnleggende ressurs som algoritmer bruker til å utføre sine beregninger og dataoperasjoner. For å lage effektive og pålitelige algoritmer, må utviklere ta hensyn til hvordan algoritmen samhandler med RAM, inkludert minnebruk, datahåndtering og optimalisering.
RAM modellen inneholder instruksjoner som man ofte finner i datamaskiner: Aritmetikk (pluss, minus, gange, dele osv.), data-flytting (oppbevare, kopiere, laste) og datakontroll (branch).
Et problem er en generell relasjon mellom input og output. Antar at alle input har en tilhørende output. En konkret input kalles en instans. Hvis det ikke kan misforstås, brukes “problem” om instanser.
Bryte ned problemet (instansen) så det kan løses trinn for trinn. Fokuserer på ett representativt trinn.
Vi kan tenke på induksjonhypotesen som forarbeidet. Arbeidet frem til ett trinn blir forarbeidet for det neste.
En rekursiv prosedyre kaller på seg selv. Den er definert ved hjelp av seg selv.
Del opp i mindre problemer:
Induksjonhypotese: Anta at du kan løse de mindre problemene
Induksjonsteg: Konstruerer fullstendig løsning ut fra del-løsningene.
Annet syn på induksjon: løkkeinvariant. Vis at den holder for løkka og at løkka bevarer den. Da holder den også til slutt.
Kjøretiden beskriver hvor effektiv en algoritme er. Den refererer til hvor lang tid det tar for en algoritme å utføre en bestemt oppgave som funksjon av inputens størrelse. Kjøretiden måles vanligvis i forhold til inputens størrelse, ofte representert som “n”, hvor “n” kan være antall elementer i en liste, antall noder i en graf, eller lignende.
Asymptotisk notasjon
Vil finne kjøretid, men ignorerer detaljer.
Det finnes en abstrakt maskin for dette. Kun enkle instruksjoner, som aritmetikk, flytting av data og programkontroll. Disse tar konstant tid, uansett hvor stort problemet er. Vi kan håndtere heltall og flyttall. Antar vanligvis at heltallene er maks clgn, for en eller annen c større eller lik 1.
Problemstørrelse, n: Lagringsplass som trengs for en instans
Kjøretid: Funksjon av problemstørrelse
Worst-case: gir en øvre grense på hvor hva kjøretiden blir, uansett input.
Average case: er ofte like ille som worst-case
Best-case: gir en nedre grense for hva kjøretiden blir.
!! Viktige å huske at vi bryr oss ikke om selve kjøretiden, men the order of growth til kjøretiden. Derfor forenkler vi mange av utrykkene til kjøretidene. !!
For å uttrykke the order of growth bruker vi en spesiell notasjon med greske bokstaver.
Θ – Theta
Ω – Omega
O – Store o
Når du ser Θ(n2) skal du lese “funksjonen er omtrent estimert til å være n2 når n blir stor nok”.
Problemstørrelse, n: Lagringsplass som trengs for en instans
Kjøretid: Funksjon av problemstørrelse
Worst-case: gir en øvre grense på hvor hva kjøretiden blir, uansett input.
Average case: er ofte like ille som worst-case
Best-case: gir en nedre grense for hva kjøretiden blir.
!! Viktige å huske at vi bryr oss ikke om selve kjøretiden, men the order of growth til kjøretiden. Derfor forenkler vi mange av utrykkene til kjøretidene. !!
For å uttrykke the order of growth bruker vi en spesiell notasjon med greske bokstaver.
Θ – Theta
Ω – Omega
O – Store o
Når du ser Θ(n2) skal du lese “funksjonen er omtrent estimert til å være n2 når n blir stor nok”.
Som nevnt ser vi ikke på selve kjøretiden med den asymptotiske effektiviteten til algoritmen.
Når du skal gjenkjenne kjøretiden til en algoritme skal du glemme de delene med lavere orden.
O – notasjon (store O)
Store O representerer den øvre grensen til funksjonen. Det vil si at funksjonen kan ikke vokse fortere enn dette. Dersom funksjonen er:
n + n/6 + n4
Så vil n4 være funksjonens order of growth, siden den har størst orden og har mest betydning når n blir stor, og vi kan skrive O(n4).
Ω – notasjon (Omega)
Omega representerer den nedre grensen til funksjonen. Det vil si at funksjonen garantert vokser raskere enn dette. Vi bruker samme eksempel som i stad
n + n/6 + n4
Ω(n4) vil være “høyeste” nedre grense fordi funksjonen vil på det minste vokse såpass fort. Men husk at Ω(n3), Ω(n) osv. også vil være nedre grense, fordi den funksjonen vil vokse fortere enn dette.
Θ – notasjon (Theta)
Theta notasjonen representerer “gjennomsnittet” av vokse-raten til en funksjon. Dersom du kan bevise at O til funksjon er lik Ω til en funksjon (dvs. Øvre grense = nedre grense). Da vil Θ til funksjonen være det samme.
Teorem
For to funksjoner f(n) og g(n), har vi at f(n) = Θ(g(n)) hvis og bare hvis f(n) = O(g(n)) og f(n) Ω(g(n)).
Når vi bruker asymptotisk notasjon er det viktig å poengtere hvilken kjøretid den henger sammen med. Se på disse eksemplene:
For INSERTION SORT er Ω(n2), O(n2) og derav blir også Θ(n2). MEN dette hører til INSERTION SORT sitt worst case scenario.
For best-case med INERTION SORT har vi at Ω(n), O(n) og derav blir også Θ(n).
Så der er riktig å si at kjøretiden for INSERTION SORT i best-case er Θ(n) og kjøretiden for INSERTION SORT i worst-case er Θ(n2).
MEN vi kan ikke si at kjøretiden er Θ(n2), uten å presisere at dette er for worst-case. Det vi kan si derimot er at O(n2) gjelder for både worst-case og best-case, samt Ω(n) også gjelder for begge.
Grunnen til at vi bruker asymptotisk notasjon er for å gi en enkel og presis beskrivelse på grensene til funksjonen.
Asymptotisk notasjon i ligninger
Asymptotisk notasjon henviser egentlig til mengder. Vi bruker =, men egentlig er det riktig å bruke ∈.
4n2 + 100n + 500 = O(n2) –> 4n2 + 100n + 500 ∈ O(n2)
o – notasjon
Lille o og Store O er ganske like, men det er noen forskjeller. Der vi både kan skrive
2n2 = O(n2) og
2n = O(n2)
2n = o(n2) men
2n ≠ o(n2)
ω – notasjon
ω til Ω er nesten lik som lille o er til store o.
n2/2 = ω(n)
n2/2 ≠ ω(n2)
Datastrukturer
Stacks
Tenk på stacks som tallerkener i skapet. De du legger øverst i bunken, er de tar først ut; last-in, last-out (LIFO).
PUSH: legge til elementer i en stack
POP: fjerne elementer i en stack
Det nederste elementet har index lik 1, det øverste har index S.top.
Dersom S.top = 0 så er stacken tom. Hvis du prøver å poppe en tom stack, vil du få stack underflow. Dersom du prøver å pushe en full stack, vil du få stack overflow.
Køer
En kø implementerer first-in, first-out (FIFO), som en vanlig kø fungerer.
ENQUEUE: legge til elementer
DEQUEUE: fjerne elementer
En kø har en head og en tail, Når man legger til et element får køen en ny tail, når det fjernes et element går head videre til neste element i køen.
Lenkede lister
Lenkede lister fungerer slik at istedet for å ha en index som bestemmer rekkefølgen, er det en peker i hvert objekt som forteller hvem som er neste i listen.
Enkel-lenket liste: peker på hvem som er neste i listen
Dobbel-lenket liste: peker både på hvem som er neste og hvem som er forrige
Operasjoner på lenkede lister
LIST-SEARCH(L,k) – finner første element, med key k en liste L.
LIST-PREPEND(L,x) – setter inn et element x i starten av en liste L.
LIST-INSERT(x,y) – Denne brukes når du setter inn et element hvor som helst i lista. Den setter inn et element x, rett etter element y, så y peker på x.
LIST-DELETE(L,x) – fjerner x fra lista L
Analyse
Aggregert analyse og amortisert analyse er to metoder for å vurdere ytelsen til algoritmer over tid, spesielt når det gjelder tid og ressursbruk.
Aggregert Analyse:
- Beregner gjennomsnittlig tid eller ressursforbruk over en sekvens av operasjoner.
- Tar hensyn til beste, verste og mellomliggende tilfeller, gir en gjennomsnittlig tidskompleksitet.
- Nyttig når en algoritme varierer i tidsbruk for ulike operasjoner.
- Gir innsikt i gjennomsnittlig ytelse over tid, selv med variasjoner i individuelle operasjoners kompleksitet.
Amortisert Analyse:
- Garanterer gjennomsnittlig utførelse av hver operasjon i worst-case scenario.
- Jevner ut kostnadene over tid, spesielt nyttig når noen operasjoner er dyre i isolasjon.
- Fokuserer på å oppnå akseptabel gjennomsnittlig kostnad per operasjon.
- Ideell for situasjoner der sjeldne, dyre operasjoner amortiseres over flere billige operasjoner.
Hash-funksjoner
Du har sikkert hatt om hash-funksjoner før, og har en viss peiling på hva det går ut på. Hvis du kan python, så fungerer det på samme måte som dictionaries gjør. Vi har en key som peker på en verdi.
Direkte adressering:
Ved direkte adressering så er key det samme som indeksen i en liste. Her er et eksempel:
T = [4, 6, 2, 8, 3, 9]
indeks: 0 1 2 3 4 5
Da vil T[key] = verdi
I dette tilfellet er det f.eks T[1] = 6, fordi 6 har indeks 1
Universet U er alle mulige nøkler, i dette tilfellet er U = {0, 1, 2, 3, 4, 5}
En mer generell måte å skrive universet på er
U = {0, 1, ..., m-1}, og m er antall elementer i tabellen.
De ulike kodesnuttene for direkte adressering er:
Direct-address-search(T, k)
return T[k]
Direct-address-insert(T, x)
T[x.key] = x
Direct-address-delete(T,x)
T[x.key] = NIL
Hash tables
Dersom man driver med veldig lange tabeller, som også har veldig høye indekser, kan det lønne seg konvertere dette til en mindre tabell. Dette fungerer ved å hashe nøkelen til en mindre indeks, som brukes i stedet for den opprinnelige indeksen.
En god hashfunksjonen minimerer sannsynligheten for at to forskjellige nøkler mappes til samme verdi. Den skal også distribuere hashverdiene så uniformt som mulig. Dette minsker muligheten for kollisjon og minimerer tiden det tar å søke etter et element.
Vi har også et krav til hashfunksjoner:
En nøkkel må alltid hashes til samme verdi. Hashfunksjonen må være deterministisk.
Et eksempel på en hasfunksjonen er
h(k) = k mod 4
h(0) = 0, h(901) = 1, h(3) = 3 osv.
Kollisjoner
I noen tilfeller vil en hashfunksjon mappe til samme verdi. For eksempel vil både h(902) og h(2) fra eksempelet over mappe til 2. Som igjen peker på samme verdi. For å løse dette bruker vi chaining, dvs. at vi lager en lenket liste ved indeks 2.
Uniformt fordelt nøkler
Dersom 0≤k<1, og m er antallet slots i tabellen T, så vil h(k) = ⌊km⌋, fungere veldig bra.
h(k) = k mod m, vil også fungere fint.
Ikke bra: når m = 2^p.
Multiplikajsonsmetoden
h(k) = ⌊m (kA mod 1) ⌋, der 0 < A < 1, A ≈ (√5 - 1)2
Divide and conquer
Designing algorithms
Divide-and-conquer er en måte man kan designe en algoritme på. Den er rekursiv, d.v.s. den kaller på seg selv. Disse algoritmene bryter problemet ned i mindre del-problemer som ligner på hovedproblemet, bare at det er mindre. Når man har løsninger til alle del-problemene bruker man disse til å lage en løsning for hele problemet.
Hvordan fungerer det?
- Du deler problemet i mindre deler
- Løser delproblemene rekursivt, til man kommer til base case
- Samler løsningen for å lage en løsning på det originale problemet
Kort og godt:
Du løser et problem t rekursivt, er problemet lite nok, base case, så løser du det direkte. Hvis ikke, recursive case, så gjør du disse stegene:
Divide: del problemet inn i mindre deler
Conquer: løs delproblemene
Combine: kombiner løsningene for å finne en løsning på hovedproblemet
Algoritmiske rekurrenser, ofte referert til som rekurrensrelasjoner eller bare rekurrenser, er matematiske uttrykk som beskriver tidskompleksiteten eller ressursbruken til en algoritme i forhold til dens tidligere oppførsel. De brukes vanligvis i analysen av algoritmer for å bestemme hvordan algoritmens ytelse (typisk målt i form av tids- eller plasskompleksitet) vokser som en funksjon av størrelsen på inndataene.
I konteksten av algoritmeanalyse består en rekurrensrelasjon vanligvis av to deler:
- Grunntilfelle: Dette er det enkleste scenariet hvor problemet kan løses direkte uten ytterligere rekursjon. Det gir den initielle betingelsen for rekurrensrelasjonen.
- Rekursivt tilfelle: Denne delen uttrykker tids- eller ressurskompleksiteten til algoritmen i form av kompleksiteten ved å løse mindre instanser av det samme problemet. Den beskriver hvordan algoritmen deler problemet inn i mindre delproblemer og kombinerer deres løsninger for å løse det opprinnelige problemet.
En vanlig notasjon for å uttrykke rekurrensrelasjoner er T(n), der “n” representerer størrelsen på inndataene (for eksempel antallet elementer i en matrise), og T(n) representerer algoritmens tids- eller ressurskompleksitet for den input-størrelsen.
Her er et enkelt eksempel på en rekurrensrelasjon for tidskompleksiteten til algoritmen merge sort, der “n” er størrelsen på input-matrisen:
T(n) = 2T(n/2) + O(n)
I dette eksempelet:
– Grunntilfellet er når inndatamatrisen bare har ett element, og det tar konstant tid O(1) å sortere den.
– Det rekursive tilfellet uttrykker tidskompleksiteten ved å sortere en matrise med størrelse “n” i form av å sortere to undermatriser med størrelse “n/2” (delingssteg) og deretter slå sammen disse sorterte undermatrisene, noe som tar lineær tid O(n) (erobringssteg).
Å løse rekurrensrelasjoner er en viktig del av algoritmeanalyse, da det lar deg forutsi og forstå algoritmens oppførsel når inndatastørrelsen øker. Teknikker som rekursjonstrær, substitusjonsmetoder og mestersteoremet brukes vanligvis for å løse og analysere disse rekurrensene og bestemme algoritmens samlede tidskompleksitet.
Oppsummert er algoritmiske rekurser matematiske uttrykk som brukes til å beskrive hvordan tids- eller ressurskompleksiteten til en algoritme avhenger av størrelsen på inndataene, og de spiller en avgjørende rolle i å analysere og forstå algoritmeeffektivitet.
Tre teknikker for å løse rekurrenser:
Rekursjonstrær
Substitusjon metode
Masterteoremet
Divide and conquer algoritmer
merge sort
Merge sort bruker divide-and-conquer metoden, den bryter ned problemet i mindre problemer og løser disse, før de merges sammen. Det er to kode-deler som hører til merge sort, en som sorterer og en som merger. Så tanken er at vi deler arrayen helt til vi kommer til enkelt-elementene. Deretter setter vi sammen og sorterer to deler, helt til vi har sortert hele arrayen.
merge_sort(A, p, r):
1 if p < r
2 q =⌊(p+r)/2⌋ # Divide the array into two halves
3 merge_sort(A,p,q) # Recursively sort both halves
4 merge_sort(A,q+1,r)
5 merge(A,p,q,r) # Merge the sorted halves
merge(A, p, q, r)):
1 n1 = q-p +1 # Beregner størrelsen på den venstre delen av A som skal merges (fra indeks p til q).
2 n2 = r-q # Beregner størrelsen på den høyre delen av A som skal merges (fra indeks q+1 til r).
3 let L[1 ... n1 + 1] and R[1 .. n2 + 1] be new arrays
4 for i = 1 to n1
5 L[i] = A[p+i-1] # Kopierer elementene fra den venstre delen av A til arrayen L.
6 for j = 1 to n2
7 R[j] = A[q+j] # Kopierer elementene fra den høyre delen av A til arrayen R.
8 L[n1 + 1] = ∞
9 R[n2 + 1] = ∞
10 i = 1
11 j = 1
12 for k = p to r
13 if L[i] ≤ R[j] # Sjekker om det nåværende elementet i L er mindre enn eller lik det nåværende elementet i R.
14 A[k] = L[i]
15 i += 1
16 else A[k] = R[j]
17 j += 1
Finne kjøretid
Divide: regne ut midten av arrayen tar konstant tid : Θ(1)
Conquer: dette steger løser to delproblemer rekursivt, med størrelse n/2: 2T(n/2)
Combine: merge prosessen tar Θ(n)
T(n) = Θ(1) + 2T(n/2) + Θ(n) = 2T(n/2) + Θ(n)
T(1) = 1
Masterteoremet gir oss at T(n)= n lg n, men vi kan også løse dette med rekurrenstre.
| Best-case | Average-case | Worst-case |
|---|---|---|
|
O(n logn) |
O(n logn) |
O(n logn) |
bisect
Når du vil sjekke om et element v er i en array, kan man bruke bisect. Dersom v er i arrayen, vil koden returnere en indeks i slik at A[i] = v. Arrayen A må være en sortert tabell.
bisect(A,p,r,v):
1 if p ≤ r:
2 q = ⌊(p+r)/ 2⌋
3 if v == A[q]:
4 return q
5 elif v < A[q]:
6 return bisect(A,p,q-1,v)
7 else
8 return bisect(A,q+1,r,v)
9 else return NIL
Bisect uten rekurrens:
bisect_2(A,p,r,v):
1 while p ≤ r:
2 q = ⌊(p+r)/ 2⌋
3 if v == A[q]
4 return q
5 elif v < A[q]:
6 r = q-1
7 else: p = q+1
8 return NIL
Finne kjøretid
Her kan vi bruke substitusjonsmetoden, (induksjon) for å finne kjøretiden. Vi få rekurrensutregningen:
T(1) = 1 (Når vi har kommet oss til grunntilfellet, tar det konstant tid)
(1) T(n) = T(n/2) + 1 (Vi deler lista i to og leter på den ene siden)
(2) = T(n/4) + 2
(3) = T(n/8) + 3
.
.
(i) = T(n/2^i) + i
(lg n) = T(n/n) + lg n = lg n + 1
Kjøretiden blir derfor Θ(lg n).
| Best-case | Average-case | Worst-case |
|---|---|---|
|
usikker |
Θ(lg n). |
usikker |
quicksort
Quicksort bruker divide-and-conquer metoden. Tenk deg at du skal sortere en gruppe mennesker utifra når på året de er født. En teknikk du kan bruke er å si at alle som er født fra før juli skal stå til høyre og alle som er født etter juli skal stå til venstre. Deretter ber du begge gruppene selv sortere seg riktig. Omtrent slik fungerer quicksort.
Quicksort sorterer en array rekursivt med å bruke ett pivot element. Et element er sortert når alle elementene til venstre en mindre enn dette tallet og alle elementene til høyre er større.
quicksort(A, p, r):
1 if p<r:
2 pivot_index = partition(A, p, r)
3 quicksort(A, p, pivot_index - 1)
4 quicksort(A, pivot_index + 1, r)
Partition-funksjonen tar inn en array og sorterer den slik at elementene lavere enn pivot-elementet er til venstre og de som er høyere er til høyre for pivot-elementet. Den returnerer indeksen til pivot-elementet etter deling.
partition(A, p, r):
1 pivot = A[r]
2 i = p -1
3 for j = p to r-1
4 if A[j] ≤ pivot
5 i += 1
6 exchange A[i] with A[j]
7 exchange A[i+1] with A[r]
8 return i+1
| Best-case | Average-case | Worst-case |
|---|---|---|
|
Θ(n lg n) |
O(n lg n) |
Θ(n^2) |
randomized quicksort
Randomized quicksort fungerer på nesten helt lik måte som quicksort, men i stedet for å bruke den høyeste indeksen som pivot, velges den tilfeldig av elementene.
randomized_quicksort(A, p, r):
1 if p<r:
2 pivot_index = randomized_partition(A, p, r)
3 randomized_quicksort(A, p, pivot_index - 1)
4 randomized_quicksort(A, pivot_index + 1, r)
Partition-funksjonen tar inn en array og sorterer den slik at elementene lavere enn pivot-elementet er til venstre og de som er høyere er til høyre for pivot-elementet. Den returnerer indeksen til pivot-elementet etter deling.
randomized_partition(A, p, r):
1 pivot = random.randint(p, r)
2 exchange A[r] with A[i]
3 return partition(A, p, r)
| Best-case | Average-case | Worst-case |
|---|---|---|
|
usikker |
Θ(n lg n). |
Θ(n^2) |
Masterteoremet
T(n) = aT(n/b) + (n^d), for a > 0, b > 1, d ≥ 0
if d > logb(a) ⇒ T(n) = O(n^d)
if d = logb(a) ⇒ T(n) = O(n^d log n)
if d < logb(a) ⇒ T(n) = O(n^(logb(a))
Iterasjonsmetoden
Dette er en måte å løse rekurrensligninger på. Dette er en ganske simpel metode, så jeg tror vi bare kjører et eksempel:
T(0) = 0
T(n) = T(n-1) + 1
Det vi vil oppnå er å fjerne T(n-1) leddet på høyre side. Vi gjør dette ved å bruke ligningen vi allerede har.
T(n-1) = T((n-1)-1) + 1
= T(n-2) + 1
T(n) = T(n-2) + 1 + 1
= T(n-2) + 2
Også fortsetter vi slik til vi kommer ned til vi ser et mønster.
T(n)= T(n-1) + 1 (1)
= T(n-2) + 2 (2)
= T(n-3) + 3 (3)
. .
. .
. .
= T(n-n) + n = n (n)
I dette tilfelle trenger vi n ekspansjoner for å komme ned til grunntilfelle.
Et annet eksempel er vist under.
T(1) = 1 T(n)
= T(n/2) + 1 (1)
= T(n/4) + 2 (2)
= T(n/8) + 3 (3)
.
.
.
= T(n/2^i ) + i (i)
= T(n/n) + lg n = lg n + 1 (lg n)
Substiusjonsmetoden
Substitusjonsmetoden (som også kalles induksjon) har to steg:
- Grunntilfellet: Vis at grunntilfellet stemmer
- Induktivt steg: Anta all løsningen gjelder for rekursivt kall og vis at det gir løsningen
Eksempler
T(n) = n
T(0) = 0
T(n) = T(n-1) + 1
Denne rekurrensrelasjonen har løsning T(n)= n fordi:
1. T(1) = T(0) + 1 = 1
2. Vi antar at T(n-1) = n-1, og vil vise at T(n) = n.
T(n) = T(n-1) + 1 = (n-1) + 1 = n
Begge stegene oppfylles og derfor kan verifisere løsningen.
Binærsøk
T(1) = 1
T(n) = T(n/2) + 1
Denne relasjonen har løsning T(n) = lg n + 1, vi verifiserer:
1. T(1) = lg(0) + 1 = 1 (Antar at T(0) = 0)
2. Vi antar at T(n/2) = lg(n/2) + 1, og vil vise at T(n) = lg 1 + 1
T(n) = T(n/2) + 1
= lg(n/2) + 1 + 1
= lg(n) - lg(2) + 2
= lg(n) - 1 + 2
= lg(n) + 1
Mergesort
T(1) = 1
T(n) = 2T(n/2) + n
Vi verifiserer at relasjonen har løsning T(n) = n lg n + n:
1. T(1) = 1 lg(1) + 1 = 1
2. Vi antar at T(n/2) = n/2 lg(n/2) + n/2
T(n) = 2((n/2) lg(n/2) + n/2) + n
= n lg(n) - nlg(2) + n + n
= nlg(n) - n + 2n
= nlg(n) + n
Quicksort (worst-case)
T(1) = 1
T(n) = T(n-1) + n
Vi verifiserer at relasjonen har løsningen T(n) = n(n+1)/2
1. T(1) = 1(1+1)/2 = 1
2. Vi antar at T(n-1) = (n-1)(n)/2
T(n) = n(n-1)/2 + n
= (n(n-1) + 2n)/2
= n(n+1)/2
Sortering i lineær tid
Hva er sammenlignsbasert sortering?
En sorteringsalgoritme som går ut på å sammenligne to elementer for å vite hvilket som kommer først, kaller vi sammenligningsbasert. Worst case sortering er Ω(n lg n). Worst-case antall sammenligninger er den lengste ruten fra roten til bladet i et tree, altså høyden til treet. Derfor vil en nedre grense for kjøretiden vil være en nedre grense for høyden. Vi må derfor vise at høyden til et valgtre i værste tilfelle er n lg n.
En stabil sorteringsalgoritme er en algoritme som beholder rekkefølgen på to like elementer etter sortering som før sortering. Tenk deg en array:
[1, 5, 2(1), 9, 3, 2(2), 4]
Etter sortering med en stabil sorteringalgoritme vil den se slik ut:
[1, 2(1), 2(2), 3, 4, 5, 9]
Radix-sort: se på siste element og jobbe seg innover
Bucket sort: deler inn i bøtter og sorterer med en annen sorterings-algoritme, f.eks. insertion sort.
Randomized select: binærsøk med velging, ikke sortering
Bevis på at worst case scenario er Ω(n lg n)
counting sort
Counting sort er ikke en sammenligningsbasert algoritme. Algoritmen er stabil siden den holder på rekkefølgen til like tall. Den baserer seg på å telle like elementer og deretter plassere de på riktig indeks. Denne algoritmen passer bra når du har mange like elementer i en array.
Antallet elementer du har er n. Antallet unike elementer er k. Dersom n>k er dette en fin algoritme å bruke.
La meg prøve å forklare.
Vi har en liste/tabell/array:
A = [3,1,2,1,2,2,3,1,2,3] (1-indeksert)
Først ser vi på hvor mange elementer vi totalt har: n =10
Så ser vi på hvor mange unike tall vi har: k=3 (1,2 og 3)
Veldig enkelt:
Det counting sort gjør, er å lage en helt ny tom liste C. I denne lista teller den opp antallet av de unike elementene og plasserer dette nye tallet på indeksen til selve elementet.
C = [0, 3, 4, 3] => vi har null 0-ere, tre 1-ere, fire 2-ere og tre 3-ere. (0-indeksert)
Så legger vi sammen nåværende verdi + verdi ved forrige indeks slik at C blir slik:
C = [0, 3, 7, 10]
Den siste verdien (her 10), skal tilsvare totalt antall elementer i A.
Deretter lager vi en ny liste B, som blir den nye sorterte listen. Fremgangsmåten her er å se på liste A og gå bakover derifra.
Vi starter med det siste elementet i A.
i = 3
Deretter bruker vi denne som indeks i liste C.
C[i] = C[3] = 10
Også bruker vi dette tallet som indeks i B og setter inn verdien fra A. Deretter minsker vi C[i] med 1.
counting_sort(A, B, k):
1 Let C[0..k] be a new array
2 for i = 0 to k
3 C[i] = 0
4 for j = to A.length
5 C[A[j]] += 1 # teller forekomstene av elementene i A
6 for i = 1 to k
7 C[i] += C[i - 1]
8 for j = A.length downto 1 # lager den sorterte arrayen B
9 B[C[A[j]]] = A[j]
10 C[A[j]] -= 1
Eksempel
| Best-case | Average-case | Worst-case |
|---|---|---|
|
Θ(n + k) |
Θ(n + k). |
Θ(n + k) |
radix sort
Radix sort er en sorteringsalgoritme der man ser på tall med like mange siffer. Først sorterer man tallene etter sifferet lengst til høyre, og jobber seg mot det lengst til venstre. Den bruker en stabil sorteringsalgortime til selve sortering, f.eks. counting sort. Radix sort trenger en stabil sub-algoritme for å kunne beholde den tidligere sorteringen på de mindre viktige sifrene.
Dersom den stabile algoritmen har kjøretid på Θ(n + k), så vil radix sort ha en kjøretid på Θ(d(n + k)). Der d er antall siffer, n er antall nummer og k er mulige verdier.
Dersom den stabile algoritmen har kjøretid på Θ(n + k), så vil radix sort ha en kjøretid på Θ((b/r)(n+2^r)). Der b er antall bits, n er antall nummer og r≤b.
| Best-case | Average-case | Worst-case |
|---|---|---|
|
Θ(d(n+k)) |
Θ(d(n+k)) |
Θ(d(n+k)) |
bucket sort
Kort fortalt deler bucket sort elementene inn i buckets (bøtter) og sorterer hver bucket for seg, før man merger dette sammen til én sortert liste. Den tar inn en array med n elementer som har verdi mellom 0 og 1.
Bucket sort tar inn en liste med n på intervallet [0,1) og fordeler intervallet i n like store buckets. Deretter ganger man hvert element med n, før man plasserer det i det del-intervaller/bucket som det passer inn i.
bucket_sort(A):
1 Let B = [0... n-1] be a new array
2 n = A.length
3 for i = 0 to n-1
4 make B[i] an empty list
5 for i = 1 to n
6 insert A[i] into list B[⌊nA[i]⌋]
7 for i = 0 to n-1
8 sort list B[i] with insertion sort
9 concatenate the lists B[0], B[1], ...B[n-1] together in order
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
Θ(n) |
Θ(n^2) |
Rotfaste trestrukturer
Basics om trær
Heaps
I algdat har vi også en annen form for arrays, som vi kaller heaps, dette har stukturen til et familietre. En node med noder “under seg” kalles henholdsvis forelder og barn. Den øverste noden er roten og nodene uten barn kalles blader.
Heaps er som regel tabeller. Vi har to typer heaps:
- Min-heap : der roten er det laveste tallet og alle barna er større enn sin forelder.
- Max-heap : roten er det største tallet og alle barna er mindre enn sin forelder
Heaps må også ha heapsegenskapen (heap property), denne sier noe om hvordan nodene under rotnoden skal være. F.eks. for max-heap sier heapegenskapen at alle barn skal være lavere enn sin forelder.
Trær er indeksert slik som dette:
Det finnes noen algoritmer for å navigere seg i dette systemet.
LEFT(i)
return 2i
#LEFT(i) gir deg indeksen til det venstre barnet til noden med indeks i.
RIGHT(i)
return 2i + 1
#RIGHT(i) gir deg indeksen til det høyre barnet til noden med indeks i.
PARENT(i)
return floor(i/2)
#PARENT(i) gir deg indeksen til forelderen til noden med indeks i.
Binære søketrær
Et binært søketre har binær-søketre-egenskapen (binary search tree property), nemlig at for alle nodene n i treet, så vil nodene til venstre for n være mindre eller lik n. Og alle nodene til høyre for n vil være større eller lik n.
Høyden på et vilkårlig søketre med n noder har høyde Ω(lgn) og O(n)
Sortere lister med binært søketre
inorder-tree-walk
Går igjennom treet og skriver ut en sortert liste av elementene. Kjøretid er Θ(n) hvis det er n noder i treet.
inorder-tree-walk(x)
1 if x ≠ NIL
2 inorder-tree-walk(x.left)
3 print(x.key)
4 inorder-tree-walk(x.right)
Søke etter element i treet
tree-search
En rekursiv måte å lete etter elementer i treet. Tar inn en peker til roten og k som er tallet vi letere etter. Vi sjekker om roten er større eller mindre enn k, da vet vi hvilken retning vi skal gå ned (venstre eller høyre).
tree-search(x, k)
1 if x== NIL or k == x.key
2 return x
3 if k < x.key
4 return tree-search(x.left, k)
5 else return tree-search(x.right, k)
iterative tree search
Ikke rekursiv, men fungerer på samme måte som tree search.
tree successor
Finner neste element som er større enn x i den sorterte rekkefølgen.
tree-successor(x)
1 if x.right ≠ NIL
2 return tree-minimum(x.right)
3 y = x.p
4 while y ≠ NIL and x == y.right
5 x = y
6 y = y.p
7 return y
tree insertion
Tar inn et tre og en peker. Setter inn en key på riktig sted.
tree-insert(T, z)
1 x = T.root
2 y = NIL
3 while x ≠ NIL
4 y = x
5 if z.key < x.key
6 x = x.left
7 else x = x.right
8 z.p = y
9 if y == NIL
10 T.root = z
11 elif z.key < y.key
12 y.left = z
13 else y.right = z
Algoritme (kjøretid)
Inorder-tree-walk (Θ(n))
Tree-serach (O(h))
Tree-minimum (O(h))
Tree-successor (O(h))
Tree-insert (O(h))
Tree-delete (O(h))
Prioriteringskøer
Dersom vi har en mengde med elementer som har ulik prioriteringsgrad, kan vi bruke heaps til å hente ut det elementet med høyest prioritering. Til dette bruker man max-heaps.
En slik prioriteringskø har noen egenskaper:
For max-priority-queues
- INSERT(s, x)sette inn et nytt element med en gitt prioritering
- MAXIMUM(S)få det mest prioriterte elementet
- EXTRACT-MAXIMUM(S)fjerne det mest prioriterte elementet
- INCREASE-KEY(S,x,k)øke prioriteringen til et gitt element.
For min-priority-queues
- INSERT(s, x) sette inn et nytt element med en gitt prioritering
- MINIMUM(S)få det minst prioriterte elementet
- EXTRACT-MINIMUM(S)fjerne det minst prioriterte elementet
- DECREASE-KEY(S,x,k) minske prioriteringen til et gitt element.
Algoritmer
max heapify
Denne algoritmer retter opp feil i max-heaps. Når vi har en forelder som er mindre enn barnet må dette rettes opp i. Da bytter den seg selv ut med det største av sitt barn, helt til noden ikke har barn som en større enn seg selv.
left(i):
return 2i
right(i):
return 2i +1
parent(i):
return i//2
max_heapify(A,i):
1 l = left(i)
2 r = right(i)
3 if l≤ A.size and A[l] > A[i]:
4 largest = l
5 else: largest = i
6 if r ≤ A.size and A[r] > A[largest]:
7 largest = r
8 if largest ≠ i:
9 exchange A[i] with A[largest]
10 max_heapify(A, largest)
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
O(log n) |
- |
build-max-heap
Denne algoritmen brukes for å lage en max heap fra en usortert array A[1, …n]. en bruker max heapify til å bygge heapen.
build_max_heap(A)
1 A.heap-size = A.length
2 for i = ⌊A.length/2⌋ downto 1
3 max_heapify(A, i)
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
Θ(n) |
- |
heap-extract-max
Denne algoritmer fjerner roten og setter det siste elementet til å være roten. Deretter kjører den max-heapify på dette elementet slik at det faller på sin plass, samtidig som man finner hvilket element som skal være den riktige roten.
heap_extract_max(A):
1 if A.size <1:
2 error "heap underflow"
3 max = A[1]
4 A[1] = A[A.heapsize]
5 A.heapsize -= 1
6 max_heapify(A,1)
7 return max
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
Θ(lg n) |
- |
heap-increase-key
Dersom vi vil sette en ny verdi til en av nodene, bruker vi denne algoritmen. Den endrer verdien til node i til den nye verdien, og flytter den slik at noden står på riktig plass.
heap_increase_key(A,i,key):
1 if key < A[i]:
2 error("new key is smaller than current key")
3 A[i] = key
4 while i > 1 and A[parent(i) < A[i]
5 exchange A[i] with A[parent(i)]
6 i = parent(i)
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
Θ(lg n) |
- |
max-heap-insert
Denne algoritmer lar oss sette inn et nytt element i heapen. Dette gjøres ved
- øke størrelsen på heapen med 1
- sette det nye elementet til -∞
- bruke heap-increase-key til å sette inn den verdien vi vil og plassere noden på riktig plass
max_heap_insert(A,key):
1 A.size = A.size +1
2 A[A.size] = -∞
3 heap_increase_key(A, A.size, key)
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
Θ(lg n) |
- |
heapsort
Heapsort er en sorteringalgoritme som bruker max-heap for å sortere elementene sine.
heapsort(A):
1 build_max_heap(A)
2 for i = A.length downto 2
3 exchange A[1] with [i]
4 A.heapsize = A.heapsize -1
5 max_heapify(A,1)
| Best-case | Average-case | Worst-case |
|---|---|---|
|
- |
O(n lg n) |
- |
Grådige algoritmer
Gårdighetsegenskapen:
Grådighetsegenskapen refererer til egenskapen ved visse problemer, hvor den optimale løsningen kan oppnås ved å ta lokalt optimale beslutninger i hvert steg av problemet. Dette betyr at i en grådig tilnærming tar du alltid den mest gunstige umiddelbare beslutningen på hvert trinn uten å nødvendigvis vurdere hele fremtidige løsningen. For slike problemer har grådige algoritmer en tendens til å fungere svært effektivt, da de ikke krever fullstendig utforskning av alle mulige beslutningsbaner, noe som ofte kan føre til betydelig tidsbesparelse og ressursfordel.
Kort sagt, grådighetsegenskapen innebærer at du kan bygge en optimal løsning ved å ta det beste umiddelbare valget i hvert skritt, noe som gjør grådige algoritmer nyttige for visse typer problemer; vi er grådige: velger det som ser best ut for oss akkurat nå.
Det er ikke alltid grådige algoritmer fungerer, så når funker det? Jo dersom disse to kriteriene er oppfylt:
- Greedy Choice Property (grådighetsegenskapen): når vi ikke ødelegger for seinere valg, dersom vi velger det beste her og nå.
- Optimal delstruktur: en optimal løsning på problemet kan konstrueres fra optimale løsninger på delproblemene.
Vi ser på et eksempel; aktivitetsutvalget
Du har en mengde aktiviteter, hver med en starttid og en sluttid. Du ønsker å velge en delmengde av aktivitetene slik at ingen av de valgte aktivitetene overlapper i tid, og du vil maksimere antall aktiviteter i den valgte delmengden.
- Optimal delstruktur
Problemet har en optimal delstruktur, noe som betyr at en optimal løsning for hele problemet består av optimale løsninger for mindre delproblemer. Hvis du har en optimal løsning som inkluderer aktiviteter A og B, må alle de gjenværende aktivitetene i problemet, som ikke overlapper med A og B, også være optimalt valgt. - Grådighetsegenskapen
Den grådige egenskapen i dette problemet er at det alltid lønner seg å velge den neste aktiviteten som slutter tidligst, forutsatt at den ikke overlapper i tid med de tidligere valgte aktivitetene. Med andre ord, du velger alltid aktiviteten med den tidligste sluttiden som fortsatt er kompatibel med de tidligere valgte aktivitetene.
La oss se hvorfor dette er tilfelle:
- Anta at du har valgt aktivitet A som slutter tidligst blant alle aktivitetene.
- La B være den neste aktiviteten som slutter tidligst blant de gjenværende aktivitetene som ikke overlapper med A.
- Hvis du velger B, får du to aktiviteter (A og B) som ikke overlapper og slutter tidligst blant alle mulige par av aktiviteter.
- Hvis du valgte en annen aktivitet C (som ikke overlapper med A) i stedet for B, ville sluttiden til C vært senere enn sluttiden til B (fordi B ble valgt fordi den sluttet tidligst).
Så, den grådige tilnærmingen er å alltid velge aktiviteten med tidligst sluttid, forutsatt at den er kompatibel med de tidligere valgte aktivitetene. Dette gir den optimale løsningen for aktivitetsutvalgsproblemet og kan enkelt implementeres når aktivitetene er sortert etter sluttid.
Kjøretiden for denne grådige tilnærmingen er Theta(n), hvor (n) er antallet aktiviteter, siden du bare trenger å gå gjennom aktivitetene én gang for å velge de optimale.
Knapsack problem (ryggsekk problemet)
Du er en tyv som skal stjele varer fra en butikk, men har kun med en ryggsekk til å frakte varene. Hvordan skal du velge hvilke varer som skal med?
Det finnes to varianter
- 0-1 knapsack , tyven kan enten ta med en vare eller ikke ta med en vare
- Kontinuerlig (fraksjonell) knapsack, tyven kan ta med fraksjoner av en vare
Det kontinuerlige ryggsekk-problemet har grådighetsegenskapen, men det har ikke 0-1 ryggsekk-problemet. Dette er fordi det finnes en optimal løsning der vi tar med mest mulig av det dyreste.
Huffman-koder
- Huffman-koder brukes til å representere data på en mer effektiv måte ved å tildele kortere binære koder til hyppig forekommende tegn og lengre koder til mindre hyppige tegn.
- Huffman-koding kan oppnå betydelig komprimering, ofte mellom 20% og 90%, avhengig av tegnenes frekvens i den opprinnelige datasekvensen.
- Det er prefiks-koder, noe som betyr at ingen kode er prefikset av en annen kode. Dette gir en unik dekoderingsmulighet, og Huffman-treet gir en hierarkisk struktur der hvert tegn er representert av en sti fra roten til en løvnode.
huffman(C)
1 n = |C|
2 Q = C
3 for i = 1 to n-1
4 allocate a new code z
5 x = extract_min(Q)
6 y = extract_min(Q)
7 z.left, z.right = x, y
8 z.freq = x.freq + y.freq
9 insert(Q, z)
10 return extract_min(Q)
Gale Shapley
Gale-Shapley-algoritmen:
Gale-Shapley-algoritmen, også kjent som den stabile ekteskapsalgoritmen, er en algoritme som løser det stabile ekteskapsproblemet eller den stabile partisjonsproblemet. Problemet involverer matching av elementer fra to sett (for eksempel kvinner og menn) under gitte preferanser, slik at det ikke er noen umatching par der begge kan forbedre ved å bytte partnere.
Her er en kort oversikt over hvordan algoritmen fungerer:
1. Initiering
- Hver mann og kvinne rangerer alle de andre i rekkefølge etter preferanse.
2. Matching
- Hver mann frier til sin høyest rangerte kvinne, og hver kvinne aksepterer frieren som er hennes høyest rangert blant dem som har fridd.
3. Oppdatering
- Hvis en kvinne får en bedre frier senere, endrer hun sitt valg til den nye frieren. Mannen som blir avvist, frir deretter til sin neste høyest rangerte valg.
4. Gjenta
- Prosessen gjentas til det ikke er flere endringer, og hver kvinne har den beste frieren hun kan få.
Resultatet er en stabil matching, da det ikke er par som har insentiver til å bytte partnere.
Blokkerende par:
Blokkerende par refererer til situasjoner der det er et par som ikke er matchet sammen, men begge foretrekker hverandre over sine nåværende partnere i en matching. I konteksten av Gale-Shapley-algoritmen vil det være et blokkerende par hvis det er to personer som ønsker å bytte partnere fordi de foretrekker hverandre.
Gale-Shapley-algoritmen sikrer at det ikke eksisterer blokkerende par i den resulterende matchingen, noe som gjør den stabil. Det betyr at ingen par har insentiver til å bryte og bytte partnere etter at algoritmen har konvergert.
Traversering av grafer
En graf består av noder (vertices) og kanter (edges). Nodene i grafen kan representeres med tall, og en kant mellom f.eks. node 5 og 7 representeres som (5, 7).En sti i en graf er en sekvens av noder der det finnes kanter som kobler påfølgende noder. Grafer kan være rettede, der kanter har en bestemt retning angitt med piler, eller de kan være urettede, der kantene vanligvis er uten piler.
En syklisk graf er en graf som inneholder minst én syklus, som er en sti som starter og slutter på samme node.
Et tre er en type urettet graf hvor det er kun én sti mellom hvert par av noder, og det kan derfor ikke ha sykluser.
Graf presentasjon
Vi kan representere grafer på to måter, nabomatrise og nabolister. En graf har én nabomatrise, men kan ha mange nabolister.
Nabomatrise
Dersom det er n noder i grafen, er det n*n ruter i matrisen. Ruten settes til 1, dersom det er en kant mellom node i og j. Ellers vil den være 0. Dette brukes når vi har en graf med mange kanter, fordi den er veldig lett å slå opp i. Ulempen er at den tar opp mye plass, selv hvis det er få kanter. Minneplass theta(V^2) og tid vil være Theta(1), altså konstant tid.
Nabolister
En naboliste inneholder lister på hver indeks i. Listen på indeks i inneholder alle nodene som i har en kant til. Denne listen er lettere å traversere, men kan ta lengre tid enn en matrise. Minneplass Theta(V+E), tid for å finne en kant vil ta theta(V)
Algoritmer
bredde-først-søk (BFS)
Dette er en algoritme for å søke igjennom en graf. Den finner
- alle nodene en kilde s kan nå
- korteste vei til hver node
Tingen med BFS er at den gjør dette søket systematisk, dvs den finner først alle nodene man kan nå med én kant, også lagrer det. Deretter finner det alle nodene den kan nå med to kanter, osv. Det er derfor den heter bredde først søk.
BFS opererer med et fargesystem, de nodene som ikke er besøkt er hvite, de som er besøkt og har hvite naboer er grå. Tilslutt har vi nodene som er besøkt og har grå naboer som er svarte.
Algoritmen har tre lister:
π: indeks i sier hvilken node som var i sin forrige.
d: avstand (antall kanter) fra startnoden til nåværende node.
Q: køen/huskelista (rekkefølgen vi besøker nodene)
Kjøretid er O(V+E) (noder + kanter)
Bredde først tre
Bredde først tre er et tre bygget på resultatet fra BFS. Dette treet inneholder stiene fra kildenoden og til alle de andre nodene som den har en kant til. Den kan printes ut ved hjelp av algoritmen Print-Path. Under ser dere et eksempel på et bredde først tre og print-path.
dybde-først-søk
I stedet for å finne alle nodene på et nivå, før man går videre (sånn som i BFS), vil DFS gå så langt ned i dybden på en sti, før den beveger seg over til enste node. Denne algoritmen bryr seg ikke om avstand, men heller om tid. Vi har to tid-variabler, discover time (d) og finish time (f)
Selv om BFS og DFS presenteres ganske ulike, så er det faktisk ganske like. Dersom vi bytter ut en FIFO køen i BFS med en LIFO kø, eller stack, ligner DFS-Visit og BFS veldig.
Det er bruken av en FIFO kø, som tillater oss å finne korteste sti til alle noder. Men dersom vi bytter ut med LIFO, vil dette gi samme atferd som rekursiv traversering. Maskinen bruker da en kallstakk, der informasjon om hvert kall legges øverst, og hentes frem når det rekursive kallet er ferdig.
Forskjellen mellom disse algoritmene ser vi i hvilke noder som prioriteres fra køen:
- BFS prioriterer de eldste, DFS-Visit prioriterer de nyeste
- Dijkstra prioriterer noder med lavt avstandsestimat
- MST-prim prioriterer noder som ha en lett kant til én av de besøkte nodene
Minimale spenntrær
Vektede grafer er grafer der alle kantene (u,v) i E (alle kantene) har en tilhørende vekt på grafen w(u,v). Tenk på det som bompenger for å komme fra en node til en annen.
Tenk deg at vi har en mengde noder, med kanter i mellom seg. Vekten på kantene er hvor mye det koster å koble akkurat disse to nodene sammen. Det vi ønsker er å finne de kantene T (subset) av E, som gjør at alle nodene har én kant koblet til seg og at den totale vekten av disse kantene er minimert. Dette problemet kalles minimum-spanning-tree problem.
Et generelt tre som der det kun finnes én sto mellom to noder, kalles et spenntre. Et minimalt spenntre, er det som lager minimal totalvekt.
w(T) = SUM[ w(u,v) ]
Disjunkte mengder
En disjunkt mengde, er en mengde der ingen av elementene er like. Vi bruker disse mengdene for å representere en en mengde noder som et tre. Det velges en representant som er et element i mengden.
Disjunkt-mengde datastruktur er en samling av disjunkte mengder:
S = {S1, S2, S3, …., Sk}
Treet er rettet, der alle nodene peker på sin forelder.
Mange programmer går ut på å gruppere n elementer i disjunkte mengder. Det er ofte to operasjoner som programmet skal utføre, finne det settet som inneholder et bestemt element, og slå sammen to sett. Det er viktig å beholde datastrukturen som støtter disse operasjonene.
MAKE-SET(x): lager et nytt set med x,
der x er det eneste elementer og
dermed representanten.
UNION(x,y): setter sammen to disjunkte,
dynamiske mengder som inneholder x og y.
FIND_SET(x): returnerer en peker til
representanten i den mengden som inneholder x.
LINK(x,y): x og y er representerer fra
hver sin disjunkte mengde.
I denne algoritmen skal de kobles sammen.
Den representanten som har den laveste ranger,
"kobler seg på " det andre mengden.
Connected grafer
En urettet graf er connected dersom hver node kan nås fra alle andre noder. De connected components i en urettet graf er hvor det finnes subgrafer som er connected. I eksempelet under er {1,4,5}, {2,3} og {6} connected components i grafen.
Et område vi kan bruke disjunkt-mengde datastrukturen er når vi skal finne disse connected components i en graf.
CONNECTED-COMPONENTS(G): bruker disjunkt-mengde operasjoner for å finne connected components.
Den operer slik at den tar utgangspunkt plasserer hver node v i hvert sin mengde. Så, for hver kant (u,v), samler den nodene i mengdene til u og v i en felles mengde.
SAME-COMPONENT(u,v): svarer på om to noder tilhører samme connected component.
Disjunkt-mengde skoger
I en disjunkt-mengde skog peker hver node på sin forelder (motsatt av et “vanlig” tre). Roten i treet, er grafens representant, som er sin egen forelder. Hver node x, har også en rang som forteller høyden på noden (eller hvor mange kanter man må gå for å komme til en løvnode).
Minimum spanning trees
Vi har to måter å løse minimum spenntre-problemet: Kruskals algoritme og Prims algoritme. Begge kjører på O(E lg V) tid og er grådige algoritmer, de tar første og beste mulighet ved valgene de tar.
Prim bruker binary heap som prioritetskø. Ved bruk av fibonacci heaps i stedet, bruker den en kjøretid på O(E+ V lg V). Denne grensen er bedre enn den øvrige når E øker asymptotisk raskere enn V.
Corollary 21.1
Let G = (V, E) be a connected undirected graph with a real-valued weight function w defined on E. Let A be a subset of E that is included in some minimum spanning tree for G, and let C = (Vc, Ec) be a connected component (tree) in the forest Ga = (V, A). If (u, v) is a light edge connecting C to som other component in Ga, then (u, v) is safe for A.
Algoritmer
Tre måter å finne et minimalt spenntre
Grafene G som tas inn i algoritmene nedenfor er connected og urettet, med V noder og E kanter. Alle kantene har også en vekt av funksjonen w.
GENERIC_MST(G,w):
Under ser dere en pseudokode til algoritmen. A er mengden med noder som skal bli treet vårt. Den fungerer slik at når du står på en node og skal til neste, velger du den kanten (u,v) som veier minst, ved hvert “veivalg”. Algoritmen lager en union mellom A og kanten (u,v), helt til du har besøkt alle nodene.
MST-KRUSKAL(G, w)
Denne algoritmen gjør først alle nodene til representant i sin egen mengde med kun den noden i. Deretter sorterer den kantene mellom nodene fra lavest til høyest vekt. Så begynner den på kanten med lavest vekt, og kombinerer mengden fra den ene noden med mengden fra den andre noden. Dersom nodene allerede er i samme mengde, “kaster” vi bort kanten, fordi vi allerede har en sti mellom disse nodene som en “tryggere” (lavere vekt).
kjøretid: O(E lg V)
Prims algoritme
MST-PRIM(G, w)
– Prims algoritme sikrer at kantene i kantmengden A alltid danner et sammenhengende tre.
– Prims algoritme er klassifisert som en grådig algoritme fordi den, ved hvert trinn, velger den kanten med lavest vekt for å inkludere i treet, så lenge dette valget ikke medfører dannelse av en syklus.
– For å hjelpe Prims algoritme med å effektivt velge kantene, bruker den en min-prioritetskø kalt Q, som inneholder alle de uutforskede verteksene som ikke er en del av treet.
– Hver verteks i Q er tildelt en “key” som representerer den laveste vekten av en kant som knytter verteksen til treet.
Korteste vei fra en til alle
Hvordan komme seg fra A til B, på kortest mulig måte. Shortest-path-problem eller korteste-vei-problemet handler om å finne den tryggeste stien/veien i en rettet, vektet graf. Forskjellen dette og MST (minimum spanning tree) er at i dette tilfelle har vi en rettet graf, mens i MST har vi ikke en rettet graf. I tillegg har vi en bestemt kildenode, noe man ikke har i MST.
Shortest-path weight: δ(u, v).
Simple path: sit/vei uten sykluser
Vi har ulike varianter av korteste-vei-problemet:
SSSP (Single-source shortest-paths problem): gitt en graf G = (V, E), finn det korteste veien fra en source node, til alle andre nodene i V.
SDSP (Single-destination shortest-paths problem): gitt en graf G = (V, E), finn korteste vei fra hver og en av nodene i V til en gitt destinasjons node.
SPSP (Single-pair shortest-path problem): gitt en graf G = (V, E), finn den korteste veien fra u til v for to gitte noder, u og v.
APSP (All-pairs shortest-paths problem): gitt en node G = (V, E), finn den korteste veien fra u til v, for hvert par av noder.
Negativt-vektet noder
I dette korteste-vei-problemet kan det oppstå situasjoner med negativt-vektet noder. Dersom en graf G = (V, E) inneholder negative sykler, som man kan nå fra kildenoden, vil man ikke kunne definere shortest path weight. Dette er fordi en negativ syklus vil føre til at man alltid kan redusere vekten på stien, desto flere ganger man går igjennom syklusen.
Sykluser
- Shortest path kan ikke inneholde negative sykluser
- Den kan heller ikke inneholde en positiv syklus, men grafen kan inneholde sykluser
- Anta at shortest path har på det meste V-1 kanter.
Representasjon shortest paths
Når man regner ut shortest path er man som regel også interessert i å finne ut av hvilke noder som er med i denne pathen. Derfor har alle nodene en forgjenger v.π som sier hvilken node man kom fra. forgjengeren er enten NIL eller en node.
Relaxation
SSSP-algoritmene bruker teknikken relaxation, den fungerer slik:
Hver node i grafen G = (V, E) har en attributt v.d, som er en øvre grense for den samlede vekten fra kildenoden s til v. Denne attributten kalles shortest-path estimate. Før man kjører RELAX på en gra må vi initialisere verdiene v.d og v.π, ved å kjøre INITIALIZE-SINGLE-SOURCE (G, s). Slik du ser nedenfor setter vi totalvekten fra s til alle nodene til å være ∞, utenom s som har s.d = 0. Vi setter også forgjengeren til alle nodene til å være NIL, siden vi ikke vet hvilken vei man skal gå enda.
Det relaxation gjør er å sjekke om det går an å forbedre den korteste veien til en node fra s. Relaxation går igjennom en kant (u, v) for å sjekke om denne kanten forbedrer shortest path og i så fall oppdaterer den. Under ser dere et eksempel på algoritmen.
Egenskaper til shortest path og relaxation
Alle egenskapene gjelder for en graf G med V noder og E kanter. s er kildenoden og w er funksjonen av vekt.
- Triangle inequality: For hver kant (u, v), er δ(s, v) ≤ δ(s, u) + w(u, v)
- Upper-bound property: v.d≥ δ(s, v) for alle nodene og når v.d = δ(s, v), forandres v.d aldri.
- No-path property: Hvis det ikke finnes en vei fra s til v, vil v.d = ∞
- Convergence property: Hvis vi har funnet den korteste veien fra kilde noden “s” til node “v” gjennom en mellomliggende node “u,” og vi har allerede beregnet den korteste avstanden fra “s” til “u” (dvs., “u.d = δ(s, u)”), så vil enhver etterfølgende relaxation av kanten mellom “u” og “v” alltid føre til at avstanden til “v” (“v.d”) blir lik den korteste avstanden fra “s” til “v” (“δ(s, v”). Med andre ord, vi oppnår riktig korteste avstand til “v” uansett hva som skjer videre.
- Path-relaxation: Hvis det er en korteste vei “p” fra kilde noden “s” til node “v,” og vi utfører relaxation av kantene langs denne banen i riktig rekkefølge, vil vi alltid oppnå den riktige korteste avstanden til “v” (“v.d = δ(s, v”).
- Predecessor-subgraph property: Når den korteste avstanden til alle noder i grafen er beregnet fra kilde noden “s,” vil forgjenger-subgrafen representere en korteste-vei-tre med “s” som rotnode. Med andre ord, vi kan bruke denne treet for å finne den korteste veien fra “s” til alle andre noder i grafen.
Algoritmer
Bellman-Ford algoritmen
Denne algoritmen løser single-source shortest-path problemet, der det kan finnes negativt-vektet noder og sykluser. Den returnerer en boolean verdi, avhengig av om det finnes negative sykluser eller ikke i den vektede, rettede grafen G = (V, E). Hvis det ikke er en slik syklus, vil den lage shortest path. Den fungerer ved at den kjører relax på hver kant i grafen. Det spiller ingen rolle hvilken rekkefølge man kjører relax, så lenge man kjører den nok ganger vil vi kunne finne shortest path.
Når vi har kjørt RELAX V-1 ganger på grafen, skal vi ha funnet den korteste veien, dersom det finnes en.
Kjøretid: O(VE)
DAG-SHORTEST-PATH
DAG (Directed Acyclic Graph)
- Kan ikke inneholde sykluser i grafen
- Kan ha negative kanter
Vi sorter grafen topologisk, vi setter altså nodene på en linje, der noden til venstre peker på noder til høyre for den. Vi bruker relax på hver kant, kun én gang, dette kommer av path relaxation egenskapen fra tidligere.
Sammenheng mellom DAG-algoritmen og dynamisk programmering:
- DAG-Shortest-Paths-problemet: Dette problemet går ut på å finne den korteste veien fra en startnode til alle andre noder i en rettet asyklisk graf (DAG). Problemet er spesielt enkelt å løse i en DAG, siden det ikke finnes sykler i grafen. Det betyr at vi ikke trenger å bekymre oss for negative sykler eller uendelige løkker i søket etter den korteste veien.
- Dynamisk programmering: Dynamisk programmering er en metode for å løse problemer ved å bryte dem ned i mindre delproblemer og bygge opp løsningen fra bunnen av. I konteksten av korteste vei i en DAG, bruker dynamisk programmering et konsept kjent som “optimal delstruktur” og “overlappende delproblemer.” Dette betyr at den korteste veien fra startnoden til en hvilken som helst annen node kan beregnes ved å kombinere resultatene fra korteste vei til dens forgjengere i grafen.
Sammenhengen mellom DAG-Shortest-Paths og dynamisk programmering kan oppsummeres som følger:
- I en DAG kan du bruke dynamisk programmering til å finne den korteste veien fra startnoden til alle andre noder.
- Du kan dra nytte av repetisjonen av delproblemer (fordi flere noder kan dele de samme forgjengerne) for å optimalisere beregningen.
- Dynamisk programmering hjelper deg med å bygge opp løsningen gradvis ved å finne den korteste veien til forgjengerne og deretter beregne den korteste veien til hver etterfølgende node i grafen.
Kjøretid: Theta(V + E)
Under ser der et eksempel på algoritmen.
Her ser vi utgangsgrafen vår.
Vi sorterer grafen topologisk, og kjører INITIALIZE-SINGLE-SOURCE på grafen.
Vi velger A som utgangsnode, fordi den kommer først i den sorterte rekkefølgen, og kjører RELAX på alle kantene knyttet til A og oppdaterer estimatet til noden.
Vi er ferdige med A, her markert rødt, og gjøre det samme med neste node i rekkefølgen, her C.
Vi er ferdige med C og gjøre det samme med neste node i rekkefølgen, her B.
Vi er ferdige med B, og gjøre det samme med neste node i rekkefølgen, her D. D har ingen kanter til andre noder, derfor er vi ferdige med den også. Da er vi ferdig med algoritmen, og vi har funnet shortest path markert i rødt.
Dijkstras algoritme
I stedet for å kjøre RELAX V-1 ganger, slik som i bellman ford, så kjører vi RELAX på alle kanter, kun én gang. Dette går fint, fordi vi tar hensyn til hvilken rekkefølge vi gjør det. Det kan ikke kjøres på grafer med negative kanter, men grafen kan ha sykluser. Rekkefølgen til algoritmen er fra den noden med lavest estimat til høyest estimat. Estimat vil si den totale vekten fra startnode til nåværende node. Når man har kjørt relax på alle kantene utifra en node, så er vi ferdig med den noden.
Kjøretid: O((E + V) lg V) generelt, og O(E lg V) om alle noder kan nås fra kilden.
Eksempel
1. Initialiser estimatet til å være ∞ for alle nodene utenom startnode som er 0.
2. Velg den noden som har minst estimat, her A.
3. Utfør relax på kantene til denne noden og oppdater estimatet til de neste nodene.
4. A er så ferdig, merket her med rød.
5. Velg den noden som har minst estimat, her C.
6. Utfør relax på kantene til denne noden og oppdater estimatet til de neste nodene.
7. C er så ferdig, merket her med rød.
8. Velg den noden som har minst estimat, her D.
9. Utfør relax på kantene til denne noden og oppdater estimatet til de neste nodene.
10. Alle nodene er ferdig og vi har funnet shortest path
Korteste vei fra alle til alle
Denne delen handler om å finne korteste vei mellom alle par av noder i en graf. Dette problemet kan løses med å kjøre en single-source shortest path algoritme på alle nodene i grafen. Dersom alle kantene er positive kan vi kjøre Dijkstras algoritme. Kjøretiden blir da O(V^3 + EV), som er O(V^3).
Hvis grafen inneholder negative kanter, kan vi kjøre Bellman Ford algoritmen. Denne for en kjøretid på O(V^2E) på enkle grafer og O(V^3) på dense grafer.
Vi skal nå se om vi greier å forbedre denne kjøretiden, ved å implementere matriser inn i problemet. Matrisen vil inneholde δ(i, j) for hver av nodene i grafen.
δ(i, j): shortest path weight from vertex i to j.
Inputen til disse algoritmene er en rettet graf med n noder, og vekten til kanten (i,j) er gitt ved en n x n matrise w, der elementet w_ij representerer vekten av kanten fra node i til node j.
Outputen fra APSP-algoritmene er en n x n matrise, der hvert element inneholder vekten av den korteste veien fra node i til node j, med andre ord δ(i, j). I tillegg finner algoritmene predecessor matrix ∏, der πij representerer forgjengeren til node j langs den korteste veien fra node i til j (eller NIL hvis det ikke finnes noen vei fra i til j eller i=j).
Subgraf gitt av i-te rad i predecessor ∏ representerer en shortest-path tree (forgjenger subgraf) med roten i noden i.
PRINT-ALL-PAIRS-SHORTEST-PATH
Dette er en modifisert versjon av PRINT PATH, som skriver ut korteste vei fra node i til j.
Johnsens algoritme
I Johnsens algoritme bruker vi Dijkstras algoritme på alle nodene. Dijkstras algoritme kan i utgangspunktet kun kjøre når grafene har positive kanter, men Johnsens algoritme skal også fungere når grafen har negative kanter. Derfor må vi mikse og trikse litt for å kunne kjøre Dijkstras på grafer med negative kanter (reweighting)
Kjøretid: O(VE lgV)
O(V^2 lg V + VE) når DIJKSTRA bruker Fibonacci heaps. Dersom den bruker den enklere binary heap implementasjonen O(VE lg V).
Dersom V ≈ E blir kjøretiden O(V^2 lgV)
Reweighting
Her er en graf G, med en negativ kant.
Konstruer en ny graf G’, med en ekstra node s. s har kanter til alle andre noder i grafene, og vekten på disse kantene er 0.
Regn ut funksjonen h av alle nodene. Funksjonen regner ut shortest path fra s til en hver node.
h(v) = δ(s,v), for v ∈ V
Finn de nye positive vektene ved denne formelen:
w'(v, u) = w(v, u) + h(v) – h(u)
der w(v, u) er vekten til kanten.
Selve algoritmen steg for steg
Her er et eksempel på algoritmen. Jeg bruker eksempelet over når jeg regner ut h-funksjonen og de nye vektene. Når det står ∞ i matrisen, betyr dette at det ikke finnes en kant mellom nodene.
*Skal stå kantene og ikke grafene^
Floyd-Warshall
Kjøretid θ(V^3)
- negative kanter kan være i grafen
- negative sykluser kan ikke være tilstede i grafen
Så hvordan fungerer denne?
Eksempel på hvordan Floyd-Warshall algoritmen fungerer. Vi får inn en matrise W, som forteller oss kantene til grafen. Vi kan konvertere mellom matrise og graf slik som bildet under viser. VI setter også D0 = W.
Transitive closure
Vi har fortsatt en graf G = (V, E). Nå bryr vi oss ikke lenger om vektene på kantene i grafen, men vi vil finne ut av om det finnes en sti mellom node i og j, for i,j ∈ V.
Transitive closure av G er definert som grafen
G* = (V, E*)
Den nye mengden med kanter E* er definert som
E* = {(i,j): hvis det finnes en sti mellom i og j i grafen G }
Vi kan finne den transitive lukningen til en graf i θ(n^3) tid, ved å gi alle kantene en vekt på 1, for å så kjøre Floyd-Warshall. Hvis det er en node mellom i og j, får vi at d_ij < n, hvis ikke blir d_ij= ∞.
En annen metode som tar samme tid, men sparer tid og plass
Vi lager en matrise med alle direktegående kanter. Nodene du når dersom du går én kant fra alle nodene i grafen.
Kjøretid: θ(n^3)
Eksempel på transitiv lukning
Maksimal flyt
Dette er egentlig et litt spennende tema, som man lettere kan knytte til virkeligheten. Forestill deg en vask, den henter vann fra en tank, fører vannet gjennom en ledning til utgangen av vasken. Dette er et flow network. Hvis vi overfører dette til en rettet graf, så vil hver rettet kant være ledningen i bak vasken. Hver ledning har en gitt kapasitet, altså maksimum vann som kan gå igjennom ledningen gitt en viss tid. F.eks. kan ledningen føre 10L vann/min. Nodene i grafen er knutepunkter for ledingene. I dette eksempelet vil vanntanken være startnoden s (source), og vasken vil vøre endenoden t (sink).
Målet med maximum-flow problem er å finne den maksimale raten som materiale kan flyte gjennom et system, uten å bryte kapasitetsbegrensninger.
Her kommer det som står over på en litt mer fjong måte:
Et Flow network G = (V, E) er en rettet graf, der alle kantene
(u,v) ∈ E har en ikke-negativ kapasitet c(u,v).
Dersom det finnes en kant (u,v) ∈ E, så vil (v,u) ∉ E.
Alle nodene er mellom en soruce s og en sink t.
|E| ≥ |V| - 1
I maximum-flow problem vil inputen være et flow network G med
en source s og en sink t. Målet er å finne den maksimale flowen til nettverket.
Flyten (flow) til et nettverk er definert som en funksjon
ƒ : V×V → R
som tilfredsstiller disse kravene:
1. capasity constraint:
for alle (u, v) ∈ V, så må 0 ≤ f(u, v) ≤ c(u, v), altså kan ikke flowen være større enn kapasiteten
2. flow conservation:
for alle u ∈ V (uten s og t), så må ∑ f(u, v) = ∑ f(v, u). Med andre ord så må Flow in = flow ut
Når det ikke er en kant mellom u og v så vil f(u, v) = 0
Verdien |f| av flowen f er gitt ved
|f| = ∑ f(s, v) - ∑ f(v, s)
Som nevnt kan vi ikke ha grafer der det går en kant fra u til v og en kant fra v til u. Dette kalles antiparallelle kanter. Hvis en graf har antiparallelle grafer må vi konvertere grafen til en ekvivalent graf, dette er veldig enkelt, se eksempel under.
Nettverk med flere sources (s) og sinks (t)
For å løse problemet med at man kan ha flere kilder {s1, s2, s3 , …}og endepunkter {t1, t2, t3, …,}, lager man en supersource s og en
En graf med flere sources og sinks:
Omformet grafen til å kun ha én source og én sink.
For å forstå de neste algoritmene er det noen begreper vi må kunne, derfor går jeg igjennom dem først.
Residual networks (rest nettverk)
Vi er ute etter å finne ut om vi kan øke kapasiteten til et flow network, for å gjøre dette må vi ha oversikt over mye av kapasiteten som brukes ved hver kant. Derfor kommer ofte flow network sammen med residual network. Denne grafen forteller oss hvor det er noe ledig kapasitet ved kantene, og hvor mye vi bruker fra før.
Det er ikke alltid man maxer ut kapasiteten ved en kant, det pleier som regel å være igjen noe ubrukt kapasitet. Når vi lager grafen til et residual network tegner vi kapasiteten brukten (flowen) som en bakoverkant, og totalkapasiteten – brukt kapasitet (flow) som fremoverkant. Se eksempel under.
Her ser du vårt flow network G med flow og kapasitet per kant:
Her har vi laget residual network Gf, prøv å se hvordan den henger sammen med G:
Augmenting path (forøkende sti)
Når vi har funnet residual network Gf gjelder det å se om vi kan finne en augmenting path. En augmenting path er en sti i Gf som går fra sourcen s til sinken t. I eksempelet finner vi én slik sti, merket i rødt. Når vi har funnet augmenting path, må vi så finne hvor mye kapasitet vi kan øke i denne stien. Den økende kapasiteten er den minste kapasiteten av alle kantene i den gjeldende augmenting pathen, her er dette 3.
Cuts (snitt) av flow network
Et cut (S, T) av et flow network G vil si at vi deler nodene i G i S og T, slik at
s ∈ S og t ∈ T
Net flow f(S, T) til et flow network G, altså total-flowen som går fra nodene i S til T minus total-flowen som går fra nodene i T til S.
Cut – kapasitet c(S , T):
Minimum cut av et nettverk er et snitt der kapasiteten er den minste den kan være over alle snittene av nettverket.
Max-flow min-cut theorem
Hvis f er en flow i et flow network G = (V, E) med source s og sink t, da vil følgende påstander være ekvivalente:
- f er en maximum flow i G
- residual nettverket (rest-nettverket) Gf inneholder ingen augmenting paths (forøkende stier)
- |f|= c(S, T) for noen cuts (S, T) av G
Ford-Fulkerson metoden
Den heter “metode” fordi med ulike implementasjoner kan vi få ulik kjøretid. Metoden avhenger av tre viktige ideer:
- residual networks ( restnettet)
- augmenting paths (forøkende sti)
- cuts
Ford-Fulkerson algoritme
Kjøretid: O(E|f*|), der |f*| er maksimum flowen
Edmunds-Karp algoritme
Dette er en versjon av Ford-Fulkserson metode BFS (bredde først søk), for å finne augmenting path med færrest kanter.
Kjøretid: O(VE^2)
δƒ(u, v) => shortest-path fra node u til v i et residual network Gƒ.
Theorem
Hvis vi kjører Edmunf-Karps algoritme på et flow nettverk G=(V, E), med source s og sink t vil det totale antallet flow økninger være O(VE).