Algoritmer

0
490

I denne artikel finder du en kort gennemgang af forskellige algoritmer, og hvordan de kan bruges til at løse problemstillinger. God viden omkring algoritmer har været en stor hjælp i forbindelse med mit arbejde med programmering.

Artiklen består af noter om algoritmer fra da jeg læste på datamatiker uddannelsen.

Algoritmer

Backtracking algoritmer

Backtracking algoritmer er baseret på depth-first recursive search – recursive strategy.

Backtracking algoritmer kan fx bruge til at løse følgende problemer – TicTacToe, 8 Queens og Sudoko.

Divide and conquer algoritmer – Del og hersk algorimer

Divide and conquer algoritmer deler problemet i mindre dele, og løser delproblemerne rekursivt.

Løsningerne på delproblemerne bliver kombineret, så det originale problem bliver løst.

En algoritme bliver kun kaldt divide and conquer, hvis den indeholder to eller flere rekusive kald.

  • Merge Sort – Easy split/hard join
  • Quicksort – Hard split/easy join

Mergesort

Mergesort er en divide and conquer algoritme, som bruges til sortering. Mergesort deler problemet i to delproblemer ved hvert step. Delproblemerne er så halv størrelse af det orginale problem: O(n log n). Delproblemer bliver så merget sammen.

  • O(n log n) i worst case og average case

Steps i Mergesort

  1. Del usorteret liste I halv og merge sort hver halvdel.
  2. Kombiner de to sorterede lister til en ved at merge dem.

Læs mere om Mergesort her: https://en.wikipedia.org/wiki/Merge_sort

Quicksort

Quicksort er også en divide and conquer algoritme. Quicksort algoritmen deler først et array i to del-arrays. Et del-array med lave værdier og et del-array med høje værdier. Quicksort sorterer så rekursivt del-arrays.

  • O(n^2) i worst case
  • O(n log n) i average case
  • Total tid brugt på omarrangere et array er altid O(n)

Steps i Quicksort

  1. Vælg et element fra et array. Dette element bliver kaldt en pivot.
  2. Omroker elementerne i arrayet – lavere værdier før pivot og højere værdier efter pivot.
  3. Brug ovenstående steps igen rekursivt i mindre delproblemer.

Husk at Quicksort kan impleteres på mange forskellige måder i forhold til valg af pivot og selve omrokingen. Det har stor betydning for performance af Quciksort algoritmen.

Læs mere om QuickSort her: https://en.wikipedia.org/wiki/Quicksort

Vil du vide mere om divide and conquer algoritmer, så læs mere om binary search, fibonacci numbers (towers of Hanoi problemet).

Dynamisk programmering algoritmer

Tilsvarende til divide and conquer (del og hersk). Problemet bliver delt til delproblemer

Dynamisk programmering algoritmer gemmer forrige svar/løsning, som så bruges når der bliver mødt et tilsvarende delproblem. Det gør at det samme problem ikke skal løses helt forfra – man undgår dermed re-computing.

  • Fibonacci numbers i computer science
  • Fibonacci heap
  • Fibonacci search

Greedy algoritmer – Grådige algoritmer

Optimering af problemer er hvor du ønsker at finde – ikke bare en løsning men den bedste løsning.

En greedy algoritme optimerer problemet ved altid at kigge efter den bedste nuværende løsning, som så bliver tilføjet til en samling af delløsninger. Greedy choice property – a locally optimal choise is globally optimal.

  • Prim
  • Kruskal
  • Dijkstra (korteste vej i en graf)
  • Brute force algoritmer
  • Randomized algoritmer

A* algoritme

A* algoritmen bliver brugt meget I pathfinding og Graph traversal. A* algoritmes bruger heuristics til guide sig i den rigtige retning samtidig med at den beregner en sti med minimale omkostninger.

Variant af Dijkstra algoritmen er almindeligt anveldt i spil(pathfinding, 8 puzzle).

A* calculates the function

f(v) = g(v) + h(v)

g(v) = actual cost of the path from the starting point to the vertex v.

h(v) = heuristic estimated cost from vertex v to the goal

DEL
Tidligere artikelBrute force
Næste artikelFreelance programmør
Freelance softwareudvikler i TB Coding, speciale i udvikling af kunstig intelligens og robotteknologi. Fokus på udvikling af software til selvkørende biler.

EFTERLAD ET SVAR