Nå som eksamen er over og jeg har mer tid og krefter tenkte jeg at jeg skulle bruke litt av tiden til å prøve å få skrevet noen guider på dette forumet og starte tråder hvor man kan skape debatt rundt programmering. Målet mitt blir å i løpet av sommeren heve nivået på dette forumet; da jeg personlig synes det er noe lavt til å være en IT-forum.

Om man ser i "README" tråden så står det følgende: Og jeg tror de fleste er enige med meg når jeg sier at i det siste blir ikke disse så veldig fulgt; er alt for mye nybegynnerspørsmål her på huset. Men nok ranting, håper at trådene mine er med å bidrar til et mer aktivt under-forum og gode debatter - og om noen lærer noe er det enda bedre.

1.0 Kort introduksjon
I denne tråden vil jeg ta for meg hvordan man kan fremstille grafer ved bruk av programmering og koding, og hvordan man kan søke gjennom disse for å få ut eventuell informasjon. Jeg vil og vise hvordan man kan bruke denne teorien til å f.eks. løse et praktisk eksempel som å finne korteste vei gjennom en labyrint. Det meste som tråden omhandler vil ikke være noe spesifikt for programmeringsspråk; men i eksemplene jeg viser vil jeg bruke Python siden det er det språket jeg mener er både lettest å skrive; men også det som er lettest å lese når man skal forstå algoritmer; selv for en uten for mye innblikk i python.

2.0 Grafer: Noder, kanter og stier
Før vi går ordentlig i gang kan det være greit å definere hva en graf faktisk er. Og når vi snakker om grafer i programmering tenker vi på en tegning som består av et sett elementer/noder (tegnet som sirkler) som er knyttet sammen på en bestemt måte. De ulike nodene kan beskrive mye forskjellig som for eksempel steder, ting eller situasjoner, mens hvordan de er knyttet sammen viser hvilke ting som hører sammen.

Det er viktig å skille mellom en rettetede og urettetede grafer; rettetede grafer er grafer hvor man kan alltid kan gå begge veier over en kant som kobler sammen 2 noder, mens i en urettet graf kan man kun gå over en kant den veien pilen viser. Om du ser på Bilde 1 under så kan man lett se forskjellen. F.eks. på grafen til venstre der kan man ikke gå fra Node 2 til Node 3, da kanten kun peker fra 3 til 2, og det finnes ingen andre veien man kan ta for å komme fra 2 til 3.

Man har også noe som heter vektede grafer, jeg vil ikke ta for meg det til å begynne med - men planen var å ta for meg dette i en guide jeg skriver senere som tar for seg litt mer avanserte algoritmer. Men i korte trekk er en vektet graf en graf hvor de ulike kantene har blitt gitt verdier som er kostnaden for å reise over en bestemt kant mellom 2 noder.

http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/6n-graf.svg/200px-6n-graf.svg.pnghttp://pages.cpsc.ucalgary.ca/~jacobs/Courses/cpsc331/F08/tutorials/Figures/directed_graph_example1.gif
Bilde 1: En urettet graf til venstre, og en rettet graf til høyre.

Et praktisk eksempel for hva man kan bruke grafteori til: La oss si du skal lage en kart-tjeneste over norge og ønsker en funksjon hvor folk kan skrive inn en ønsker reise og du skal da finne en vei mellom de 2 adressene personen skrev inn. I et slikt tilfelle kan man lage en graf som representerer veinettet i Norge. Man lar nodene representere de ulike veikryssene og kantene mellom nodene er de mulige veiene man kan ta mellom ulike veikryssene. Man kan da ta i bruk mange ulike graf-algoritmer for å søke seg frem til den informasjonen man ønsker som f.eks. korteste vei mellom punktene.

2.1 Hvordan representere en graf
Det neste blir å finne en måte man kan representere grafen på slik at man enkelt kan bruke den i de ulike algoritmene man vil bruke. Til dette har man noe som heter nabo-matrise og nabo-liste som er de mest brukte. Jeg vil gi en kort introduksjon til begge to.

