DOA Examination Notes PDF

DOA eksamensnoter Patrick Gobbenobber Bjerregaard, Jonas Andersen & Malthe Jensen Januar 2018 Contents 1 Linear Data Structures...

DOA eksamensnoter Patrick Gobbenobber Bjerregaard, Jonas Andersen & Malthe Jensen Januar 2018 Contents 1 Linear Data Structures 3 1.1 Indledning............................................. 3 1.2 Linked Lists............................................ 3 1.2.1 Generel opbygning.................................... 3 1.2.2 Insert........................................... 3 1.2.3 Remove.......................................... 4 1.2.4 Copy............................................ 4 1.3 Stacks og queues......................................... 4 1.3.1 Stacks........................................... 4 1.3.2 Queues.......................................... 5 2 Recursion 6 2.1 Indledning............................................. 6 2.2 Hvad er rekursion?........................................ 6 2.3 Den rekursive opskrift...................................... 6 2.4 Eksempel 1 - Sum........................................ 6 2.5 Eksempel 2 - Factorial...................................... 7 2.6 Hvornår bør man bruge rekursion?............................... 7 3 Maps 8 3.1 Indledning............................................. 8 3.2 Hash Maps............................................ 8 3.2.1 Hash funktionen..................................... 8 3.2.2 Open-address hash maps................................. 8 3.3 Collisions and clustering..................................... 10 3.3.1 Probing.......................................... 10 3.3.2 Chained hashing..................................... 11 3.4 Load faktor............................................ 11 3.5 Hvornår bør hash benyttes?................................... 11 4 Priority Queues 12 4.1 Indledning............................................. 12 4.2 Heap................................................ 12 4.2.1 insert().......................................... 12 4.2.2 remove().......................................... 13 4.2.3 Heapify.......................................... 13 4.3 Priority queues.......................................... 13 5 Searching - Tree Structures 14 5.1 Indledning............................................. 14 5.2 Træ-strukturer generelt..................................... 14 5.3 Søgning.............................................. 14 5.3.1 Lineær søgning...................................... 14 5.3.2 Binær søgning...................................... 14 5.3.3 Binary search trees.................................... 14 5.3.4 AVL trees......................................... 16 1  5.3.5 Treaps........................................... 17 6 Searching - Skip Lists 19 6.1 Indledning............................................. 19 6.2 Skip Lists generelt........................................ 19 6.2.1 Insert........................................... 19 6.2.2 Remove.......................................... 20 6.3 Sammenligning med AVL / Treap............................... 20 7 Sorting 21 7.1 Indledning............................................. 21 7.2 Kvadratiske sorteringsalgoritmer................................ 21 7.2.1 Generelt om kvadratiske sorteringsalgoritmer..................... 21 7.2.2 Insertion sort....................................... 21 7.2.3 Selection sort....................................... 21 7.3 Rekursive sorteringsalgoritmer................................. 22 7.3.1 Generelt om rekursive sorteringsalgoritmer...................... 22 7.3.2 Merge sort........................................ 22 7.3.3 Quick sort......................................... 22 7.4 Radix sort............................................. 23 7.4.1 Tidskompleksitet..................................... 23 7.5 Oversigt over sorteringsalgoritmer............................... 24 8 Graphs - Pathfinding 25 8.1 Indledning............................................. 25 8.2 Grafer generelt.......................................... 25 8.3 Pathfinding............................................ 26 8.3.1 Breadth-First Search (BFS)............................... 27 8.3.2 Dijkstra’s algoritme................................... 27 8.3.3 A*-algoritmen...................................... 28 9 Graphs - Other graph algorithms 29 9.1 Indledning............................................. 29 9.2 Grafer generelt.......................................... 29 9.3 Maximum Flow.......................................... 29 9.3.1 Dantzig’s algoritme.................................... 30 9.4 Minimum Spanning Tree..................................... 30 9.4.1 Prim’s algoritme..................................... 31 9.4.2 Kruskal’s algoritme.................................... 31 9.5 Matching............................................. 32 9.5.1 The stable matching problem.............................. 33 9.5.2 Gale og Sharpley’s algoritme.............................. 33 2  1. Linear Data Structures 1.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Linear Data Structures. Som det første vil datastrukturen Linked List blive introduceret. Her vil den generelle opbygning samt de almindelige operationer for datastrukturen blive præsenteret. Denne præsentation vil have fokus på de tre funktioner insert(), remove() og copy(). Til sidst vil også Stacks og Queues blive præsenteret, da disse kan bygges ud fra Linked Lists. 1.2 Linked Lists 1.2.1 Generel opbygning Består af en række forbundne noder - Hver node består af to felter; info og next - Start-noden (head) refereres via head pointer - Slutningen identificeres via "null" link For Linked Lists er der følgende almindelige operationer: Insert – I starten af listen eller hvilket som helst andet sted Remove – I starten af listen eller hvilket som helst andet sted Traverse – Optælling af noder, søgning, mm... Copying, rotating, splitting, joining, flipping,... 1.2.2 Insert 1 t e m p l a t e v o i d i n s e r t ( Node∗ prevPtr , T i n f o ) 3 { i f ( p r e v P t r == n u l l p t r ) r e t u r n ; 5 Node ∗ n e w I n f o = new Node( i n f o , prevPtr −>n e x t ) ; prevPtr −>n e x t = n e w I n f o ; 7 } 3  headInsert 1 t e m p l a t e v o i d h e a d I n s e r t ( Node∗& headPtr , T i n f o ) 3 { Node ∗ tempPtr = new Node( i n f o , headPtr ) ; 5 headPtr = tempPtr ; } 1.2.3 Remove t e m p l a t e 2 v o i d remove ( Node∗ p r e v P t r ) { 4 i f ( p r e v P t r == n u l l p t r | | prevPtr −>n e x t == n u l l p t r ) r e t u r n ; Node∗ condemmed = prevPtr−>n e x t ; 6 prevPtr −>n e x t = prevPtr−>next−>n e x t ; d e l e t e condemmed ; 8 } 1.2.4 Copy t e m p l a t e 2 Node ∗ copy ( Node∗ s o u r c e P t r ) { 4 i f ( s o u r c e P t r == n u l l p t r ) r e t u r n n u l l p t r ; Node ∗ i t e r a t o r = new Node() ; 6 Node ∗ newHead = i t e r a t o r ; f o r ( s o u r c e P t r ; s o u r c e P t r != n u l l p t r ; s o u r c e P t r = s o u r c e P t r −>n e x t ) 8 { i t e r a t o r −>i n f o = s o u r c e P t r −>i n f o ; 10 i f ( s o u r c e P t r −>n e x t != n u l l p t r ) { 12 i t e r a t o r −>n e x t = new Node() ; i t e r a t o r = i t e r a t o r −>n e x t ; 14 } else { 16 i t e r a t o r −>n e x t = n u l l p t r ; } 18 } r e t u r n newHead ; 20 } 1.3 Stacks og queues 1.3.1 Stacks Lineær data struktur, som er karakteriseret ved: Man kan kun indsætte i toppen Man kan ud udtage fra toppen Stacks kan således betragtes som en LIFO-struktur (last in first out). Der er fire primitive operationer, man kan udføre på en stack: push() - indsætter et element på stacken pop() - fjerner et element fra stacken Figure 1.1: Illustration af 4 en stack  top() - inspicer top element isEmpty() - fortæller om stacken er tom 1.3.2 Queues Lineær data (FIFO)-struktur ("first in first out"), som er karakteris- eret ved: Der er fire primitive operationer på queue; disse tilsvarer opera- tionerne hos stack: push() - indsætter et element på queuen pop() - fjerner et element fra queuen front() - inspicerer det forreste element i queuen isEmtpy() - Boolean. Fortæller om queuen er tom En queue kan implementeres vha. en linked list. Det er fornuftigt at have en tail-pointer, som peger på det bagerste element i køen/listen. Figure 1.2: Illustration af en queue 5 2. Recursion 2.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Recursion. Først vil begrebet rekursion hurtigt blive gennemgået, hvorefter den rekursive opskrift vil blive præsenteret. Efterfølgende vil en række eksempler blive gennemgået, før der til sidst vil følge en diskussion af, hvornår det giver mening at bruge rekursion. 2.2 Hvad er rekursion? Rekursion er en problemløsningsmetode, som bygger på at et problem kan løses ved at løse mindre tilfælde af problemet selv. Rekursive problemer kan inddeles i to tilfælde (cases): Base case – Tilfælde af problemet som ikke kan løses vha. rekursion Rekursiv case – Tilfælde af problemet som kan løses vha. rekursion 2.3 Den rekursive opskrift Når man ønsker at løse et problem rekursivt følges nedenstående opskrift: 1. Formuler problemet ud fra dets størrelse/kompleksitet 2. Find base case (BC) og definer hvorledes det kan løses uden rekursive kald 3. Find den rekursive case (RC) og definer hvorledes denne bevæger sig mod best case efter hvert kald 4. Find belæg for, at RC går mod BC 2.4 Eksempel 1 - Sum En algoritme opstilles, som følger den rekursive opskrift. Denne algoritme finder summen af alle værdier i et givet array. 1. Formuler problemet ud fra dets størrelse/kompleksitet – Algoritmen sum(int* ar, int n), returnerer summen af ’n’ første element i arrayet ’ar’. 2. Find base case (BC) og definer hvorledes det kan løses uden rekursive kald – Base case er når n=0. I dette tilfælde er sum(ar, n) = 0 3. Find den rekursive case (RC) og definer hvorledes denne bevæger sig mod best case efter hvert kald – Rekursiv case er når n>0. I dette tilfælde er sum(ar, n) = ar + sum(ar+1, n-1) 6  4. Find belæg for, at RC går mod BC – Siden n>=0 og n er et heltal, og den rekursive case laver et rekursivt kald med n=n-1, opnås til sidst en situation hvor n=0, hvilket er problemets base case. 2.5 Eksempel 2 - Factorial En algoritme opstilles, som følger den rekursive opskrift. Denne algoritme returnerer det fakrorielle af n. 1. Formuler problemet ud fra dets størrelse/kompleksitet – Algoritmen unsigned int fac(unsigned int n), returnerer factorial af n. 2. Find base case (BC) og definer hvorledes det kan løses uden rekursive kald – Base case er når n=0. I dette tilfælde er fac(n) = 1 3. Find den rekursive case (RC) og definer hvorledes denne bevæger sig mod best case efter hvert kald – Rekursiv case er når n>0. I dette tilfælde er fac(n) = n*fac(n-1) 4. Find belæg for, at RC går mod BC – Siden n>=0 og n er et heltal, og den rekursive case laver et rekursivt kald med n=n-1, opnås til sidst en situation hvor n=0, hvilket er problemets base case. 2.6 Hvornår bør man bruge rekursion? Det er kun rekursive problemer, der har rekursiver løsninger. Og blot fordi et problem har en rekursiv løsning betyder det ikke, at den rekursive løsning nødvendigvis er den bedste. Der gælder generelt følgende: Enhver rekursiv metode kan skrives vha. iteration De fleste simple problemer (sum, factorial) er mere effektivt løst vha. iteration Der er dog tilfælde, hvor det giver mening at anvende rekursion. Der er f.eks. problemstillingen Towers of Hanoi, hvor rekursion præsenterer en elegant løsning på problemet. Desuden giver det mening at anvende rekursion i rekursive data strukturer (trees). 7 3. Maps 3.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Maps. Til start vil der være en kort beskrivelse af Hash Maps, samt hvilke begreber, der knytter sig til dette. Herefter vil der være en beskrivelse af af to forskellige typer af hash maps, "Open-address hash maps" og "Chained hashing". 3.2 Hash Maps Hash maps er en datastruktur, som fordeler elementer over et bredt område. Generelt set er hash maps hurtigere end binær søgning, men kræver til gengæld mere hukommelse. Hash maps gemmer data i key-value par. Keys er unikke mens values ikke behøves at være unikke. Hash maps bruger en Hash funktion til indeksering af data. En af de store fordele ved hash maps er, at indsættelse og fjernelse af elementer i et hash map udføres ved konstant tid (O(1)). 3.2.1 Hash funktionen Hash maps benytter en hash-funktion til indek- sering af data, i modsætning til lineær indekser- ing. Ideelt set returneres et unikt index for hvert unikt key som passes til hash-funktionen. Imidler- tid er dette ikke altid opnåeligt, hvilket resulterer i fænomenerne collisions og clustering. Et eksempel på en hash-funktion kan ses i figur 3.1. 3.2.2 Open-address hash maps Open-address hash maps indsætter key-value par ("records") på næste ubenyttede index. Hvert in- dex i et open-address hash map har således tre Figure 3.1: Hash function eksempel forskellige stadier: OCCUPIED PREV_USED NEVER_USED I open-address hash maps er der følgende bemærkelsesværdige operationer: findIndex(const KeyType & key) - Returnerer indekset for den givne key, hvis denne ikke findes returneres KEY_NOT_FOUND. insert(Key key) - Hvis key allerede eksistere sker der ingenting, ellers indsættes den givne key i det givne map. remove(Key key) - Hvis Key er i det givne map slettes denne. 8  findIndex(const KeyType& key) i n t f i n d I n d e x ( c o n s t KeyType& key ) 2 { i n t nProbe = 0 ; s i z e _ t n E n t r i e s S e a r c h e d = 0 ; 4 i n t index ; i n t hashIndex ; 6 h a s h I n d e x = i n d e x = hash ( key ) ; w h i l e (map [ i n d e x ]. s t a t e != MapEntry : : A d d r e s s S t a t e : : NEVER_USED && n E n t r i e s S e a r c h e d++ != MAP_SIZE) // Keep s e a r c h i n g 8 { i f (map [ i n d e x ]. key != key | | map [ i n d e x ]. s t a t e == MapEntry : : A d d r e s s S t a t e : : PREV_USED) 10 { i n d e x = ( h a s h I n d e x + probe(++nProbe ) ) % MAP_SIZE ; 12 // probe } 14 else { 16 r e t u r n i n d e x ; // Index p o i n t s t o t h e e n t r y a t which key i s found } 18 } r e t u r n KEY_NOT_FOUND; 20 } insert(Key key) v o i d i n s e r t ( c o n s t KeyType& key ) 2 { i n t index = 0 ; 4 i n t hashIndex ; i f ( ( i n d e x = f i n d I n d e x ( key ) ) != KEY_NOT_FOUND) r e t u r n ; // Key a l r e a d y i n map − return 6 // INV : Key i s not i n map 8 i f ( n E n t r i e s U s e d == MAP_SIZE) throw OAHashMapException ( ) ; // Map i s f u l l − no room f o r key 10 i n d e x = h a s h I n d e x = hash ( key ) ; 12 i n t nProbes = 0 ; w h i l e (map [ i n d e x ]. s t a t e == MapEntry : : A d d r e s s S t a t e : : OCCUPIED) 14 i n d e x = ( h a s h I n d e x + probe(++nProbes ) ) % MAP_SIZE ; // p r o b i n g 16 // Open a d d r e s s found − i n s e r t key map [ i n d e x ]. key = key ; 18 map [ i n d e x ]. s t a t e = MapEntry : : A d d r e s s S t a t e : : OCCUPIED; 20 ++n E n t r i e s U s e d ; } remove(Key key) 1 v o i d remove ( c o n s t KeyType& key ) { 3 i n t index ; 5 if ( ( i n d e x = f i n d I n d e x ( key ) ) == KEY_NOT_FOUND) r e t u r n ; 7 map [ i n d e x ]. s t a t e = MapEntry : : A d d r e s s S t a t e : : PREV_USED; −−n E n t r i e s U s e d ; 9 } 9 3.3 Collisions and clustering Collisions, eller kollisioner, opstår, når mere end én key hasher til det samme index. I en situation, hvor et givent index i et hash map allerede er optaget (stadiet OCCUPIED), og et nyt key-value par som hasher til samme index ønskes indsat i hash mappet, er det nødvendigt at finde en ny, ledig plads til det nye key-value par. Metoden, hvorpå denne ledige plads findes, kaldes probing. Primær clustering er betegnelsen for fænomenet, hvor mere end én key hasher til det samme index, og forårsager at den ene key flyttes til den næste ledige plads fundet via probing. Sekundær clustering er betegnelsen for fænomenet, hvor flere primære clusters grænser op til hinanden; herved afhænger tiden, det tager at probe ved kollisioner ikke blot af størrelsen på det primære cluster som er associeret med det index der hashes til, men også af størrelsen af andre indeksers primære clusters. 3.3.1 Probing Probing anvendes, når data hashes til et allerede eksisterende index (dvs. et index som er i stadiet OCCUPIED). For at minimere forekomsten af kollisioner og clusters kan der bruges forskellige former for probing. Af forskellige former for probing findes følgende: Linear probing Kvadratisk probing Figure 3.2: Illustration af forskellige probing 10 3.3.2 Chained hashing Et Chained hash map er en måde at undgå forekomster af kollisioner og clusters. Denne opbevarer data ved at bruge en dynamisk datastruktur (ex: linked list) ved hvert element i det givne hash map, istedet for at gemme data direkte ved hvert index. Dette illustreres i figur 3.3. På denne måde vil alle collisions relaterede problemer blive håndteret internt i datastrukturen, og ansvaret for hash funktionen vil således blive begrænset til at bestemme, hvilket index data skal hashes til. 3.4 Load faktor Hash maps har to faktorer, der spiller ind, når man snakker om dets Figure 3.3: Chained hashing ydeevne. Disse er kapacitet og load faktor. Kapaciteten fortæller hvor mange "pladser", der kan indexes til i det givne hash map. Load faktor fortæller, hvor fyldt et hash map er. En generel regel siger, at load faktoren skal holdes under.75 for at opretholde konstante O(1) insert og remove metoder. Anvendte index Load faktor: α = Mængde af index Hvad er den øvre grænse for α - for OA og chained hashing? Gennemsnitligt besøgte elementer 1 1 - OA hashing, linear probing 2 (1 + 1−α ) α - Chained hashing 1+ 2 3.5 Hvornår bør hash benyttes? Når keys er komplekse – En af de største fordele ved hashing er det lave antal sammenligninger. Dette udnyttes bedst muligt, hvis keys er komplekse. Når en god hash funktion kan udledes – Hurtig udregning af index – Tilnærmelsesvis ensartet fordeling af indexværdier. Når du har overflod af hukommelse – Open-address hash maps er mest effektive når størrelsen på maps er væsentligt højere end det forventede antal key-value par. Dette vil medføre en lav α. – Chained hash maps kan operere med højere datastørrelse, men dette kræver dynamisk hukom- melses allokering. 11  4. Priority Queues 4.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Priority Queue. Til start vil der være en beskrivelse af datastrukturen heap. Efterfølgende vil begreber som minHeap og maxHeap blive præsenteret, samt hvorledes disse relateres til datastrukturen Priority Queue. 4.2 Heap En heap er et binært træ som opfylder følgende betingelser: The Heap property - Data i en node ’n’ er mindre end noderne i ’n’s undertræer(subtrees). Dette er dog kun hvis der er tale om en minHeap. Hvis der var tale om en maxHeap var det selvfølgelig omvendt. The Shape property - Heap er et komplet binært træ. En heap opbevares efter det princip, som er vist på figur 4.1. Dette princip siger at man opbevarer data fra venstre mod højre. I Heap er der følgende bemærkelsesværdige operationer: Figure 4.1: Opbevaring af Heap get() - Denne funktion returnerer det mindste element (min- Heap) insert() - Denne funktion indsætter et element remove() - Denne funktion fjerner det øverste element 4.2.1 insert() Tidskompleksiteten for insert() er O(n ∗ log(n)). 1. Indsæt det givne element i sidste plads i den givne heap. Dette medfører at den overholder shape property. 2. Percolate-Up det nye element. – Percolate-up går ud på rekursivt at sammenligne værdierne af det givne element og dennes ’forældre’, hvis denne værdi er mindre(minHeap) end forældrene byttes disse og der sammen- lignes igen med det angivne elements forældre. Dette foretages indtil at Heap property er overholdt. 1 p e r c o l a t e U p ( i ) : i f heap [ i ] < heap [ p a r e n t ( i ) ] swap ( i , p a r e n t ( i ) ) 3 percolateUp ( parent ( i ) ) ; 12  4.2.2 remove() Tidskompleksiteten for remove() er O(n ∗ log(n)). 1. Erstat det øverste element med det sidste element. Dette medfører at den overholder shape property. 2. Percolate down – Percolate-down går ud på rekursivt at sammenligne værdierne af det givne element og dennes ’børn’, hvis det angivne elements værdi er større end et af børnene byttes disse og der sam- menlignes igen med det angivne elements børn. Dette foretages indtil at Heap property er overholdt. 1 p er c ol a te D ow n ( i ) : s m a l l e s t = i n d e x o f s m a l l e s t c h i l d o f i i f heap [ i ] > heap [ s m a l l e s t ] 3 swap ( i , s m a l l e s t ) p er c ol a te D ow n ( s m a l l e s t ) ; 4.2.3 Heapify Heapify er processen hvorved et binært træ bliver omdannet til en Heap datastruktur. Processen består i først at Percolate-down alle "non-leaf" noder i omvendt rækkefølge. Der gælder for en given non-leaf node ’n’, at ’n’s undertræer er heaps. Dette betyder dog ikke at ’n’ er en heap, denne kan godt være placeret forkert. Dette foretages indtil alle noder er blevet percolated og der opnåes en heap datastruktur. 4.3 Priority queues Priority queue er en datatype som minder om queue, men som adskiller sig ved tildelingen af prioritet for hvert element i datastrukturen. Prioriteringen søger det formål at mindste det arbejde det kræver at udtage elementer med højest/lavest prioritet. Således vil data, som poppes, komme ud i rækkefølge efter prioritet. Den data med højest prioritet vil blive returneret først. Eksempler på implementeringer af priority queues vha. heaps inklud- erer: maxHeap – En maxHeap, dvs. en heap, hvor det øverste element er det højest prioriterede element i heapen, er et eksempel på en priority queue implementering. minHeap – En minHeap, dvs. en heap, hvor det øverste element er det lavest prioriterede element i heapen, er et andet eksempel Figure 4.2: maxHeap på en priority queue implementering. Figure 4.3: minHeap 13 5. Searching - Tree Structures 5.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Searching - Tree Structures. Til start vil der være en generel beskrivelse af træ-strukturer. Herefter vil der være en beskrivelse af Søgning, samt eksempler på måder at søge på. Til sidst vil der være en beskrivelse af følgende datastrukturer; "Binary search trees", "AVL trees" samt "Treeps", som alle er træ-strukturerer, der optimerer data til fordel for søgning. 5.2 Træ-strukturer generelt Et tree er en datastruktur bestående af elementer ("noder"), startende fra root node, der hver inde- holder en værdi samt en referenceliste til den pågældende nodes "børn". Det gælder for trees, at der ikke må eksistere cykler i datastrukturen. Et binært træ er således et tree, hvor hver node har to "børn" (left/right child). Man kan betragte et tree enten som bestående af ingen nodes (et tomt tree), eller som bestående af én node med pointere til sine child-nodes, der hver især er også er trees. En node uden børn kaldes for en leaf node. 5.3 Søgning Søgning efter bestemte informationer i store datasæt er overordentligt vigtigt at kunne gennemføre hurtigt, og det bliver stadigt vigtigere at kunne søge hurtigt i takt med at de tilgængelige informations- mængder blot fortsætter med at vokse. Hurtige søgetider er altafgørende også i forretningssammenhæng. I de følgende afsnit vil to relativt simple søgealgoritmer i lineære strukturer være beskrevet, Lineær- og Binær-søgning. Bemærk at lineær søgning er langsom, men ikke stiller krav til organiseringen af data, mens binær søgning er meget hurtigere, men stiller krav til at data er sorteret. 5.3.1 Lineær søgning Lineær søgning er en søgningsalgorite, som finder index på den værdi, som passer på den givne søgeværdi i et "vilkårligt" (ikke sorteret) array. Lineær søgning tjekker hvert element af listen eller array’et indtil den finder det element som passer med den givne søgeværdi. Tidskompleksiteten for denne søgning vil være O(n), hvor n er antal elementer i listen. 5.3.2 Binær søgning Binær søgning er en søgningsalgoritme, som finder index på den værdi, som passer på den givne søgeværdi, i et sorteret array. Binær søgning sammenligner den givne søgeværdi med det midterstre elemenet i det givne array. Hvis disse ikke er ens, søges der igen på den halvdel, hvor den givne søgeværdi må befinde sig. Tidskompleksiteten for denne søgning vil være O(logn), hvor n er antal elementer i det givne array. 5.3.3 Binary search trees Et binary search tree (BST) er et binært træ, som har fået pålagt en række regler. Ved overholdelse af disse regler kan man søge meget effektivt i træet. Følgende regler gør sig gældende for et BST: Alle knuder til venstre for en given knude har data mindre eller lig knuden 14  Alle knuder til højre for en given knude har data større end knuden Search Søgning i et BST har en worst case søgetid på O(d), hvor d er dybden af træet. Følgende forklarer proceduren for at søge i et BST: 1. Start ved root 2. Er dette noden? Hvis nej gå til 3, ellers er noden fundet 3. Hvis noden der søges er større end den aktuelle node, da gå til højre. Ellers venstre. Start ved punkt 2 Ovenstående procedurer fortsætter indtil noden er fundet eller dybden er nået. Insert Insert i et BST har en worst case søgetid på O(d), hvor d er dybden af træet. For et BST gælder, at nye noder indsættes som blade. Illustrationen i figur 5.1 præsenterer hvorledes insert funktionen fungerer. Fra illustrationen er det således muligt at op- stille en opskrift for insert: 1. Start ved root 2. Er data som skal indsættes større, da gå til højre. Ellers gå til venstre. Når man når så langt man kan komme er det her, som data skal indsættes. Figure 5.1: Illustration af BST insert Remove For remove gælder ligeledes, at denne har en worst case eksekveringstid på O(d), hvor d er dybden af træet. Remove er mere komplekt end tidligere beskrevne BST operationer, da denne skal tage hånd om at bevare BST strukturen. Følgende beskriver fremgangsmåden for remove operationen: 1. Søg efter noden, som skal fjernes 2. Hvis noden ikke er et blad, da udskift noden med en anden node, som er lettere at fjerne 3. Fjern den duplikerede node Figure 5.2: Først lokaliseres Figure 5.3: Den største node, Figure 5.4: Den originale duplik- noden, som skal fjernes (17). som er mindre end den aktuelle erede node fjernes Denne node er ikke et blad, node, lokaliseres (14). Den ak- hvilket er hvorfor vi går til skridt tuelle node (17) udskiftes nu med to i ovenstående tabel denne 15 5.3.4 AVL trees Et AVL tree er et selvbalancerende BST, idet det, for hver af de muterende operationer (insert() og remove()) sørger for at opretholde balance overalt i træet efter en speciel "balance condition".Det gør indsættelse og fjernelse noget mere omfattende, men til gengæld gør det søgning meget hurtig, idet balance konditionen garanterer at dybden af træet - og dermed søgetiden worst-case er O(log(n)). Balance konditionen er: For hver knude i et træ, må højdeforskellen mellem venstre og højre undertræ ikke over- stige 1. Figure 5.5: Tilfælde af ubalance Bemærk at der ikke forefindes duplikerede knuder i et AVL træ. Der forefindes fire forskellige tilfælde af ubalance i en node ’k’ i et AVL træ. 1. In the left subtree of the left child of k (left-left case 1) 2. In the right subtree of the left child of k (right-left case 2) 3. In the left subtree of the right child of k (left-right case 3) 4. In the right subtree of the right child of k (right-right case 4) Generelt kan der siges at case 1 og 4 repræsenterer "Outside cases" og case 2 og 3 repræsenterer "Inside cases". En grafisk repræsentation af de fire tilfælde af ubalance kan ses på figur 5.5. Rotationer Hvert tilfælde af ubalance kan fikses ved at anvende de rigtige rotationer. Outside cases – left-left case -> right single rotation. – right-right case -> left single rotation. Inside cases – left-right case -> right-left double rotation. – right-left case -> left-right double rotation. Efter imbalance correction vil balancen være genoprettet. 16  Figure 5.6: SingleRotation Figure 5.7: Double Rotation Imbalance correction procedure Find knuden ’k’ hvor der er en ubalance. Bestem tilfælde af ubalance. Udfør korrekt rotation til at genoprette balancen baseret på tilfældet af ubalancen. Insertion Ubalance efter indsættelse af et nyt element kan blive balanceret ved brug af en operation. 1. Indsæt den givne knude som ved et BST. 2. balancér træet, hvis der er nogen ubalance, ved at tjekke for ubalance fra den indsatte knude og til roden af AVL træet. Deletion Det er ikke garanteret at et AVL træ kan balanceres med kun en rotation efter en sletning af et element. 1. Fjern den givne knude som ved et BST. 2. Der tjekkes for ubalance fra den givne knude til roden af AVL træet. 5.3.5 Treaps Denne datastruktur har sit navn fra en sammetrækning af "Tree" og "Heap". I en Treap er data organiseret som i et binært søgetræ, dvs. alt til venstre for en given node er mindre, alt til højre er større. Idet en treap søger at opretholde balance i træet, tildeles hvert element der indsættes i treapen en prioritet; denne benyttes til at opretholde en heap property på træet (se afsnit 4.2). Search For treaps benyttes den samme search-metode som for et BST. 17 Insert 1. Opret en ny node med en key x og værdi y. 2. Benyt standard BST indsættelse til at indsætte den nye node. 3. Hver nyligt oprettet node har en tilfældigt angivet prioritet, så heap property kan være brudt. Rotationer benyttes til at sørge for at den indsatte nodes prioritet følger heap property. - Hvis en ny node indsættes i ventre subtræ, og root node for det venstre subtræ har højere prioritet, roteres til højre. - Hvis en ny node indsættes i højre subtræ, og root node for det højre subtræ har højere prioritet, roteres til venstre. Remove 1. Hvis noden er et leaf (ikke har child nodes), kan den slettes uden videre. 2. Hvis noden har et child node som er NULL (tomt tree), samt en child node som ikke er det, erstattes noden med sin ikke-tomme child node. 3. Hvis noden har to child nodes som ikke er NULL, findes den child node som har den højeste prioritet af de to child nodes. - Hvis den højre child node’s prioritet er størst, udføres venstre rotation på noden. - Hvis den venstre child node’s prioritet er størst, udføres højre rotation på noden. 18 6. Searching - Skip Lists 6.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Searching - Skip Lists. Første punkt vil introducere Skip Lists samt hvad der for denne datastruktur er interessant. Efterfølgende vil de muterende operationer for Skip Lists blive præsenteret. Til slut sammenlignes Skip Lists med træ-strukturer, hvis søgetid er den samme som for Skip Lists. 6.2 Skip Lists generelt Skip lists er et probabilistisk alternativ til bal- ancerede træer og bliver af mange betragtet som lettere at implementere. Skip listen er bygget op som en række af linked lists, hvor hver række kom- mer til udtryk i form af de niveauer, som tildeles noderne i listen. Niveauerne tildeles probabilistisk Figure 6.1: Illustration af Skip List således, at der gerne skulle være halvt så mange noder på niveau to, som der er på niveau et. Og halvt så mange noder på niveau tre, som der er på niveau to - osv. osv. Skip Listen fungerer ved at indsætte data i sorteret orden. Søgning forgår vha. såkaldte fast lanes, som tillader operationen at sprænge elementer over for på denne måde at effektivisere søgningen. Figur 6.1 illustrerer søgning efter en node med tallet 10. Her ses hvorledes operationen starter på øverste niveau i head node for på denne måde at sprænge noderne med data 2, 3, 4 og 8 over. Tidskompleksitet Skip Lists har en gennemsnitlig tidskompleksitet på O(log(n)). Dette skyldes det brugen af coin toss ved indsættelse af elementer i Skip Lists, der sikrer at noder ved oprettelse har en sandsynlighed på 50% for også at fremgå i listen et eller flere niveauer højere oppe. I særligt uheldige situationer kunne det forestilles at samtlige elementer i en Skip List eksisterer i samtlige niveauer (samme niveau), hvilket medfører en worst-case tidskompleksitet for søgning i Skip Lists på O(n). Dette er dog ekstremt us- andsynligt, og for en Skip List bestående af 1000 elementer er der således kun 1 : 1018 sandsynlighed for at en søgning tager mere end 5 gange den forventede tid. 6.2.1 Insert For at indsætte en node i en skip list, søges der fra højeste level efter den givne værdi, som skal indsættes, ved at sammenligne værdien af den næste node med den værdi, som ønskes indsat i en skip list. De basiske principper er: Værdi af næste node er mindre end værdi, som skal indsættes. Dette medfører at vi skal bevæge os videre ad samme level. Værdi af næste node er større end værdi, som skal indsættes. Dette medfører at en pointer til denne node gemmes i en vector update, som holdes opdateret således at update[i] indeholder en pointer til den node længest til højre af level i eller højere, som er til venstre for indsættelses positionen. Desuden bevæges der et level ned. 19  Ved level 0, er det altid muligt at indsætte en given node. Når pladsen er fundet for den node, som skal indsættes, vælges nodens level tilfældigt ved brug af et såkaldt "coin-toss". Det såkaldte "Coin-toss" skal implementeres således at vi opnår en fordeling af elementer, hvor halvdelen af noder, som har niveau i pointers også har niveau i+1 pointers. Algoritmen til at imple- mentere dette følger følgende pseudo kode: i n t randomLevel ( ) 2 { i n t l v l := 1 4 // random ( ) t h a t r e t u r n s a random v a l u e i n [ 0... 1 ) w h i l e random ( ) < p and l v l < MaxLevel do 6 l v l := l v l + 1 8 return l v l } En grafisk illustration over indsættelse af en node i en skip list kan ses på figur 6.2. Figure 6.2: Illustration af insert i Skip List 6.2.2 Remove For at fjerne en node i en skip list, søges der på samme måde som ved indsættelse af en node. Når noden fjernes forbindes de nu uforbundne noder. Efter hver fjernelse af en node tjekkes der om hvorvidt vi har fjernet det maksimale level i listen. Hvis dette er tilfældet dekrementeres det maksimale antal levels. 6.3 Sammenligning med AVL / Treap I forhold til balancerede træstrukturer som AVL/Treap er Skip Lists som nævnt betragtet som lettere at implementere. AVL træer har en worst case tidskompleksitet på O(log(n)) for operationerne search, insert og remove, imens denne hos både Treap og Skip Lists er O(n). Visse balancerede træer besidder altså en fordel i henhold til worst case tidskompleksitet rent teoretisk, men er til gengæld en del sværere at implementere. 20 7. Sorting 7.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Sorting. Til start vil en række kvadratiske sorteringsalgoritmer blive præsenteret, samt hvorledes disse opererer. Efterfølgende vil der følge en gennemgang af de rekursive sorteringsalgoritmer; Merge sort og Quick sort. En præsentation af Radix sort er til sidst inkluderet. 7.2 Kvadratiske sorteringsalgoritmer 7.2.1 Generelt om kvadratiske sorteringsalgoritmer Ved kvadratiske sorteringsalgoritmer forstås sorteringsalgoritmer som har en (worst-case) tidskomplek- sitet på O(n2 ). Disse indbefatter bl.a. algoritmerne: Bubble sort, Insertion sort og Selection sort, hvoraf de to sidstnævnte vil blive beskrevet yderligere i det følgende. Fælles for disse er at de opererer in-place, hvilket vil sige at sorteringen foregår i samme hukommelsesområde som det datasæt, der sorteres. Dermed allokeres ingen ny hukommelse ved sortering af et datasæt. Desuden er både Insertion sort og Selection sort komparative sorteringsalgoritmer, hvilket vil sige at de benytter sammenligning af elementer i datasættet til at foretage sortering (i modsætning til eks. Radix sort). 7.2.2 Insertion sort Insertion sort fungerer efter følgende simple opskrift: 1. En del af arrayet vil altid være sorteret, resten vil være usorteret 2. Ved hver iteration indsættes det første usorterede element ind i rækken af sorterede elementer 3. Således udvides antallet af sorterede elementer med en 4. Fortsæt indtil den usorterede del af arrayet er tomt For Insertion sort vil det bedst mulige input være et allerede Figure 7.1: Insertion sort sorteret array. I dette tilfælde ville ville tidskompleksiteten for Insertion sort være O(n). 7.2.3 Selection sort Selection sort fungerer efter følgende simple opskrift: 1. En del af arrayet vil altid være sorteret, resten vil være usorteret 2. Ved hver iteration vælges det mindste usorterede element. Dette swappes med det første element i den usorterede del. 3. Således udvides antallet af sorterede elementer med en. Figure 7.2: Selection sort 4. Fortsæt indtil den usorterede del af arrayet er tomt For Selection sort vil tidskompleksiteten altid være O(n2 ). Dette skyldes, at Selection sort altid vil kigge hele rækken af usorterede elementer igennem, før den er sikker på, at den har fundet det mindste element (jf. punkt 2 i ovenstående liste). 21  7.3 Rekursive sorteringsalgoritmer 7.3.1 Generelt om rekursive sorteringsalgoritmer Rekursive sorteringsalgoritmer tillader en sortering af n elementer med en tidskompleksitet på O(n ∗ log(n)). Disse indbefatter bl.a. algoritmerne: Merge sort og Quick sort. Fælles for begge sorteringsal- goritmer er at de fungerer efter divide and combine princippet. 7.3.2 Merge sort Merge sort fungerer efter divide and combine princippet, hvor sorteringen bliver udført ved først at sortere mindre (rekursion) dele af arrayet. Føl- gende liste beskriver strategien bag Merge sort: 1. Split arrayet op i to lige store dele 2. Hvis størrelsen på arrayet er 1 er sorteringen fuldendt 3. Ellers sorteres array rekursivt Figure 7.3: Illustration af Merge Sort 4. Kombiner (merge) resultatet af de to sorterede sub-arrays til et samlet resultat For Merge sort gælder, at den ikke opererer in-place. Den kopierer altså data, og bruger således tid på at oprette dynamisk hukommelse. Tidskompleksiteten for Merge sort er O(n ∗ log(n)). Implementering af Merge sort 1 // P r e c o n d i t i o n : data i s an a r r a y with a t l e a s t n components // P o s t c o n d i t i o n : The e l e m e n t s a r e s o r t e d i n a s c e n d i n g o r d e r 3 v o i d m e r g e s o r t ( i n t ∗ data , s i z e _ t n ) { 5 s i z e _ t n1 ; // s i z e o f t h e f i r s t s u b a r r a y s i z e _ t n2 ; // s i z e o f t h e s e c o n d s u b a r r a y 7 i f (n > 1) 9 { n1 = n / 2 ; 11 n2 = n − n1 ; 13 m e r g e s o r t ( data , n1 ) ; // data [ 0.. n1 [ m e r g e s o r t ( data + n1 , n2 ) ; // data [ n1.. n [ 15 merge ( data , n1 , n2 ) ; 17 } } 7.3.3 Quick sort Quick sort fungerer efter divide and combine princippet, hvor sorteringen bliver udført ved først at sortere mindre (rekursion) dele af arrayet. Det primære arbejde i Quick sort ligger i at dele arrayet op i mindre dele. Average case tidskompleksitet for Quick sort er O(n ∗ log(n)). Følgende beskriver strategien bag Quick sort: 1. Vælg en pivot 2. Del arrayet op i to halve: Mindre-end-pivot elementer Større-end-pivot elementer 22  3. Sorter arrayet rekursivt 4. [Mindre-end-pivot elementer]+[pivot element]+[større-end-pivot elementer] udgør nu et helt, sorteret array For Quick sort gælder, at denne tillader par- allelisering. Dette betyder, at flere tråde kan op- erere på data samtidig. Trådene kan operere på de rekursive sub-arrays og på denne måde få sorterin- gen til at køre parallelt. For Quick sort gælder yderligere, at denne opererer in-place. Den ar- bejder altså direkte i det tildelte array og bruger således ikke tid på at oprette dynamisk hukom- melse. For Quick sort eksisterer tre former for worst- case input: Array er allerede sorteret i rigtigt række- følge. Array er allerede sorteret i omvendt række- følge. Alle elementer er identiske. I ovenstående tilfælde ville tidskompleksiteten for Quick sort være O(n2 ). 7.4 Radix sort Figure 7.4: Illustration af Quick Sort Radix sort er en "non-comparing" sorteringsalgoritme som sorterer data ved at gruppere dem efter hvert individuelle ciffers position og værdi. Det at Radix sort er "non-comparing" betyder at der ikke foregår sammenligninger af data i sorteringen, men i stedet grupperes dataene efter kendte parametre. Radix sort bruger en ekstern data struktur til at sortere elementer i forskellige "buckets". "in-place" algoritmer kræver at alt data bliver manipuleret i det originale array, uden at allokere ekstern hukom- melse. Det er dog muligt at implementere radix sort som en "in-place" algoritme, men denne vil have meget til fælles med quick sort, som deler datasættet i forskellige sektioner i det originale array. Dette vil dog medføre at radix sort ikke længere vil være "stable" da der ikke er garanti for at den originale rækkefølge bliver overholdt. Når en algoritme betegnes som "stable" betyder det at de elementer, som eksempelvis er duplikeret eller har samme værdi, skal fremgå i original rækkefølge i det sorterede datasæt. 7.4.1 Tidskompleksitet De algoritmer som involverer sammenligning "comparing" værdier har en "best-case" tidskompleksitet på O(n ∗ log(n)), hvor n er størrelsen på det array som skal sorteres, algoritmer som ikke involverer sammenligning af værdier kan opnå en bedre "best-case" tidskompleksitet. Radix sort specifikt har en tidskompleksitet på O(n ∗ d), hvor d er antallet af cifre i det største af de n elementer der skal sorteres. Dette skyldes at hver position i det datasæt, som skal sorteres, skal processeres d antal gange, da d er antallet af cifre i det største af de n elementer. At processere en position kræver at sortere n værdier derved kræver hver iteration af det ydre loop O(n). Tilsammen giver det O(n ∗ d). 23 7.5 Oversigt over sorteringsalgoritmer Table 7.1: Oversigt over tidskompleksitet for sorteringsalgoritmer Navn Best case Average case Worst case Stabil Bubble sort O(n) O(n2 ) O(n2 ) Ja Insertion sort O(n) O(n2 ) O(n2 ) Ja Selection sort O(n2 ) O(n2 ) O(n2 ) Nej Merge sort O(n ∗ log(n)) O(n ∗ log(n)) O(n ∗ log(n)) Ja Quick sort O(n ∗ log(n)) O(n ∗ log(n)) O(n2 ) Hvis in-place, sandsynligvis ikke. Dog muligt. Radix sort O(n ∗ d) O(n ∗ d) O(n ∗ d) Ja (bortset fra in-place MSD Radix sort). 24 8. Graphs - Pathfinding 8.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Graphs - Pathfinding. Som det første vil datastrukturen Graph kort blive benævnt, samt hvilken terminologi der for denne gør sig gældende. Efterfølgende vil begrebet Pathfinding blive introduceret sammen med en række algoritmer, hvis virke beskæftiger sig inden for dette emne. Disse algoritmer er: Breadth-First Search, Dijkstra’s algoritme samt A*-algoritmen. 8.2 Grafer generelt En graf er en struktur som består af knuder og kanter. Grafer anvendes til at giver en grafisk repræsen- tation af en række problemer, som eksempelvis et navigationssystem. For at opnå en forståelse af grafer er det vigtigt at forstå terminologien, som vil blive beskrevet i det følgende. Directed graphs - Envejs navigérbare kanter. - se figur 8.1 Undirected graphs - Tovejs navigérbare kanter. - se figur 8.2 Connected graphs - Der er en path imellem alle noder. - se figur 8.3 Disconnected graphs - Der er ikke en path imellem alle noder. - se figur 8.4 Weighted graphs Kanter har en tildelt vægt i form at en talværdi. - se figur 8.5 Unweighted graphs Kanter har ikke en vægt. - se figur 8.6 Cyclic graphs Grafer som indeholder mindst 1 cycle - se figur 8.7 Acyclic graphs Grafer som ikke indeholde nogen cycles - se figur 8.8 Path - En sekvens af kanter. – Paths fra A til F på figur 9.2 omfatter: ∗ (A, B, E, F), (A, B, C, E, F), (A, B, C, E, F, E, F) osv. Figure 8.1: Illustration Figure 8.2: Illustration Figure 8.3: Illustration Figure 8.4: Illustration af en Directed graph. af en Undirected graph. af en Connected graph. af en Disconnected graph. 25  Figure 8.5: Illustration Figure 8.6: Illustration Figure 8.7: Illustration Figure 8.8: Illustration af en Weighted graph. af en Unweighted graph. af en Cyclic graph. af en Acyclic graph. 8.3 Pathfinding Pathfinding eksisterer, da man i en graf ofte vil vide, hvorledes man kommer fra én knude til en anden. En række algoritmer eksisterer for at kunne løse dette. Disse er som følger: Breadth-First Search (BFS) Dijksra’s Algoritme A* Algoritmen Ovenstående algoritmer følger alle den samme struktur. Ydermere ar- bejder disse ud fra samme ide. Ideen går ud på at holde øje med frontier, som er en datastruktur, der opbevarer noder. Det er fra Figure 8.9: Pathfinding denne, at man vælger den næste node, som skal udforskes. Den generelle stuktur for de tre algoritmer er som følger: 1. Initier frontier og tilføj start node til denne 2. Gør følgende mens frontier ikke er tom: 1. Vælg og fjern en node n fra frontier 2. Marker n som besøgt 3. Tilføj alle n’s ikke-besøgte naboer til frontier Eksempel - Generel Struktur // Find a path from s t o t 2 FindPath ( Graph g , Node s , Node t ) { 4 // I n i t i a l i z i n g f r o n t i e r = new Queue ( ) ; // The s e t o f nodes y e t t o e x p l o r e 6 s. prev = n u l l ; // S t a r t node has no p r e v i o u s node f r o n t i e r. push ( s ) ; // Add s t a r t node t o t h e f r o n t i e r 8 // E x p l o r e nodes 10 w h i l e ( ! f r o n t i e r. isEmpty ( ) ) { 12 current = f r o n t i e r. get () ; // g e t ( ) ~ f r o n t ( ) + pop ( ) i f ( c u r r e n t == t ) r e t u r n ; // Path found − e a r l y e x i t 14 f o r e a c h ( Node n i n c u r r e n t. n e i g h b o r s ) 16 { i f ( n. p r e v == n u l l ) // n has not been v i s i t e d b e f o r e 18 { n. prev = c u r r e n t ; 20 f r o n t i e r. push ( n ) ; } 22 } } 24 } 26 8.3.1 Breadth-First Search (BFS) BFS er en pathfinding algoritme, som traverserer samtlige af en nodes nabo-noder, før disses naboer da traverseres. BFS kan benyttes i datastrukturer som eksempelvis trees og graphs. BFS er meget simpel - praktisk talt en direkte implementering af den generelle fremgangsmåde - se kodeudsnit 8.3. BFS finder den korteste vej fra Start node til To node for en uvægtet graf. – Hvis BFS ikke afslutter "tidligt", findes den korteste vej fra S til samtlige andre noder i den uvægtede graf BFS besøger samtlige noder i en graf, hvilket gør den særligt brugbar som traverseringsalgoritme. – Dette medfører dog at BFS ikke er særligt effektiv til at finde den korteste vej i meget store grafer (den besøger mange knuder på vejen) BFS tager ikke højde for kanters vægt, men kun antallet af kanter. 8.3.2 Dijkstra’s algoritme Dijkstra’s algoritme finder den korteste vej i en vægtet graf. Den korteste vej defineres som vejen, hvis sum af vægtede kanter er minimal. Algoritmen er opfundet er Edgar Dijkstra i 1959. Ved at modificere den generelle struktur en smule kan algoritmen implementeres Der tilføjes en pris til alle noder. Denne symboliserer omkostningen for at komme fra start noden til den enkelte node Figure 8.10: Dijkstra’s algoritme med tilhørende eksempel-graf Væsentlige bullet-points for Dijkstra’s algoritme: Dijkstra’s algoritme kan til dels håndtere negative vægte på kanter. Den kan håndtere det i tilfælde, hvor grafen ikke indeholder cykler Dijkstra’s algoritme kan godt håndtere et kant-til-selv scenarie Dijkstra’s algoritme vil fungere som BFS, hvis denne bliver kørt på en graf, hvor alle kanter har den samme vægt Dijkstra’s algoritme kan godt fungere med en FIFO queue. Dog er denne hurtigere ved valg af priority queue 27  8.3.3 A*-algoritmen A* er en pathfinding algoritme som prioriterer veje der "lader til" at føre tættere på den angivne target node. A* udvælger den node som minimerer funktionen f(n) = g(n) + h(n), hvor: – n er noden, – g(n) er omkostningen fra S til n – h(n) er heurestikken mellem n og T A* algoritmen benytter "heurestik" til at udvælge den næste node, som skal traverseres. Heurestik er en metode der rangerer noderne i frontier for at bestemme den næste node, som skal undersøges. – Heurestik kan benyttes i situationer, hvor man kan tale om en afstand (f.eks. rent fysisk, i et koordinatsystem, eller i tid). – Kræver at begrebet "tættere på" giver mening mellem noderne. – Ved at benytte heurestik udvælges de bedste noder som kandidater til en del af den fundne vej først Klassiske måder at udregne heurestik i et grid inkluderer: Table 8.1: Oversigt over heurestik-udregninger Manhattan 4-vejs bevægelse h(n) = |∆x| + |∆y| Diagonal 8-vejs bevægelse h(n) = max(|∆x|, |∆y|) Euclidian Any-direction bevægelse h(n) = dist(n, T ) // Find a path from s t o t 2 // Pre : A l l nodes i n g have n. c o s t = i n f i n i t y and n. p r e v = n u l l FindPathAStar ( Graph g , Node s , Node t ) 4 { // I n i t i a l i z i n g 6 f r o n t i e r = new P r i o r i t y Q u e u e ( ) ; // Nodes i n s e r t e d with c o s t + h ( n ) a s p r i o r i t y s. p r e v = None ; 8 s. cost = 0 // Cost o f g e t t i n g from s t o s i s 0 f r o n t i e r. push ( s , 0 ) ; 10 // E x p l o r e nodes 12 w h i l e ( ! f r o n t i e r. isEmpty ( ) ) { 14 current = f r o n t i e r. get () ; i f ( c u r r e n t == t ) r e t u r n ; // Path found , e a r l y e x i t 16 f o r e a c h ( Node n i n c u r r e n t. n e i g h b o r s ) 18 { i f ( c u r r e n t. c o s t + edge ( c u r r e n t , n ). w e i g h t < n. c o s t ) // Lower−c o s t path from s t o n 20 { n. c o s t = c u r r e n t. c o s t + edge ( c u r r e n t , n ). w e i g h t ; 22 p r i o r i t y = n. cost + h(n , t ) ; n. prev = c u r r e n t ; 24 f r o n t i e r. push ( n , p r i o r i t y ) ; } 26 } } 28 } 28 9. Graphs - Other graph algorithms 9.1 Indledning Det følgende vil beskrive de overordnede emner og fokuspunkter, som er at finde under overskriften Graphs - Other graph algorithms. Som det første vil der være en henvisning til en kort beskrivelse af datastruktutren Graph. Efterfølgende vil en række algoritmer, hvis virke beskæftiger sig indenfor dette emne, blive beskrevet. Disse algoritmer omfatter: Dantzig’s algoritme indenfor begrebet Maxi,um Flowm Prim’s algoritme og Kruskal’s algoritme indenfor begrebet Minimum Spanning Tree. Desu- den vil begrebet Matching blive benævnt. 9.2 Grafer generelt Dette står beskrevet i afsnit 8.2. 9.3 Maximum Flow Maksimalt flow eller Maximum Flow omhandler at sikre størst flow gennem en graf. Givet en source- knude og en sink-knude i en graf, og et mellemliggende "netværk" af knuder, kan maximum-flow- algoritmer afgøre hvilke veje gennem netværket, der skal benyttes, for at sikre at det største flow når fra source til sink. I forbindelse med Maximum Flow gør følgende terminologi sig gældende: Residual capacity En kants ubrugte kapacitet (hvor meget flow, der stadig kan bevæges igennem en given kant) Residual graph En tovejs navigerbar graf, som viser residual capacity på kanterne i grafen Augmenting path En envejs navigerbar vej fra source til sink i en residual graf hvor hver kant har positiv residual kapacitet Residual capacity of the augmenting path Den mindste residual kapacitet i en augmenting path Figure 9.1: Illustration af en residual graf Figure 9.2: Illustration af augmenting path 29 9.3.1 Dantzig’s algoritme Dantzig’s algoritme finder det maksimale flow fra source-knude til sink -knude gennem en graf med envejs navigerbare knuder. Algoritmen fungerer på følgende vis: Find augmenting paths og opdater den residuelle graf til at afspejle denne vej Når der ikke kan findes flere augmenting paths er der optimalt flow. Den residuelle graf viser det optimale flow Figur 9.3 præsenterer hvorledes Dantzig’s algoritme virker. Figure 9.3: Eksempel på hvorledes Dantzig’s algoritme kører på en graf 9.4 Minimum Spanning Tree This text is here. Et minimum spanning tree (MST) for en graf G er en anden graf G0 hvorom det gælder: G’ er et træ, dvs. det indeholder cykler. G’ udspænder G, dvs alle knuder i G er forbundet i G’. G’ r minimalt, dvs. summen af kanternes vægt er minimal. Figure 9.4: Eksempel på en Et MST er særdeles anvendeligt i real-life applikationer, f. eks. til at graf bestemme langs hvilke strækninger i et vejnet man skal grave kabler ned langs for at servicere samtlige husstande billigst muligt. Der findes flere algoritmer til at finde et MST for en graf. I det følgende vil "Prim’s" og "Kruskal’s" algoritmer blive benævnt. Et minimum spanning tree har følgende egenskaber: Lad en graf G blive defineret som G = (V, E) hvor V er et sæt af noder og E er et sæt af kanter(vist som et sæt af noder). – Eksempel fra figur 9.4: Figure 9.5: Minimun spanning – V = A, B, C, D, E, F, G, H tree fundet med Prim’s algo- – E = A, B, A, D, B, C, B, D, B, E, C, E, C, F, C, G, D, E, ritme i startknuden A. E, F, E, H 30  |E 0 | = |V | − 1 dvs at antal kanter er lig antal knuder −1. Maximum Acyclicity - Hvis der tilføjes en ekstra kant vil der være en cycle i MST. Minimum Connectivity - Hvis der fjernes en kant vil MST træet være disconnected. |V |− 2 Det maksimal antal MST is givet som |V | 9.4.1 Prim’s algoritme Prim’s algoritme finder det mindst udspændte træ (MST) som udspænder sig over alle knuder i en connected, undirected, weighted graph. Den generelle idé er at starte ved en given start knude og derefter tilføje de mindst vægtede kanter til MST indtil alle knuder er er forbundet. Pseudokoden for denne algoritme kan ses i det følgende: 1 Prim ( Graph g , Node s t a r t ) { 3 Graph g’ ; Edges minSpanTree ; // Holds s e t o f e d g e s t h a t form min. s p a n n i n g t r e e 5 g’. add ( s t a r t ) ; 7 w h i l e ( | g’. nodes | != | g. nodes | ) // S t i l l nodes t o add... { 9 s e l e c t l e a s t −w e i g h t edge {u , v} from g such t h a t u i s i n g’ and v i s not minSpanTree. add ( { u , v } ) 11 g’. add ( v ) } 13 // When we g e t t o h e r e , t h e min. s p a n n i n g t r e e s p a n s a l l nodes 15 r e t u r n minSpanTree } 9.4.2 Kruskal’s algoritme Kruskal’s algortime finder det mindst udspændte træ som udspænder sig over alle knuder i en connected, undirected, weighted graf. Den generelle idé er at betragte grafen som en helhed og tilføje de lavest vægtede kanter til MST, medmindre det resulterer i en cycle. Dette gentages indtil alle noder er forbundet i det mindst udspændte træ. Bemærk at Kruskal’s algoritme ofte bygger en masse små MST op for senere at forbinde dem til et større MST, som udspænder sig over alle knuder. Pseudokoden for denne algoritme kan ses i det følgende: 1 K r u s k a l ( Graph g ) { 3 Graph g’ ; Edges minSpanTree ; // Holds s e t o f e d g e s t h a t form min. s p a n n i n g t r e e 5 w h i l e ( | g’. nodes | != | g. nodes | ) // S t i l l nodes t o add... 7 { s e l e c t l e a s t −w e i g h t edge {u , v} from g ( such t h a t no c y c l e i s formed i n MST) 9 minSpanTree. add ( { u , v } ) g’. add ( v ) 11 } 13 // When we g e t t o h e r e , t h e min. s p a n n i n g t r e e s p a n s a l l nodes r e t u r n minSpanTree 15 } 31 9.5 Matching Matching omhandler at matche to knuder fra hvert sit sæt af knuder, så at matchingen er optimal under en eller anden betingelse. Det kunne fx være: Job ansøgere, der skal have et job Lære, der skal tilmeldes et kursus Køretøjer, der skal tildeles en chauffør En matching i en graf G er et subset af kanter M således at ingen kanter i M har nogen naboer (en knude kan ikke have mere end én kant tilknyttet). (a) Matching (b) Ikke matching Figure 9.6: Illustration af matching-begrebet En maksimal matching minimere antallet af knuder, som ikke er at finde som start- eller slutknude til en kant i M En perfekt matching er hvor alle knuder i grafen G er at finde som start- eller slutknude til en kant iM Eksempel - Matching Figure 9.7: Eksempler på matching 32 9.5.1 The stable matching problem The stable matching problem går ud på at opnå en stable matching. Unstable matching er når to noder, som ikke er matched, priorieterer hinanden højere end de noder de er matched med. For at stable matching kan opstå skal følgende krav opfyldes: Vi har en graf, G = (V, E), som består af to ikke overlappende sæt a noder U, W af samme kardinalitet, dvs. at antallet af noder er ens. Desuden gælder følgende: Hvert element i U har en prioritering af alle elementer i W. Hvert element i W har en prioritering af alle elementer i U. 9.5.2 Gale og Sharpley’s algoritme Gale og Sharpley’s algoritme garanterer at alle knuder bliver forbundet. På figur er pseudokoden for algoritmen vist: Figure 9.8: Pseudokode for Gale og Sharpley’s algoritme Algoritmen følger følgende principper: Lad Alice være en kvinde og Bob være en mand, som begge er forlovet, men ikke til hinanden. Når algoritmen er færdig, er det ikke længere muligt for Bob og Alice at foretrække hinanden over deres nuværende partnere. Hvis Bob foretrækker Alice i forhold til sin nuværende partner så har han friet til Alice før sin nuværende partner. Hvis Alice har accepteret hans forslag, men ikke er sammen med ham til sidst, vil dette betyde at hun har droppet ham til fordel for en, hun har foretrukket mere. Hvis Alice har afvist hans forslag, vil det betyde at hun allerede var sammen med en, hun foretrak mere end Bob. 33