rapport/rapport.tex

   1 \documentclass[a4paper, 12pt]{article}
   2 \usepackage[swedish]{babel}
   3 \usepackage[utf8]{inputenc}
   4 \usepackage{verbatim}
   5 \usepackage{fancyhdr}
   6 \usepackage{graphicx}
   7 \usepackage{parskip}
   8 % Include pdf with multiple pages ex \includepdf[pages=-, nup=2x2]{filename.pdf}
   9 \usepackage[final]{pdfpages}
  10 % Place figures where they should be
  11 \usepackage{float}
  12
  13 % vars
  14 \def\title{Sökning}
  15 \def\preTitle{Laboration 2}
  16 \def\kurs{Artificiell Intelligens med inriktning mot kognition och
  17   design B, ht 2008}
  18
  19 \def\namn{Anton Johansson}
  20 \def\mail{dit06ajn@cs.umu.se}
  21 \def\namnett{Victor Zamanian}
  22 \def\mailett{dit06vzy@cs.umu.se}
  23
  24 \def\handledareEtt{Dennis Olsson, denniso@cs.umu.se}
  25 \def\inst{datavetenskap}
  26 \def\dokumentTyp{Laborationsrapport}
  27
  28 \begin{document}
  29 \begin{titlepage}
  30   \thispagestyle{empty}
  31   \begin{small}
  32     \begin{tabular}{@{}p{\textwidth}@{}}
  33       UMEÅ UNIVERSITET \hfill \today \\
  34       Institutionen för \inst \\
  35       \dokumentTyp \\
  36     \end{tabular}
  37   \end{small}
  38   \vspace{10mm}
  39   \begin{center}
  40     \LARGE{\preTitle} \\
  41     \huge{\textbf{\kurs}} \\
  42     \vspace{10mm}
  43     \LARGE{\title} \\
  44     \vspace{15mm}
  45     \begin{large}
  46       \namn, \mail \\
  47       \namnett, \mailett
  48     \end{large}
  49     \vfill
  50     \large{\textbf{Handledare}}\\
  51     \mbox{\large{\handledareEtt}}
  52   \end{center}
  53 \end{titlepage}
  54
  55 \pagestyle{fancy}
  56 \rhead{\footnotesize{\today}}
  57 \lhead{\footnotesize{\namn, \mail \\ \namnett, \mailett}}
  58 \chead{}
  59 \lfoot{}
  60 \cfoot{}
  61 \rfoot{}
  62
  63 \tableofcontents
  64 \newpage
  65
  66 \rfoot{\thepage}
  67 \pagenumbering{arabic}
  68
  69 \section{Problemspecifikation}
  70 Denna rapport redogör för hur en karta och olika sökalgoritmer
  71 implementeras i programmeringsspråket Java. Huvudfokus i rapporten
  72 ligger på analys och jämförelse mellan de olika sökalgoritmerna.
  73
  74 Fyra algoritmer av två olika typer är implementerade. Bredden-först
  75 sökning och Djupet-först sökning är två oinformerade sökningar som
  76 söker efter ett givit mål utan någon problemspecifik
  77 kunskap. Greedy-Search och A* är två informerade sökningar som
  78 använder sig av problemspecifik kunskap för att förbättra sin
  79 sökning. I det här fallet används till exempel kortaste vägen från
  80 varje nod till målet för att avgöra sökvägar i kartan.
  81
  82 Labbspecifikation finns att läsa på:\\
  83 \verb!http://www.cs.umu.se/kurser/5DV063/HT08/lab2.html!
  84
  85 \section{Användarhandledning}
  86 Programmet körs från dit06vzy/edu/ai/lab2 med följande kommando:
  87
  88 \begin{footnotesize}
  89 \verb!java -cp lib/jdom.jar:bin/prod SearchInterface MySearcher \! \\
  90 \verb!<sökväg till karta> <metod> [startnod [slutnod]]!
  91 \end{footnotesize}
  92
  93 Där \verb!<sökväg till karta>! ska hänvisa till en karta sparad i
  94 xml-format enligt följande utseende:
  95
  96 \begin{footnotesize}
  97 \begin{verbatim}
  98 <?xml version='1.0' encoding='ISO-8859-1' ?>
  99 <map>
 100         <node id="Teg" x="1720099" y="7072732">
 101                 <road to="Rondellen" speed="50" />
 102                 <road to="Tegsbron" speed="110" />
 103         </node>
 104    ...
 105 </map>
 106 \end{verbatim}
 107 \end{footnotesize}
 108
 109 Metoden som ska angivas, \verb!<metod>!, är \verb!B! för bredden
 110 först, \verb!D! för djupet först, \verb!Ad! för $A^*$ kortaste vägen och
 111 \verb!At! för $A^*$ snabbaste vägen.
 112
 113 Om varken startnod eller slutnod anges efterfrågas de av
 114 programmet. Om en (1) nod anges som parameter antas den vara startnod
 115 och då efterfrågas bara slutnod av programmet. Annars, om både
 116 startnod och slutnod anges körs vald metod (algoritm) för att hitta
 117 vägen mellan noderna.
 118
 119 \section{Algoritmbeskrivning}
 120
 121 \subsection{setMap(File mapFile)}
 122 Denna metod läser in en karta i form av en XML-fil och representerar
 123 den i en graf. Implementationen av grafen är en modifierad version av
 124 Graph.java som vi använde i kursen Datastrukturer och Algoritmer.
 125
 126 När XML-filen lästs in och tolkats som ett DOM-dokument skaffas alla
 127 noder fram ur detta och sparas i grafen som objekt av typen
 128 \verb!GraphNode!. Dessa objekt innehåller x- och y-koordinater för
 129 noden och ett ''ID'' vilket är namnet på platsen på kartan som noden
 130 representerar. Sedan gås alla noder igenom ännu en gång för att lägga
 131 till vägar och hastighetsbegränsningar mellan dem. Metoden skriver
 132 även ut felmeddelanden om filen 1) inte hittas, 2) inte kan läsas av
 133 någon annan anledning, 3) om det är något fel på innehållet i filen
 134 och vilket felet är, och 4) om någon av koordinaterna för någon nod
 135 inte kan tolkas som ett heltal. Programmet avslutas om något av
 136 ovanstående fel uppstår.
 137
 138 \subsection{Graph.java}
 139 Klassen Graph används för att abstrahera och spara undan alla noder i
 140 kartan. Klassen innehåller en Hashtabell där Kartans namn på noder
 141 sparas som nyckel och själva noden av typ GraphNode sparas som
 142 värde. Metoderna som används mest i denna implementation är de för att
 143 sätta in noder och kanter mellan noderna.
 144
 145 \subsection{GraphNode.java}
 146 Klassen GraphNode används för att spara undan städerna ur
 147 kartan. GraphNode har en Hashtabell som sparar länkar till sina
 148 grannar som nycklar och vikten som värde. Detta innebär att klassen
 149 kan fråga efter en granne och returnera vikten till denna granne.
 150
 151 Dessutom innehåller GraphNode attribut för att spara information om
 152 den är besökt (\textbf{visited}), information om vilken nod den har
 153 besökts ifrån (\textbf{parent}), information om avstånd/tid som det
 154 har kostat för algoritmer att ta sig till aktuell nod
 155 (\textbf{distanceTraveled}) och ett evalueringsvärde
 156 (\textbf{evalFuncVal}) som noderna kan sorteras efter i en
 157 prioritetskö.
 158
 159 \subsection{Oinformerade sökalgoritmer}
 160 Följande sökalgoritmer tar emot två parametrar, \textit{from} och
 161 \textit{to} som anger från vilken nod i grafen algoritmen ska börja
 162 och till vilken nod som ska sökas.
 163
 164 Förutom att algoritmerna använder olika typer av datastrukturer för
 165 att lagra noder så agerar de enligt följande procedur:
 166 \begin{enumerate}
 167 \item Lägg till första noden i en \textit{datastruktur}.
 168 \item Ta ut en nod \textbf{n} ur \textit{datastrukturen}.\label{Otaut}
 169   \begin{enumerate}
 170   \item Markera noden som besökt.
 171   \item Om noden som besöks är målnoden avslutas sökningen och
 172     resultat returneras.
 173   \item Annars läggs alla obesökta grannoder till i
 174     \textit{datastrukturen}, om de inte redan finns representerade i
 175     den, och en länk till noden \textbf{n} sparas i ett attribut
 176     \textbf{parent}.\label{Oparent}
 177   \end{enumerate}
 178 \item Börja om från steg \ref{Otaut}.
 179 \end{enumerate}
 180
 181 För varje besökt nod läggs dess namn till i en sträng. Anledningen
 182 till att man sparar föregående besökt nod i ett attribut
 183 \textbf{parent}, i steg \ref{Oparent}, är att när målet har nåtts blir
 184 det möjligt att stega tillbaka med hjälp av dessa attribut för att
 185 hitta vägen algoritmen valt mellan start och mål.
 186
 187 Har algoritmen hittat målnoden returneras en sträng som innehåller alla
 188 besökta noder och en sträng innehållande den hittade vägen från
 189 startnod till målnod.
 190
 191 Är \textit{datastrukturen} i steg \ref{Otaut} tom, så är alla noder
 192 besökta utan att något mål är hittat. En sträng som förklarar det
 193 inträffade returneras.
 194
 195 \subsubsection{breadthFirst(String from, String to)}
 196 Bredden-först använder datastrukturen stack för att spara noder. Detta
 197 medför att den först besökta nodens alla barn kommer att besökas innan
 198 algoritmen går vidare nästa steg djupare i kartan, därav namnet
 199 Bredden-först.
 200
 201 \subsubsection{depthFirst(String from, String to)}
 202 Djupet-först algoritmen sparar noder i datastrukturen kö. Detta medför
 203 att noderna kommer att plockas ut enligt ''Första in första
 204 ut''-principen, således vandrar algoritmen på djupet i grafen innan
 205 den går på bredden.
 206
 207 \subsection{Informerade sökalgoritmer}
 208 Följande algoritmer använder sig av någon typ av evalueringsfunktion
 209 $f$ som används för bedömning av vilket väg som är bäst att ta.
 210 Evalueringsfunktionen i sin tur beror av någon typ av heuristik,
 211 dvs. någon nivå av kunskap eller information om världen den evaluerar.
 212
 213 \subsubsection{greedySearch(String from, String to)}
 214 Metoden \textit{greedySearch} utför en sökning efter en väg mellan
 215 platserna \verb!from! och \verb!to! efter en ''girig'' algoritm.
 216 Algoritmen börjar på den plats som \verb!from! representerar och
 217 undersöker vilka noder den kan gå till i nästa steg. För dessa
 218 noder undersöker den vilket steg som leder till att den färdas
 219 geografiskt närmare målnoden \verb!to! och väljer detta.
 220
 221 \subsubsection{aStar(String from, String to, boolean fastest)}
 222 Algoritmen $A^*$ (uttalas ''A-sjärna'') fungerar ungefär som
 223 \textit{greedySearch} men den använder ett annat sätt att välja vägen
 224 som den ska ta. Om parametern \verb!fastest! har värdet \verb!true!
 225 söker algoritmen efter den snabbaste vägen (som namnet antyder),
 226 annars söker den efter den kortaste vägen. Funktionen som bestämmer
 227 vilken väg som ska tas i kartan beror på två saker: 1) hur långt den
 228 nod man undersöker ligger från målnoden och 2a) hur långt man färdats
 229 totalt från startnoden eller 2b) hur lång tid det tagit att färdats
 230 från startnoden.
 231
 232 \section{Begränsningar}
 233 % Vilka problem och begränsningar har vår lösning
 234
 235 \section{Reflektioner}
 236 % Vad var krångligt, hur löste vi det. Allmänna synpunkter.
 237 När målet väl hittats i algoritmerna var det inte helt självklart hur
 238 vägen till målet skulle sparas. Vi löste det genom att algoritmen
 239 ''lägger spår'' efter sig när den söker, genom metoden
 240 \verb!GraphNode.setParent(GraphNode node)! som sätter en nods ''förälder'' till
 241 \verb!node!. När målnoden nåtts stegar sedan algoritmerna längs länken
 242 som skapats från startnoden till målnoden och tar fram vägen till
 243 målet på så sätt.
 244
 245 Metoden setMap i klassen MySearcher måste loopa igenom alla noder ur
 246 xml-filen två gånger. Detta beror på att det inte går att lägga till
 247 en väg mellan en nod och en nod som inte ännu existerar i
 248 minnet. Detta skulle kanske kunnat lösas genom att man faktiskt skapar
 249 den nod som inte finns och lägger till information om nodens position
 250 när man kommer till de noderna senare när man kommer till den noden i
 251 DOM-dokumentet. Metoder hade då behövt skrivas för att sätta
 252 koordinaternas värden för en nod. Vi valde att gå igenom noderna två
 253 gånger i stället därför att det kändes lättast då vi skrev metoden.
 254
 255 \section{Diskussion}
 256 % Redogör för sökalgoritmernas för- och nackdelar, samt hur de
 257 % presterade på den givna uppgiften
 258
 259 \subsection{Bredden-först sökning}
 260 Fördelen med Bredden-först sökning var att den är väldigt enkel att
 261 implementera. Den bakomliggande logiken är lätt att förstå och det
 262 behöves ingen specialkunskap om domänen sökningen sker i.
 263
 264 Nackdelen med denna sökning är att om sökningen sker i en stor graf så
 265 kommer algoritmen att besöka väldigt många noder innan den hittar fram
 266 till målet. För varje steg djupare ($d$) algoritmen tar, så ökar
 267 antalet noder som besöks med $d^{b}$, där $b$ = maximala antalet
 268 grannoder, för lite större $d$ kommer detta att bli väldigt många
 269 noder, vilket resulterar i att minnesanvändandet i algoritmen blir
 270 stor.
 271
 272 Bredden-först algoritmen är komplett, det vill säga den hittar alltid
 273 fram till målet om det finns. Detta går att härleda eftersom
 274 Bredden-först algoritmen eventuellt kommer att besöka varenda nod som
 275 existerar i grafen.
 276
 277 I en graf där alla vägar väger lika mycket, kommer Bredden-först att
 278 hitta den optimala lösningen (snabbaste/kortaste vägen till mål),
 279 eftersom algoritmen har gått vägen med minst antal steg. För generella
 280 grafer där vägarna kan ha olika viktkostnader kommer dock
 281 Bredden-först inte att vara optimal. Detta är fallet i grafen som
 282 används i denna laboration.
 283
 284 \subsection{Djupet-först sökning}
 285 Djupet-först sökning är precis som Bredden-först sökning enkel att
 286 implementera, ingen kunskap om målet behövs förutom en koll för att se
 287 när målet är nått.
 288
 289 Liksom Bredden-först sökning så kommer Djupet-först att besöka alla
 290 noder i grafen tills den har hittat målnoden, algoritmen är således
 291 komplett. Utrymmet som krävs kommer att vara beroende av den djupaste
 292 vägen till målet, eller mer exakt $b^{d}$, där $b$ är bredden eller
 293 antalet grannoder och $d$ är djupet.
 294
 295 I testkörningarna, se \ref{tests} på sida \pageref{tests}, syns att
 296 jämfört med Bredden-först kommer Djupet-först sökning att hitta målet
 297 utan att expandera lika många noder. Vägen till målet är dock ofta en
 298 lång omväg eftersom algoritmen, i grafer, ofta kommer att hitta målet
 299 på första djupsökning. Algoritmen är således inte optimal.
 300
 301 Eftersom Djupet-först i denna implementation avnänder sig av ett
 302 attribut, \textbf{visited}, så kommer inte samma nod att besökas två
 303 gånger. Detta gör att algoritmen undviker att hamna i cykler där den
 304 snurrar runt mellan samma noder.
 305
 306 \subsection{A* sökning}
 307
 308 \subsection{Girig sökning}
 309
 310 \section{Testkörningar}
 311 \subsection{Test Bredden-först}
 312 \subsubsection{From: Tegsbron to Nydala}
 313
 314 \textbf{All expanded nodes:}
 315 Tegsbron, I20, Teg, Station, Obs, Rondellen, Gamlia, Foa, Begbilar, TreKorvar, Kyrkan, NUS, Berghem, Mariehem, Flygplatsen, On, Sofiehem, MIT, Nydala
 316
 317
 318 \textbf{Path to goal:}
 319 Tegsbron, I20, Obs, Foa, Mariehem, Nydala
 320
 321 \subsubsection{From: Flygplatsen to Begbilar}
 322
 323 \textbf{All expanded nodes:}
 324 Flygplatsen, TreKorvar, Rondellen, On, Teg, Kyrkan, Tegsbron, NUS, Station, I20, Gamlia, Sofiehem, Obs, Berghem, GimonAs, Alidhem, Foa, Begbilar
 325
 326
 327 \textbf{Path to goal:}
 328 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 329
 330 \subsubsection{From: MIT to Flygplatsen}
 331
 332 \textbf{All expanded nodes:}
 333 MIT, Nydala, Berghem, Alidhem, Mariehem, Ok, Gamlia, Sofiehem, Foa, Station, NUS, GimonAs, Begbilar, Obs, I20, Kyrkan, Tegsbron, Rondellen, Teg, TreKorvar, Flygplatsen
 334
 335
 336 \textbf{Path to goal:}
 337 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 338
 339 \subsubsection{From: Nydala to Gamlia}
 340
 341 \textbf{All expanded nodes:}
 342 Nydala, Ok, Mariehem, MIT, Alidhem, Foa, Berghem, Sofiehem, Obs, Begbilar, Gamlia
 343
 344
 345 \textbf{Path to goal:}
 346 Nydala, Mariehem, Berghem, Gamlia
 347
 348 \subsubsection{From: Teg to Foa}
 349
 350 \textbf{All expanded nodes:}
 351 Teg, Rondellen, Tegsbron, Kyrkan, TreKorvar, I20, Station, NUS, Flygplatsen, On, Obs, Gamlia, Sofiehem, Foa
 352
 353
 354 \textbf{Path to goal:}
 355 Teg, Tegsbron, I20, Obs, Foa
 356
 357 \subsection{Test Djupet-först}
 358 \subsubsection{From: Tegsbron to Nydala}
 359
 360 \textbf{All expanded nodes:}
 361 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Sofiehem, Alidhem, Ok, Nydala
 362
 363
 364 \textbf{Path to goal:}
 365 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Sofiehem, Alidhem, Ok, Nydala
 366
 367 \subsubsection{From: Flygplatsen to Begbilar}
 368
 369 \textbf{All expanded nodes:}
 370 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar
 371
 372
 373 \textbf{Path to goal:}
 374 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar
 375
 376 \subsubsection{From: MIT to Flygplatsen}
 377
 378 \textbf{All expanded nodes:}
 379 MIT, Alidhem, Ok, Sofiehem, GimonAs, NUS, Gamlia, Station, Obs, Begbilar, Foa, Mariehem, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen
 380
 381
 382 \textbf{Path to goal:}
 383 MIT, Alidhem, Sofiehem, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen
 384
 385 \subsubsection{From: Nydala to Gamlia}
 386
 387 \textbf{All expanded nodes:}
 388 Nydala, MIT, Alidhem, Sofiehem, NUS, Kyrkan, Station, Obs, Begbilar, Foa, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen, On, Gamlia
 389
 390
 391 \textbf{Path to goal:}
 392 Nydala, MIT, Alidhem, Sofiehem, NUS, Gamlia
 393
 394 \subsubsection{From: Teg to Foa}
 395
 396 \textbf{All expanded nodes:}
 397 Teg, Tegsbron, I20, Obs, Foa
 398
 399
 400 \textbf{Path to goal:}
 401 Teg, Tegsbron, I20, Obs, Foa
 402
 403 \subsection{Test A* snabbast}
 404 \subsubsection{From: Tegsbron to Nydala}
 405
 406 \textbf{All expanded nodes:}
 407 Tegsbron, Teg, I20, Rondellen, Station, Kyrkan, NUS, TreKorvar, Gamlia, Gamlia, Sofiehem, Flygplatsen, Berghem, Berghem, Alidhem, On, GimonAs, MIT, MIT, MIT, Obs, Ok, Obs, Ok, Mariehem, Mariehem, Nydala
 408
 409
 410 \textbf{Path to goal:}
 411 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Gamlia, Berghem, Mariehem, Nydala
 412
 413 \subsubsection{From: Flygplatsen to Begbilar}
 414
 415 \textbf{All expanded nodes:}
 416 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, NUS, Gamlia, Teg, Tegsbron, Berghem, I20, I20, Mariehem, Obs, Obs, Gamlia, Sofiehem, Obs, Alidhem, MIT, Foa, Foa, Foa, Foa, MIT, Begbilar
 417
 418
 419 \textbf{Path to goal:}
 420 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Foa, Begbilar
 421
 422 \subsubsection{From: MIT to Flygplatsen}
 423
 424 \textbf{All expanded nodes:}
 425 MIT, Alidhem, Sofiehem, Berghem, Gamlia, Nydala, NUS, NUS, GimonAs, Ok, Kyrkan, Kyrkan, Mariehem, Mariehem, Rondellen, Rondellen, Ok, Ok, Station, Station, Station, TreKorvar, TreKorvar, Teg, Teg, Flygplatsen
 426
 427
 428 \textbf{Path to goal:}
 429 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 430
 431 \subsubsection{From: Nydala to Gamlia}
 432
 433 \textbf{All expanded nodes:}
 434 Nydala, Ok, MIT, Alidhem, Mariehem, Alidhem, Berghem, Berghem, Gamlia
 435
 436
 437 \textbf{Path to goal:}
 438 Nydala, Mariehem, Berghem, Gamlia
 439
 440 \subsubsection{From: Teg to Foa}
 441
 442 \textbf{All expanded nodes:}
 443 Teg, Tegsbron, Rondellen, Kyrkan, I20, Station, Obs, Station, NUS, TreKorvar, Gamlia, Gamlia, Berghem, Berghem, Sofiehem, Flygplatsen, Mariehem, Mariehem, Alidhem, On, Obs, Foa
 444
 445
 446 \textbf{Path to goal:}
 447 Teg, Tegsbron, I20, Station, Obs, Foa
 448
 449 \subsection{Test A* kortast}
 450 \subsubsection{From: Tegsbron to Nydala}
 451
 452 \textbf{All expanded nodes:}
 453 Tegsbron, I20, Station, Gamlia, Berghem, NUS, MIT, Nydala
 454
 455
 456 \textbf{Path to goal:}
 457 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 458
 459 \subsubsection{From: Flygplatsen to Begbilar}
 460
 461 \textbf{All expanded nodes:}
 462 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, NUS, Gamlia, Gamlia, Berghem, Berghem, Obs, Begbilar
 463
 464
 465 \textbf{Path to goal:}
 466 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 467
 468 \subsubsection{From: MIT to Flygplatsen}
 469
 470 \textbf{All expanded nodes:}
 471 MIT, Alidhem, Sofiehem, Berghem, Gamlia, NUS, NUS, GimonAs, Nydala, Station, Ok, Kyrkan, Ok, Rondellen, Ok, TreKorvar, Flygplatsen
 472
 473
 474 \textbf{Path to goal:}
 475 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 476
 477 \subsubsection{From: Nydala to Gamlia}
 478
 479 \textbf{All expanded nodes:}
 480 Nydala, MIT, Berghem, Gamlia
 481
 482
 483 \textbf{Path to goal:}
 484 Nydala, MIT, Berghem, Gamlia
 485
 486 \subsubsection{From: Teg to Foa}
 487
 488 \textbf{All expanded nodes:}
 489 Teg, Rondellen, Kyrkan, Station, Tegsbron, NUS, I20, I20, Gamlia, Gamlia, Berghem, Berghem, TreKorvar, Mariehem, Mariehem, Foa
 490
 491
 492 \textbf{Path to goal:}
 493 Teg, Rondellen, Kyrkan, NUS, Gamlia, Berghem, Mariehem, Foa
 494
 495 \subsection{Test Girig sökning}
 496 \subsubsection{From: Tegsbron to Nydala}
 497
 498 \textbf{All expanded nodes:}
 499 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 500
 501
 502 \textbf{Path to goal:}
 503 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 504
 505 \subsubsection{From: Flygplatsen to Begbilar}
 506
 507 \textbf{All expanded nodes:}
 508 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, Obs, Begbilar
 509
 510
 511 \textbf{Path to goal:}
 512 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 513
 514 \subsubsection{From: MIT to Flygplatsen}
 515
 516 \textbf{All expanded nodes:}
 517 MIT, Alidhem, Sofiehem, GimonAs, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 518
 519
 520 \textbf{Path to goal:}
 521 MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 522
 523 \subsubsection{From: Nydala to Gamlia}
 524
 525 \textbf{All expanded nodes:}
 526 Nydala, MIT, Berghem, Gamlia
 527
 528
 529 \textbf{Path to goal:}
 530 Nydala, MIT, Berghem, Gamlia
 531
 532 \subsubsection{From: Teg to Foa}
 533
 534 \textbf{All expanded nodes:}
 535 Teg, Tegsbron, I20, Obs, Foa
 536
 537
 538 \textbf{Path to goal:}
 539 Teg, Tegsbron, I20, Obs, Foa
 540
 541 \newpage
 542 \appendix
 543 \section{Källkod}
 544 \pagenumbering{roman}
 545
 546 \subsection{MySearcher.java}
 547 \begin{footnotesize}
 548   \verbatiminput{../src/MySearcher.java}
 549 \end{footnotesize}
 550
 551 \subsection{Graph.java}
 552 \begin{footnotesize}
 553   \verbatiminput{../src/Graph.java}
 554 \end{footnotesize}
 555
 556 \subsection{GraphNode.java}
 557 \begin{footnotesize}
 558   \verbatiminput{../src/GraphNode.java}
 559 \end{footnotesize}
 560
 561 \subsection{GraphTest.java}
 562 \begin{footnotesize}
 563   \verbatiminput{../test/GraphTest.java}
 564 \end{footnotesize}
 565
 566 \subsection{MySearcherTest.java}
 567 \begin{footnotesize}
 568   \verbatiminput{../test/MySearcherTest.java}
 569 \end{footnotesize}
 570 \end{document}