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 udvikling af algoritmer som freelancer.
Artiklen består af noter om algoritmer fra da jeg læste på datamatiker uddannelsen.
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
- Del usorteret liste I halv og merge sort hver halvdel.
- 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
- Vælg et element fra et array. Dette element bliver kaldt en pivot.
- Omroker elementerne i arrayet – lavere værdier før pivot og højere værdier efter pivot.
- 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