2.1.1 Nabo-matrise
En nabo-matrise er en enkel måte å beskrive hvordan en graf ser ut ved å bruke en tabell/matrise hvor hver rad/kolonne representerer en Node. Verdien i de ulike rutene beskriver kanten mellom nodene; om verdien er 0 finnes det ikke en kant mellom de 2 nodene. For en uvektet graf er verdien 1 for alle plasser hvor det er en kant mellom nodene; i vektede grafer vil verdien representere vekten til den bestemte kanten.
http://bildr.no/image/865096.jpeg
Bilde 2: En nabo-matrise som beskriver den urettede grafen fra bilde 1.

Hvis vi f.eks. lurer på om det finnes en kant fra Node 4 til Node 2 går vi først ned på rad 4 i matrisen, og følger raden til den andre kolonnen. Vi ser at verdien i denne ruten er 0, og ut i fra dette vet vi at det ikke finnes en kant fra Node 4 til Node 2. Siden vi vet at grafen er urettet kan vi også konkludere med at det betyr at det ikke finnes en kant fra 2 til 4.

En slik matrise som du ser ovenfor i bilde 2 er veldig enkel å beskrive i kode ved å bare bruke en 2-dimensjonalt array. Under ser du et eksempel på hvordan dette kan gjøres i python-kode.
Fordelene med å bruke en nabo-matrise er at det går veldig fort å søke opp om det er en kant mellom 2 bestemte noder (konstant enkelt oppslag). Bakdelene er at den tar opp ganske mye minne (kvadratet av antall noder). Det tar og litt tid å finne alle kanter som går ut i fra en bestemt node. (O(Antall noder))

2.1.2 Nabo-liste
Den andre måten vi vil bli kjent med er nabo-liste. Denne går enkelt og greit ut på at man i stede for å bruke et 2 dimensjonelt array i stede lager en liste for hver node i grafen. I denne listen legger man inn hvilke noder det finnes en kant til fra denne noden. I python kan man gjøre det som i eksemepelet under.
Nabomatrisen i de fleste tilfeller bedre da den tar mindre minne og er mer effektiv tidsmessig på operasjoner som å finne alle kanter fra en node. Men den er ikke like effektiv på å sjekke opp om det er en kant mellom 2 noder.

3.0 Søke gjennom grafer
Vi skal nå se på hvordan man kan søke gjennom grader ved bruk av dybde-først og bredde-først søk. Vi vil se litt kort på forskjellene mellom de og hva de kan brukes til. Vi vil bruke grafen du ser under i bilde 3 i våre eksempler.
http://bildr.no/image/867000.jpeg
Bilde 3: En rettede grafen vi vil bruke i eksemplene under

3.1 Dybde først søk.
"Depth-first search (DFS) is an algorithm for traversing or searching a tree, tree structure, or graph. One starts at the root (selecting some node as the root in the graph case) and explores as far as possible along each branch before backtracking."-wikipedia

Dette betyr at om man skal gjøre et manuelt søk ved bruk av DFS for å prøve å finne en sti fra node 3 til node 5 i grafen fra bilde 3 ville vi startet med å sette node 3 som start-punkt. Vi ville så se etter den første naboen til denne naboen, som i dette tilfellet er node 2. Vi villde da se etter de nærmeste naboene til 2 som er 0, og fra 0 til 1. Når vi kom til 1 står vi i et punkt hvor vi ikke lenger kan reise til noder vi ikke har besøk før. (Eneste mulige vei er til 2, men der har vi vært før). Den vil da gjøre det som heter backtracking, hvor den hopper tilbake den veien den kom. I dette tilfellet tilbake til 0. Den vil så prøve å finne en annen vei fra 0, og vil i vårt tilfelle finne en vei til node 4. og til slutt finne en kant fra 4 til 5: som er målet vårt.

Kort fortalt blir søket slik:
3 -> 2
2 -> 0
0 -> 1
0 -> 4
4 -> 5

Og stien fra 3 til 5 som vi ender opp med er: 3 -> 2 -> 0 -> 4 -> 5

