Komplekse algoritmer

Skip to content

Easy Oppgave 1 - Greatest Common Divisor (GCD)

Greatest Common Divisor, eller GCD, er et matte-konsept som ofte brukes i komplekse algoritmer. Denne algoritmen tar for seg to input tall, og finner det største tallet som begge tallene er delelig på.

Eksempler:

  • GCD av \(48\) og \(18\) er \(6\)
  • GCD av \(101\) og \(10\) er \(1\)
  • GCD av \(270\) og \(192\) er \(6\)
  • GCD av \(56\) og \(98\) er \(14\)
  • GCD av \(50\) og \(50\) er \(50\)

I alle disse eksemplene er det ingen tall som er større som begge to er delelige på. Men, hvordan implementeres dette?

  • Prøv først selv å lage en algoritme.
    • Hvor rask ser denne ut til å være i “Big O notation”? (Se på Level 2 for hva Big O betyr).
  • Prøv deretter å implementere følgende algorithme (litt matematisk): Euclidean Algorithm
Test data
a b GCD
48 18 6
101 10 1
270 192 6
56 98 14
50 50 50
84 30 6
17 31 1
144 60 12
81 27 27
121 11 11

Les mer om KMP her: Wikipedia KMP

Bruk gjerne pseudokoden som inspirasjon.

I Level 1 – Oppgave 10, implementerte dere en måte å søke i tekst. KMP er en raskere algoritme (som også er mye mer komplisert å forstå) for å søke i tekst. Der farten i Level 1 var \(O(n \cdot k)\) er kjøretiden her nærmere \(O(n + k)\), der \(n\) er lengden på søke-teksten og \(k\) lengden på det vi søker etter. Altså vi går så å si fra \(O(n^2)\) til \(O(n)\).

Implementer denne algoritmen.

Test Data
Test-type Tekst Test-mønster Forventet resultat
Enkelt treff ababcabcabababd ababd Treff på indeks 10
Flere treff og overlapp aaaaa aa Treff på indeksene 0, 1, 2, 3
Ingen treff abcdefg hij Ingen treff
Norsk tekst det var en gang en katt som het kattastrofe. katt Treff på indeksene 19 og 32
Start og slutt abcXYZabc abc Treff på indeksene 0 og 6

Hard Oppgave 3 - Levenshtein Distance

Les om Levenshtein Distance Wikipedia, Levenshtein Distance

Levenshtein Distance brukes til å finne ut hvor stor forskjell det er mellom to tekster. Avstanden er definert som det minste antallet operasjoner som kreves for å gjøre den ene strengen om til den andre.

Operasjonene

Avstanden regnes ut basert på følgende tre operasjoner:

  1. Innsetting av et tegn
    • kat → sett inn t etter a → katt
  2. Sletting av et tegn
    • banan → slett n (tredje bokstav) → baan
  3. Erstatting av tegn
    • hallo → erstatt h med m → mallo

Hver av disse operasjonene gjelder som 1 i distance.

Implementer denne algoritmen.

Test data
String 1 String 2 Levenshtein Distance
kitten sitting 3
book back 2
abc abc 0
saturday sunday 3
norge norgee 1
programmer program 3

Cracked Oppgave 4 - Dijkstra’s Algoritme

Teori

Dijkstra’s algoritme [a] finner den korteste veien fra én start-node til alle andre noder i en graf [b] der alle kantvekter er non-negative. Algoritmen bruker et “besøkt”-sett og en prioritetskø (Priority queue) [c] (eller en enkel lineær søkestrategi) for å gradvis finne fram og låse inn de korteste avstandene.

Grafen

Grafen består av noder (punkter i grafen) og kanter (binder punkter sammen). Hver kant har en “weight”, for eksempel avstand, tid, pris, eller noe annet.

Implementer denne algoritmen.

  • Programmet skal returnere en liste over korteste avstander, eller
  • De faktisk korteste rutene (søkeord: backtracking)

Her må du også implementere en “graf”-datastruktur.

Test data (Vekt er i parenteser)

Noder: A, B, C, D
Kanter (med vekt i parentes):

  • A → B (1)
  • A → C (4)
  • B → C (2)
  • B → D (5)
  • C → D (1)

Startnode: A

Forventede korteste avstander:

  • A: 0
  • B: 1
  • C: 3
  • D: 4

Noder: S, A, B, C, D, E

Kanter:

  • S → A (7)
  • S → B (2)
  • A → C (3)
  • B → A (2)
  • B → D (4)
  • C → E (1)
  • D → E (5)

Startnode: S

Forventede korteste avstander:

  • S: 0
  • B: 2
  • A: 4 (via B)
  • D: 6 (via B)
  • C: 7 (via A)
  • E: 8 (via C)

Noder: S, A, B, C, D, E, F, G, H, I

Kanter (rettede, med vekt):

  • Node S
    • S → A (4)
    • S → B (1)
    • S → C (7)
  • Node A
    • A → B (2)
    • A → D (5)
  • Node B
    • B → C (2)
    • B → E (10)
  • Node C
    • C → D (3)
    • C → F (1)
  • Node D
    • D → E (4)
    • D → G (8)
  • Node E
    • E → H (2)
  • Node F
    • F → D (2)
    • F → G (3)
  • Node G
    • G → H (1)
    • G → I (5)
  • Node H
    • H → I (3)

Startnode: S

Korteste avstander fra S:

  • S: 0
  • B: 1
  • C: 3
  • A: 4
  • F: 4
  • D: 6
  • G: 7
  • H: 8
  • E: 10
  • I: 11

Teori

A* er en søkealgoritme som finner korteste vei fra en start-node til en mål-node i en graf. Den ligner litt på Dijkstra’s algoritme fra forrige oppgave, men bruker noe som kalles “heuristics” for å “gjette” hvor langt det er igjen til målet.

Denne algoritmen brukes ofte i spill til path-finding.

For den matematiske definisjonen så regner A* ut følgende:

\[ f(n) = g(n) + h(n) \]
  • g(n) = faktisk kostnad fra start til n
  • h(n) = heuristics: estimert kostnad fra n til målet
  • f(n) = total “score” som brukes for å velge neste node

Hvis algoritmen for “heuristics” er god, altså ikke overvurderer avstanden til mål, vil A* finne den korteste veien.

Oppgaven

Implementer A* Search for en graf der du får:

  • Nodes
  • Edges med weights
  • En heuristics-verdi h(node) for hver node
  • En start-node og en mål-node

Programmet skal finne fram til:

  • Total kostnad for den korteste veien.
  • Selve veien (rekkefølge av noder)
Test Data
Type Verdi
Noder S, A, B, G
Start S
Mål G

Noder

Fra Til Vekt
S A 1
S B 4
A B 2
A G 5
B G 1

Heuristikk (h(node)) (estimert kostnad til G):

Node h(node)
S 4
A 3
B 1
G 0

Forventet resultat:

  • Korteste vei: S → A → B → G
  • Total kostnad: 1 + 2 + 1 = 4
Type Verdi
Noder S, A, B, C, D, G
Start S
Mål G

Noder

Fra Til Vekt
S A 2
S B 5
A C 2
B C 1
B D 3
C G 3
D G 1

Heuristikk (h(node)) (estimert kostnad til G):

Node h(node)
S 7
A 5
B 4
C 3
D 1
G 0

Forventet resultat:

  • Korteste vei: S → A → C → G
  • Total kostnad: 2 + 2 + 3 = 7