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 var och en av
 218 dessa noder undersöker den vilket steg som leder till att den färdas
 219 geografiskt närmare målnoden (fågelvägen) \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
 241 ''förälder'' till \verb!node!. När målnoden nåtts stegar sedan
 242 algoritmerna längs länken som skapats från startnoden till målnoden
 243 och tar fram vägen till målet på så sätt.
 244
 245 Angående att vi måste loopa igenom alla noder två gånger: Detta beror
 246 på att det inte går att lägga till en väg mellan en nod och en nod som
 247 inte ännu existerar i minnet. Detta skulle kanske kunnat lösas genom
 248 att man faktiskt skapar den nod som inte finns och lägger till
 249 information om nodens position när man kommer till de noderna senare
 250 när man kommer till den noden i DOM-dokumentet. Metoder hade då behövt
 251 skrivas för att sätta koordinaternas värden för en nod. Vi valde att
 252 gå igenom noderna två gånger i stället därför att det kändes lättast
 253 då vi skrev metoden.
 254
 255 Vi hade lite problem med att inse att vi behövde ha en separat
 256 evaluerings\-funktion i A*-algoritmen och ett attribut i klassen
 257 \verb!GraphNode! för att hålla reda på varje nods
 258 evaluerings\-funktions\-värde. Innan vi insåg detta använde vi
 259 attributet i \verb!GraphNode! som egentligen ska hålla reda på
 260 stigkostnad. Vi insåg att det var något fel med vår algoritm då vi
 261 jämförde våra algoritmers lösningar (valda sökvägar) med andra grupper
 262 i klassen.
 263
 264 Metoden setMap i klassen MySearcher måste loopa igenom alla noder ur
 265 xml-filen två gånger. Detta beror på att det inte går att lägga till
 266 en väg mellan en nod och en nod som inte ännu existerar i
 267 minnet. Detta skulle kanske kunnat lösas genom att man faktiskt skapar
 268 den nod som inte finns och lägger till information om nodens position
 269 när man kommer till de noderna senare när man kommer till den noden i
 270 DOM-dokumentet. Metoder hade då behövt skrivas för att sätta
 271 koordinaternas värden för en nod. Vi valde att gå igenom noderna två
 272 gånger i stället därför att det kändes lättast då vi skrev metoden.
 273
 274 Det hade varit bra med klargörande i labbspecifikationen vi fick ut
 275 att kartan kunde ha enkelriktade vägar. Det enda sättet detta gick att
 276 notera var om man gick igenom xml-filen noggrannt och kollade upp
 277 varje väg som fanns. Mycket onödigt felsökande och i vårt fall
 278 omimplementation av hela vår graf hade kunnat undvikas.
 279
 280 \section{Diskussion}
 281 % Redogör för sökalgoritmernas för- och nackdelar, samt hur de
 282 % presterade på den givna uppgiften
 283
 284 \subsection{Bredden-först sökning}
 285 Fördelen med Bredden-först sökning var att den är väldigt enkel att
 286 implementera. Den bakomliggande logiken är lätt att förstå och det
 287 behöves ingen specialkunskap om domänen sökningen sker i.
 288
 289 Nackdelen med denna sökning är att om sökningen sker i en stor graf så
 290 kommer algoritmen att besöka väldigt många noder innan den hittar fram
 291 till målet. För varje steg djupare ($d$) algoritmen tar, så ökar
 292 antalet noder som besöks med $d^{b}$, där $b$ = maximala antalet
 293 grannoder, för lite större $d$ kommer detta att bli väldigt många
 294 noder, vilket resulterar i att minnesanvändandet i algoritmen blir
 295 stor.
 296
 297 Bredden-först algoritmen är komplett, det vill säga den hittar alltid
 298 fram till målet om det finns. Detta går att härleda eftersom
 299 Bredden-först algoritmen eventuellt kommer att besöka varenda nod som
 300 existerar i grafen.
 301
 302 I en graf där alla vägar väger lika mycket, kommer Bredden-först att
 303 hitta den optimala lösningen (snabbaste/kortaste vägen till mål),
 304 eftersom algoritmen har gått vägen med minst antal steg. För generella
 305 grafer där vägarna kan ha olika viktkostnader kommer dock
 306 Bredden-först inte att vara optimal. Detta är fallet i grafen som
 307 används i denna laboration.
 308
 309 \subsection{Djupet-först sökning}
 310 Djupet-först sökning är precis som Bredden-först sökning enkel att
 311 implementera, ingen kunskap om målet behövs förutom en koll för att se
 312 när målet är nått.
 313
 314 Liksom Bredden-först sökning så kommer Djupet-först att besöka alla
 315 noder i grafen tills den har hittat målnoden, algoritmen är således
 316 komplett. Utrymmet som krävs kommer att vara beroende av den djupaste
 317 vägen till målet, eller mer exakt $b^{d}$, där $b$ är bredden eller
 318 antalet grannoder och $d$ är djupet.
 319
 320 I testkörningarna, se \ref{tests} på sida \pageref{tests}, syns att
 321 jämfört med Bredden-först kommer Djupet-först sökning att hitta målet
 322 utan att expandera lika många noder. Vägen till målet är dock ofta en
 323 lång omväg eftersom algoritmen, i grafer, ofta kommer att hitta målet
 324 på första djupsökning. Algoritmen är således inte optimal.
 325
 326 Eftersom Djupet-först i denna implementation avnänder sig av ett
 327 attribut, \textbf{visited}, så kommer inte samma nod att besökas två
 328 gånger. Detta gör att algoritmen undviker att hamna i cykler där den
 329 snurrar runt mellan samma noder.
 330
 331 \subsection{Girig sökning}
 332 Fördelen med en girig sökning är att den har någon typ av
 333 evalueringsfunktion $f(n)$ ($f(n) = h(n)$) som gör att den inte
 334 accepterar vilken lösning på ett problem (sökning i karta till
 335 exempel) som helst, utan väljer, om något naivt, en i genomsnitt
 336 bättre lösning än en oinformerad sökning. Nackdelen med en girig
 337 sökning är att den inte tar hänsyn till totala kostnaden för en
 338 lösning jämfört med en annan lösning, utan nöjer sig med första bästa
 339 lösning (Best-first search).
 340
 341 En annan nackdel med girig sökning är att man skulle kunna hamna i ett
 342 läge där man hoppar mellan två noder i kartan i all oändlighet, givet
 343 att algoritmen inte håller reda på vilka punkter den redan besökt
 344 (vilket vår implementation gör).
 345
 346 \subsection{A* sökning}
 347 En uppenbar fördel med A*-algoritmen är faktumet att den är optimal,
 348 dvs. den hittar den absolut bästa vägen. Den använder sig, som den
 349 giriga sök\-algoritmen, av en evaluerings\-funktion $f(n)$. Men $f(n)$
 350 för A* är mer informerad än den giriga då A* är optimal och den giriga
 351 inte är det. Den ytterligare informationen ligger i att A* håller reda
 352 på hur långt den har gått totalt, alltså stigkostnaden. En nackdel kan
 353 däremot vara att A* måste expandera fler noder för att kunna avgöra
 354 vilken väg som är faktiskt är bäst, och att den då kan kräva lite mer
 355 minne. Något som också tar lite extra minne är att vi sparar värdet
 356 för evaluerings\-funktionen i varje nod. Att den måste expandera fler
 357 noder kan möjligtvis också ta längre tid än mindre informerade (och
 358 icke\-optimala) algoritmer.
 359
 360 \section{Testkörningar}
 361 \subsection{Test Bredden-först}
 362 \subsubsection{From: Tegsbron to Nydala}
 363
 364 \textbf{All expanded nodes:}
 365 Tegsbron, I20, Teg, Station, Obs, Rondellen, Gamlia, Foa, Begbilar, TreKorvar, Kyrkan, NUS, Berghem, Mariehem, Flygplatsen, On, Sofiehem, MIT, Nydala
 366
 367
 368 \textbf{Path to goal:}
 369 Tegsbron, I20, Obs, Foa, Mariehem, Nydala
 370
 371 \subsubsection{From: Flygplatsen to Begbilar}
 372
 373 \textbf{All expanded nodes:}
 374 Flygplatsen, TreKorvar, Rondellen, On, Teg, Kyrkan, Tegsbron, NUS, Station, I20, Gamlia, Sofiehem, Obs, Berghem, GimonAs, Alidhem, Foa, Begbilar
 375
 376
 377 \textbf{Path to goal:}
 378 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 379
 380 \subsubsection{From: MIT to Flygplatsen}
 381
 382 \textbf{All expanded nodes:}
 383 MIT, Nydala, Berghem, Alidhem, Mariehem, Ok, Gamlia, Sofiehem, Foa, Station, NUS, GimonAs, Begbilar, Obs, I20, Kyrkan, Tegsbron, Rondellen, Teg, TreKorvar, Flygplatsen
 384
 385
 386 \textbf{Path to goal:}
 387 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 388
 389 \subsubsection{From: Nydala to Gamlia}
 390
 391 \textbf{All expanded nodes:}
 392 Nydala, Ok, Mariehem, MIT, Alidhem, Foa, Berghem, Sofiehem, Obs, Begbilar, Gamlia
 393
 394
 395 \textbf{Path to goal:}
 396 Nydala, Mariehem, Berghem, Gamlia
 397
 398 \subsubsection{From: Teg to Foa}
 399
 400 \textbf{All expanded nodes:}
 401 Teg, Rondellen, Tegsbron, Kyrkan, TreKorvar, I20, Station, NUS, Flygplatsen, On, Obs, Gamlia, Sofiehem, Foa
 402
 403
 404 \textbf{Path to goal:}
 405 Teg, Tegsbron, I20, Obs, Foa
 406
 407 \subsection{Test Djupet-först}
 408 \subsubsection{From: Tegsbron to Nydala}
 409
 410 \textbf{All expanded nodes:}
 411 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Sofiehem, Alidhem, Ok, Nydala
 412
 413
 414 \textbf{Path to goal:}
 415 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Sofiehem, Alidhem, Ok, Nydala
 416
 417 \subsubsection{From: Flygplatsen to Begbilar}
 418
 419 \textbf{All expanded nodes:}
 420 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar
 421
 422
 423 \textbf{Path to goal:}
 424 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar
 425
 426 \subsubsection{From: MIT to Flygplatsen}
 427
 428 \textbf{All expanded nodes:}
 429 MIT, Alidhem, Ok, Sofiehem, GimonAs, NUS, Gamlia, Station, Obs, Begbilar, Foa, Mariehem, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen
 430
 431
 432 \textbf{Path to goal:}
 433 MIT, Alidhem, Sofiehem, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen
 434
 435 \subsubsection{From: Nydala to Gamlia}
 436
 437 \textbf{All expanded nodes:}
 438 Nydala, MIT, Alidhem, Sofiehem, NUS, Kyrkan, Station, Obs, Begbilar, Foa, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen, On, Gamlia
 439
 440
 441 \textbf{Path to goal:}
 442 Nydala, MIT, Alidhem, Sofiehem, NUS, Gamlia
 443
 444 \subsubsection{From: Teg to Foa}
 445
 446 \textbf{All expanded nodes:}
 447 Teg, Tegsbron, I20, Obs, Foa
 448
 449
 450 \textbf{Path to goal:}
 451 Teg, Tegsbron, I20, Obs, Foa
 452
 453 \subsection{Test A* snabbast}
 454 \subsubsection{From: Tegsbron to Nydala}
 455
 456 \textbf{All expanded nodes:}
 457 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
 458
 459
 460 \textbf{Path to goal:}
 461 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Gamlia, Berghem, Mariehem, Nydala
 462
 463 \subsubsection{From: Flygplatsen to Begbilar}
 464
 465 \textbf{All expanded nodes:}
 466 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
 467
 468
 469 \textbf{Path to goal:}
 470 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Foa, Begbilar
 471
 472 \subsubsection{From: MIT to Flygplatsen}
 473
 474 \textbf{All expanded nodes:}
 475 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
 476
 477
 478 \textbf{Path to goal:}
 479 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 480
 481 \subsubsection{From: Nydala to Gamlia}
 482
 483 \textbf{All expanded nodes:}
 484 Nydala, Ok, MIT, Alidhem, Mariehem, Alidhem, Berghem, Berghem, Gamlia
 485
 486
 487 \textbf{Path to goal:}
 488 Nydala, Mariehem, Berghem, Gamlia
 489
 490 \subsubsection{From: Teg to Foa}
 491
 492 \textbf{All expanded nodes:}
 493 Teg, Tegsbron, Rondellen, Kyrkan, I20, Station, Obs, Station, NUS, TreKorvar, Gamlia, Gamlia, Berghem, Berghem, Sofiehem, Flygplatsen, Mariehem, Mariehem, Alidhem, On, Obs, Foa
 494
 495
 496 \textbf{Path to goal:}
 497 Teg, Tegsbron, I20, Station, Obs, Foa
 498
 499 \subsection{Test A* kortast}
 500 \subsubsection{From: Tegsbron to Nydala}
 501
 502 \textbf{All expanded nodes:}
 503 Tegsbron, I20, Station, Gamlia, Berghem, NUS, MIT, Nydala
 504
 505
 506 \textbf{Path to goal:}
 507 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 508
 509 \subsubsection{From: Flygplatsen to Begbilar}
 510
 511 \textbf{All expanded nodes:}
 512 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, NUS, Gamlia, Gamlia, Berghem, Berghem, Obs, Begbilar
 513
 514
 515 \textbf{Path to goal:}
 516 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 517
 518 \subsubsection{From: MIT to Flygplatsen}
 519
 520 \textbf{All expanded nodes:}
 521 MIT, Alidhem, Sofiehem, Berghem, Gamlia, NUS, NUS, GimonAs, Nydala, Station, Ok, Kyrkan, Ok, Rondellen, Ok, TreKorvar, Flygplatsen
 522
 523
 524 \textbf{Path to goal:}
 525 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 526
 527 \subsubsection{From: Nydala to Gamlia}
 528
 529 \textbf{All expanded nodes:}
 530 Nydala, MIT, Berghem, Gamlia
 531
 532
 533 \textbf{Path to goal:}
 534 Nydala, MIT, Berghem, Gamlia
 535
 536 \subsubsection{From: Teg to Foa}
 537
 538 \textbf{All expanded nodes:}
 539 Teg, Rondellen, Kyrkan, Station, Tegsbron, NUS, I20, I20, Gamlia, Gamlia, Berghem, Berghem, TreKorvar, Mariehem, Mariehem, Foa
 540
 541
 542 \textbf{Path to goal:}
 543 Teg, Rondellen, Kyrkan, NUS, Gamlia, Berghem, Mariehem, Foa
 544
 545 \subsection{Test Girig sökning}
 546 \subsubsection{From: Tegsbron to Nydala}
 547
 548 \textbf{All expanded nodes:}
 549 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 550
 551
 552 \textbf{Path to goal:}
 553 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 554
 555 \subsubsection{From: Flygplatsen to Begbilar}
 556
 557 \textbf{All expanded nodes:}
 558 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, Obs, Begbilar
 559
 560
 561 \textbf{Path to goal:}
 562 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 563
 564 \subsubsection{From: MIT to Flygplatsen}
 565
 566 \textbf{All expanded nodes:}
 567 MIT, Alidhem, Sofiehem, GimonAs, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 568
 569
 570 \textbf{Path to goal:}
 571 MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 572
 573 \subsubsection{From: Nydala to Gamlia}
 574
 575 \textbf{All expanded nodes:}
 576 Nydala, MIT, Berghem, Gamlia
 577
 578
 579 \textbf{Path to goal:}
 580 Nydala, MIT, Berghem, Gamlia
 581
 582 \subsubsection{From: Teg to Foa}
 583
 584 \textbf{All expanded nodes:}
 585 Teg, Tegsbron, I20, Obs, Foa
 586
 587
 588 \textbf{Path to goal:}
 589 Teg, Tegsbron, I20, Obs, Foa
 590
 591 \newpage
 592 \appendix
 593 \section{Källkod}
 594 \pagenumbering{roman}
 595
 596 \subsection{MySearcher.java}
 597 \begin{footnotesize}
 598   \verbatiminput{../src/MySearcher.java}
 599 \end{footnotesize}
 600
 601 \subsection{Graph.java}
 602 \begin{footnotesize}
 603   \verbatiminput{../src/Graph.java}
 604 \end{footnotesize}
 605
 606 \subsection{GraphNode.java}
 607 \begin{footnotesize}
 608   \verbatiminput{../src/GraphNode.java}
 609 \end{footnotesize}
 610
 611 \subsection{GraphTest.java}
 612 \begin{footnotesize}
 613   \verbatiminput{../test/GraphTest.java}
 614 \end{footnotesize}
 615
 616 \subsection{MySearcherTest.java}
 617 \begin{footnotesize}
 618   \verbatiminput{../test/MySearcherTest.java}
 619 \end{footnotesize}
 620 \end{document}