3.1.1 Rekursivt dybde-først søk
Den første algoritmen jeg vil introdusere er en rekursiv implementasjon av dybde først søk. Denne fungerer slik at funsksjonen blir først kallt med en start- og mål-node sammen med en graf. Denne funksjonen vil så kalle seg selv rekursivt for alle naboene til start-noden. (hvor naboen blir satt som start-node i stede). Funksjonen vil så returnere stien den tok om den når den fant ende-noden.
Outputen fra denne funksjonen blir som følger:
Hvor vi kan se at den tok samme sti som vi fant ved å manuelt gjøre et dybde-først søk.

3.1.1 Dybde-først søk med Stack
Den neste implementasjonen vi vil se på er en litt mer generall løsning, da den lett kan omskrives til å fungere som et bredde først søk. Fungerer ved at den har en "fringe" som inneholder elementene vi ønsker å sjekke. Denne skal fungere som en stack, altså FIFU, (Først inn, først ut). Det hele vil fungere slik at vi vil kjøre funksjonen så lenge det er elementer i stacken. Poppe et element av stacken, sjekke om det er endenoden - og returnere stien den tok dit om det er det; hvis ikke legger den alle naboene sine inn på stacken slik at disse blir søkt gjennom.
3.2 Bredde først søk
Bredde først søk er på mange måter ganske lik dybde-først søk, spesielt den som bruker fringen. Den eneste praktiske forskjellen i koden er at den i stede for å plukke det siste elementet fra fingen og fungere som en stack vil den plukke ut det første elementet - og på den måten bruke den som en kø. (FISU = Først inn, sist ut). Dette betyr at om du f.eks. velger å starte på nummber 3 og skal søke med dybde først søk etter node 4 vil den starte med å legge 3 inn i fringen.
Fringe: [3]

Den vil så ta ut første element fra fringen, som her er node 3. Den vil se at dette ikke er målet vårt og vil derfor legge inn naboene som er 2 og 5 på fringen.
Fringe: [2, 5]

Den vil så fortsette med å igjen ta ut første element fra fringen, som nå er 2, dette er heller ikke målet vårt så naboene til 2 blir lagt til på slutten av fringen. (0 og 1).
Fringe: [5, 0, 1].

Den vil igjen ta ut første element fra fringen, som nå er 5, dette er ikke målet vårt så naboene til 5 blir lagt på fringen.
Fringe: [0, 1, 4]

Dette vil den fortsette å gjøre for både 0 og 1, før den kommer til 4. Hvor den returnerer stien den tok som var 3 -> 5 -> 4.

Kort fortalt så viser dette at den søker nodene som er nærmest start-noden først og jobber seg gradvis utover. En fin sideeffekt av dette er at vi alltid vil finne den korteste stien ved å bruke denne implementasjonen.

For å implementere dette trenger vi derfor ikke gjøre store endringer på dybde-først klassen som ble laget i det forrige eksempelet og vi kan derfor bare arve fra den. Ved å gjøre endring på _getNext metoden slik at den velger første element fra fringen i stede for det siste så har vi i praksis implementert bredde først søk.

Du er sikker på at du ikke har blandet stack og kø nå? Det er da kø som er FIFO? Hvis du queuer 1, 2, a, b, potet i en bolk i en kø, og så dequeuer dem, vil du ha fått 1, 2, a, b, potet - det første er 1 i begge tilfellene, ergo: FIFO.
Pusher du dem til en stack og popper etterpå, vil du ha fått potet ut igjen først..

Edit: forresten et fantastisk tiltak, stor fan av det.

Ok, nytt spørsmål.
Edit: Fant svaret selv, og det var et så dårlig spørsmål at jeg like gjerne sletter det for ingen andre kan ha nytte av det. Jeg leste rett og slett ikke godt nok.

om du editer posten for å slette spørsmålet kan du egentlig like gjerne slette posten Et tips til neste gang, for ingen har nytterverdi av den posten nå som du fjernet meningen med den.

Det går ikke an å slette poster på freak (jeg sletter denne hvis det går an).

Edit: Nope, kan ikke slette.