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{Road.java}
 160 Klassen Road används som kanter i grafen. Den sparar undan information
 161 om varje kant/väg i kartan. Detta görs i attributen för hastighet
 162 \textbf{speed}, avstånd \textbf{distance} och tid det tar att färdas
 163 hela vägens sträcka i maxhastighet \textbf{travelTime}.
 164
 165 \subsection{Oinformerade sökalgoritmer}
 166 Följande sökalgoritmer tar emot två parametrar, \textit{from} och
 167 \textit{to} som anger från vilken nod i grafen algoritmen ska börja
 168 och till vilken nod som ska sökas.
 169
 170 Förutom att algoritmerna använder olika typer av datastrukturer för
 171 att lagra noder så agerar de enligt följande procedur:
 172 \begin{enumerate}
 173 \item Lägg till första noden i en \textit{datastruktur}.
 174 \item Ta ut en nod \textbf{n} ur \textit{datastrukturen}.\label{Otaut}
 175   \begin{enumerate}
 176   \item Markera noden som besökt.
 177   \item Om noden som besöks är målnoden avslutas sökningen och
 178     resultat returneras.
 179   \item Annars läggs alla obesökta grannoder till i
 180     \textit{datastrukturen}, om de inte redan finns representerade i
 181     den, och en länk till noden \textbf{n} sparas i ett attribut
 182     \textbf{parent}.\label{Oparent}
 183   \end{enumerate}
 184 \item Börja om från steg \ref{Otaut}.
 185 \end{enumerate}
 186
 187 För varje besökt nod läggs dess namn till i en sträng. Anledningen
 188 till att man sparar föregående besökt nod i ett attribut
 189 \textbf{parent}, i steg \ref{Oparent}, är att när målet har nåtts blir
 190 det möjligt att stega tillbaka med hjälp av dessa attribut för att
 191 hitta vägen algoritmen valt mellan start och mål.
 192
 193 Har algoritmen hittat målnoden returneras en sträng som innehåller alla
 194 besökta noder och en sträng innehållande den hittade vägen från
 195 startnod till målnod.
 196
 197 Är \textit{datastrukturen} i steg \ref{Otaut} tom, så är alla noder
 198 besökta utan att något mål är hittat. En sträng som förklarar det
 199 inträffade returneras.
 200
 201 \subsubsection{breadthFirst(String from, String to)}
 202 Bredden-först använder datastrukturen stack för att spara noder. Detta
 203 medför att den först besökta nodens alla barn kommer att besökas innan
 204 algoritmen går vidare nästa steg djupare i kartan, därav namnet
 205 Bredden-först.
 206
 207 \subsubsection{depthFirst(String from, String to)}
 208 Djupet-först-algoritmen sparar noder i datastrukturen kö. Detta medför
 209 att noderna kommer att plockas ut enligt ''Första in första
 210 ut''-principen, således vandrar algoritmen på djupet i grafen innan
 211 den går på bredden.
 212
 213 \subsection{Informerade sökalgoritmer}
 214 Följande algoritmer använder sig av någon typ av evalueringsfunktion
 215 $f$ som används för bedömning av vilket väg som är bäst att ta.
 216 Evalueringsfunktionen i sin tur beror av någon typ av heuristik,
 217 dvs. någon nivå av kunskap eller information om världen den evaluerar.
 218
 219 \subsubsection{greedySearch(String from, String to)}
 220 Metoden \textit{greedySearch} utför en sökning efter en väg mellan
 221 platserna \verb!from! och \verb!to! efter en ''girig'' algoritm.
 222 Algoritmen börjar på den plats som \verb!from! representerar och
 223 undersöker vilka noder den kan gå till i nästa steg. För var och en av
 224 dessa noder undersöker den vilket steg som leder till att den färdas
 225 geografiskt närmare målnoden (fågelvägen) \verb!to! och väljer detta.
 226
 227 \subsubsection{aStar(String from, String to, boolean fastest)}
 228 Algoritmen $A^*$ (uttalas ''A-sjärna'') fungerar ungefär som
 229 \textit{greedySearch} men den använder ett annat sätt att välja vägen
 230 som den ska ta. Om parametern \verb!fastest! har värdet \verb!true!
 231 söker algoritmen efter den snabbaste vägen (som namnet antyder),
 232 annars söker den efter den kortaste vägen. Funktionen som bestämmer
 233 vilken väg som ska tas i kartan beror på två saker: 1) hur långt den
 234 nod man undersöker ligger från målnoden och 2a) hur långt man färdats
 235 totalt från startnoden eller 2b) hur lång tid det tagit att färdats
 236 från startnoden.
 237
 238 \subsection{API, dokumentation}
 239 En API-dokumentation av implementationen finns på sidan:\\
 240 \verb!http://www.cs.umu.se/~dit06vzy/ai/lab2/doc/!
 241
 242 \section{Begränsningar}
 243 % Vilka problem och begränsningar har vår lösning
 244 Implementationen av grafen (\textit{Graph.java}) är inte gjord med
 245 generics. Detta innebär att det vissa datatyper, till exempel
 246 (\textit{Road.java}), som vi använder för att spara vägar i grafen
 247 måste explicit konverteras till rätt datatyp innan dess metoder kan
 248 anropas.
 249
 250 \section{Reflektioner}
 251 % Vad var krångligt, hur löste vi det. Allmänna synpunkter.
 252 När målet väl hittats i algoritmerna var det inte helt självklart hur
 253 vägen till målet skulle sparas. Vi löste det genom att algoritmen
 254 ''lägger spår'' efter sig när den söker, genom metoden
 255 \verb!GraphNode.setParent(GraphNode node)! som sätter en nods
 256 ''förälder'' till \verb!node!. När målnoden nåtts stegar sedan
 257 algoritmerna längs länken som skapats från startnoden till målnoden
 258 och tar fram vägen till målet på så sätt.
 259
 260 Vi hade lite problem med att inse att vi behövde ha en separat
 261 evaluerings\-funktion i A*-algoritmen och ett attribut i klassen
 262 \verb!GraphNode! för att hålla reda på varje nods
 263 evaluerings\-funktions\-värde. Innan vi insåg detta använde vi
 264 attributet i \verb!GraphNode! som egentligen ska hålla reda på
 265 stigkostnad. Vi insåg att det var något fel med vår algoritm då vi
 266 jämförde våra algoritmers lösningar (valda sökvägar) med andra grupper
 267 i klassen.
 268
 269 Metoden setMap i klassen MySearcher måste loopa igenom alla noder ur
 270 xml-filen två gånger. Detta beror på att det inte går att lägga till
 271 en väg mellan en nod och en nod som inte ännu existerar i
 272 minnet. Detta skulle kanske kunnat lösas genom att man faktiskt skapar
 273 den nod som inte finns och lägger till information om nodens position
 274 när man kommer till de noderna senare när man kommer till den noden i
 275 DOM-dokumentet. Metoder hade då behövt skrivas för att sätta
 276 koordinaternas värden för en nod. Vi valde att gå igenom noderna två
 277 gånger i stället därför att det kändes lättast då vi skrev metoden.
 278
 279 Det hade varit bra med klargörande i labbspecifikationen vi fick ut
 280 att kartan kunde ha enkelriktade vägar. Det enda sättet detta gick att
 281 notera var om man gick igenom xml-filen noggrannt och kollade upp
 282 varje väg som fanns. Mycket onödigt felsökande och i vårt fall
 283 omimplementation av hela vår graf hade kunnat undvikas.
 284
 285 \section{Diskussion}
 286 % Redogör för sökalgoritmernas för- och nackdelar, samt hur de
 287 % presterade på den givna uppgiften
 288
 289 \subsection{Bredden-först-sökning}
 290 Fördelen med Bredden-först-sökning var att den är väldigt enkel att
 291 implementera. Den bakomliggande logiken är lätt att förstå och det
 292 behöves ingen specialkunskap om domänen sökningen sker i.
 293
 294 Nackdelen med denna sökning är att om sökningen sker i en stor graf så
 295 kommer algoritmen att besöka väldigt många noder innan den hittar fram
 296 till målet. För varje steg djupare ($d$) algoritmen tar, så ökar
 297 antalet noder som besöks med $d^{b}$, där $b$ = maximala antalet
 298 grannoder, för lite större $d$ kommer detta att bli väldigt många
 299 noder, vilket resulterar i att minnesanvändandet i algoritmen blir
 300 stor.
 301
 302 Bredden-först-algoritmen är komplett, det vill säga den hittar alltid
 303 fram till målet om det finns. Detta går att härleda eftersom
 304 Bredden-först-algoritmen eventuellt kommer att besöka varenda nod som
 305 existerar i grafen.
 306
 307 I en graf där alla vägar väger lika mycket, kommer Bredden-först att
 308 hitta den optimala lösningen (snabbaste/kortaste vägen till mål),
 309 eftersom algoritmen har gått vägen med minst antal steg. För generella
 310 grafer där vägarna kan ha olika viktkostnader kommer dock
 311 Bredden-först inte att vara optimal. Detta är fallet i grafen som
 312 används i denna laboration.
 313
 314 \subsection{Djupet-först-sökning}
 315 Djupet-först-sökning är, precis som Bredden-först-sökning enkel att
 316 implementera, ingen kunskap om målet behövs förutom en koll för att se
 317 när målet är nått.
 318
 319 Liksom Bredden-först-sökning så kommer Djupet-först att besöka alla
 320 noder i grafen tills den har hittat målnoden, algoritmen är således
 321 komplett. Utrymmet som krävs kommer att vara beroende av den djupaste
 322 vägen till målet, eller mer exakt $b^{d}$, där $b$ är bredden eller
 323 antalet grannoder och $d$ är djupet.
 324
 325 I testkörningarna, på sida \pageref{tests}, syns att jämfört med
 326 Bredden-först kommer Djupet-först-sökning att hitta målet utan att
 327 expandera lika många noder. Vägen till målet är dock ofta en lång
 328 omväg eftersom algoritmen, i grafer, ofta kommer att hitta målet på
 329 första djupsökning. Algoritmen är således inte optimal.
 330
 331 Eftersom Djupet-först i denna implementation avnänder sig av ett
 332 attribut, \textbf{visited}, så kommer inte samma nod att besökas två
 333 gånger. Detta gör att algoritmen undviker att hamna i cykler där den
 334 snurrar runt mellan samma noder.
 335
 336 \subsection{Girig sökning}
 337 Fördelen med en girig sökning är att den har någon typ av
 338 evalueringsfunktion $f(n)$ ($f(n) = h(n)$) som gör att den inte
 339 accepterar vilken lösning på ett problem (sökning i karta till
 340 exempel) som helst, utan väljer, om något naivt, en i genomsnitt
 341 bättre lösning än en oinformerad sökning. Nackdelen med en girig
 342 sökning är att den inte tar hänsyn till totala kostnaden för en
 343 lösning jämfört med en annan lösning, utan nöjer sig med första bästa
 344 lösning (s.k. Best-first search).
 345
 346 En annan nackdel med girig sökning är att man skulle kunna hamna i ett
 347 läge där man hoppar mellan två noder i kartan i all oändlighet, givet
 348 att algoritmen inte håller reda på vilka punkter den redan besökt
 349 (vilket vår implementation gör).
 350
 351 \subsection{A* sökning}
 352 En uppenbar fördel med A*-algoritmen är faktumet att den är optimal,
 353 dvs. den hittar den absolut bästa vägen. Den använder sig, som den
 354 giriga sök\-algoritmen, av en evaluerings\-funktion $f(n)$. Men $f(n)$
 355 för A* är mer informerad än den giriga då A* är optimal och den giriga
 356 inte är det. Den ytterligare informationen ligger i att A* håller reda
 357 på hur långt den har gått totalt, alltså stigkostnaden. En nackdel kan
 358 däremot vara att A* måste expandera fler noder för att kunna avgöra
 359 vilken väg som är faktiskt är bäst, och att den då kan kräva lite mer
 360 minne. Något som också tar lite extra minne är att vi sparar värdet
 361 för evaluerings\-funktionen i varje nod. Att den måste expandera fler
 362 noder kan möjligtvis också ta längre tid än mindre informerade (och
 363 icke\-optimala) algoritmer.
 364
 365 \section{Testkörningar}\label{tests}
 366 \subsection{Test Bredden-först}
 367 \subsubsection{From: Tegsbron to Nydala}
 368
 369 \textbf{All expanded nodes:}
 370 Tegsbron, I20, Teg, Station, Obs, Rondellen, Gamlia, Foa, Begbilar, TreKorvar, Kyrkan, NUS, Berghem, Mariehem, Flygplatsen, On, Sofiehem, MIT, Nydala
 371
 372
 373 \textbf{Path to goal:}
 374 Tegsbron, I20, Obs, Foa, Mariehem, Nydala
 375
 376 \subsubsection{From: Flygplatsen to Begbilar}
 377
 378 \textbf{All expanded nodes:}
 379 Flygplatsen, TreKorvar, Rondellen, On, Teg, Kyrkan, Tegsbron, NUS, Station, I20, Gamlia, Sofiehem, Obs, Berghem, GimonAs, Alidhem, Foa, Begbilar
 380
 381
 382 \textbf{Path to goal:}
 383 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 384
 385 \subsubsection{From: MIT to Flygplatsen}
 386
 387 \textbf{All expanded nodes:}
 388 MIT, Nydala, Berghem, Alidhem, Mariehem, Ok, Gamlia, Sofiehem, Foa, Station, NUS, GimonAs, Begbilar, Obs, I20, Kyrkan, Tegsbron, Rondellen, Teg, TreKorvar, Flygplatsen
 389
 390
 391 \textbf{Path to goal:}
 392 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 393
 394 \subsubsection{From: Nydala to Gamlia}
 395
 396 \textbf{All expanded nodes:}
 397 Nydala, Ok, Mariehem, MIT, Alidhem, Foa, Berghem, Sofiehem, Obs, Begbilar, Gamlia
 398
 399
 400 \textbf{Path to goal:}
 401 Nydala, Mariehem, Berghem, Gamlia
 402
 403 \subsubsection{From: Teg to Foa}
 404
 405 \textbf{All expanded nodes:}
 406 Teg, Rondellen, Tegsbron, Kyrkan, TreKorvar, I20, Station, NUS, Flygplatsen, On, Obs, Gamlia, Sofiehem, Foa
 407
 408
 409 \textbf{Path to goal:}
 410 Teg, Tegsbron, I20, Obs, Foa
 411
 412 \subsection{Test Djupet-först}
 413 \subsubsection{From: Tegsbron to Nydala}
 414
 415 \textbf{All expanded nodes:}
 416 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Sofiehem, Alidhem, Ok, Nydala
 417
 418
 419 \textbf{Path to goal:}
 420 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Sofiehem, Alidhem, Ok, Nydala
 421
 422 \subsubsection{From: Flygplatsen to Begbilar}
 423
 424 \textbf{All expanded nodes:}
 425 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar
 426
 427
 428 \textbf{Path to goal:}
 429 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar
 430
 431 \subsubsection{From: MIT to Flygplatsen}
 432
 433 \textbf{All expanded nodes:}
 434 MIT, Alidhem, Ok, Sofiehem, GimonAs, NUS, Gamlia, Station, Obs, Begbilar, Foa, Mariehem, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen
 435
 436
 437 \textbf{Path to goal:}
 438 MIT, Alidhem, Sofiehem, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen
 439
 440 \subsubsection{From: Nydala to Gamlia}
 441
 442 \textbf{All expanded nodes:}
 443 Nydala, MIT, Alidhem, Sofiehem, NUS, Kyrkan, Station, Obs, Begbilar, Foa, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen, On, Gamlia
 444
 445
 446 \textbf{Path to goal:}
 447 Nydala, MIT, Alidhem, Sofiehem, NUS, Gamlia
 448
 449 \subsubsection{From: Teg to Foa}
 450
 451 \textbf{All expanded nodes:}
 452 Teg, Tegsbron, I20, Obs, Foa
 453
 454
 455 \textbf{Path to goal:}
 456 Teg, Tegsbron, I20, Obs, Foa
 457
 458 \subsection{Test A* snabbast}
 459 \subsubsection{From: Tegsbron to Nydala}
 460
 461 \textbf{All expanded nodes:}
 462 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
 463
 464
 465 \textbf{Path to goal:}
 466 Tegsbron, Teg, Rondellen, Kyrkan, NUS, Gamlia, Berghem, Mariehem, Nydala
 467
 468 \subsubsection{From: Flygplatsen to Begbilar}
 469
 470 \textbf{All expanded nodes:}
 471 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
 472
 473
 474 \textbf{Path to goal:}
 475 Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Foa, Begbilar
 476
 477 \subsubsection{From: MIT to Flygplatsen}
 478
 479 \textbf{All expanded nodes:}
 480 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
 481
 482
 483 \textbf{Path to goal:}
 484 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 485
 486 \subsubsection{From: Nydala to Gamlia}
 487
 488 \textbf{All expanded nodes:}
 489 Nydala, Ok, MIT, Alidhem, Mariehem, Alidhem, Berghem, Berghem, Gamlia
 490
 491
 492 \textbf{Path to goal:}
 493 Nydala, Mariehem, Berghem, Gamlia
 494
 495 \subsubsection{From: Teg to Foa}
 496
 497 \textbf{All expanded nodes:}
 498 Teg, Tegsbron, Rondellen, Kyrkan, I20, Station, Obs, Station, NUS, TreKorvar, Gamlia, Gamlia, Berghem, Berghem, Sofiehem, Flygplatsen, Mariehem, Mariehem, Alidhem, On, Obs, Foa
 499
 500
 501 \textbf{Path to goal:}
 502 Teg, Tegsbron, I20, Station, Obs, Foa
 503
 504 \subsection{Test A* kortast}
 505 \subsubsection{From: Tegsbron to Nydala}
 506
 507 \textbf{All expanded nodes:}
 508 Tegsbron, I20, Station, Gamlia, Berghem, NUS, MIT, Nydala
 509
 510
 511 \textbf{Path to goal:}
 512 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 513
 514 \subsubsection{From: Flygplatsen to Begbilar}
 515
 516 \textbf{All expanded nodes:}
 517 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, NUS, Gamlia, Gamlia, Berghem, Berghem, Obs, Begbilar
 518
 519
 520 \textbf{Path to goal:}
 521 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 522
 523 \subsubsection{From: MIT to Flygplatsen}
 524
 525 \textbf{All expanded nodes:}
 526 MIT, Alidhem, Sofiehem, Berghem, Gamlia, NUS, NUS, GimonAs, Nydala, Station, Ok, Kyrkan, Ok, Rondellen, Ok, TreKorvar, Flygplatsen
 527
 528
 529 \textbf{Path to goal:}
 530 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 531
 532 \subsubsection{From: Nydala to Gamlia}
 533
 534 \textbf{All expanded nodes:}
 535 Nydala, MIT, Berghem, Gamlia
 536
 537
 538 \textbf{Path to goal:}
 539 Nydala, MIT, Berghem, Gamlia
 540
 541 \subsubsection{From: Teg to Foa}
 542
 543 \textbf{All expanded nodes:}
 544 Teg, Rondellen, Kyrkan, Station, Tegsbron, NUS, I20, I20, Gamlia, Gamlia, Berghem, Berghem, TreKorvar, Mariehem, Mariehem, Foa
 545
 546
 547 \textbf{Path to goal:}
 548 Teg, Rondellen, Kyrkan, NUS, Gamlia, Berghem, Mariehem, Foa
 549
 550 \subsection{Test Girig sökning}
 551 \subsubsection{From: Tegsbron to Nydala}
 552
 553 \textbf{All expanded nodes:}
 554 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 555
 556
 557 \textbf{Path to goal:}
 558 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 559
 560 \subsubsection{From: Flygplatsen to Begbilar}
 561
 562 \textbf{All expanded nodes:}
 563 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, Obs, Begbilar
 564
 565
 566 \textbf{Path to goal:}
 567 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 568
 569 \subsubsection{From: MIT to Flygplatsen}
 570
 571 \textbf{All expanded nodes:}
 572 MIT, Alidhem, Sofiehem, GimonAs, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 573
 574
 575 \textbf{Path to goal:}
 576 MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 577
 578 \subsubsection{From: Nydala to Gamlia}
 579
 580 \textbf{All expanded nodes:}
 581 Nydala, MIT, Berghem, Gamlia
 582
 583
 584 \textbf{Path to goal:}
 585 Nydala, MIT, Berghem, Gamlia
 586
 587 \subsubsection{From: Teg to Foa}
 588
 589 \textbf{All expanded nodes:}
 590 Teg, Tegsbron, I20, Obs, Foa
 591
 592
 593 \textbf{Path to goal:}
 594 Teg, Tegsbron, I20, Obs, Foa
 595
 596 \newpage
 597 \appendix
 598 \section{Källkod}
 599 \pagenumbering{roman}
 600
 601 \subsection{MySearcher.java}
 602 \begin{footnotesize}
 603   \verbatiminput{../src/MySearcher.java}
 604 \end{footnotesize}
 605
 606 \subsection{Graph.java}
 607 \begin{footnotesize}
 608   \verbatiminput{../src/Graph.java}
 609 \end{footnotesize}
 610
 611 \subsection{GraphNode.java}
 612 \begin{footnotesize}
 613   \verbatiminput{../src/GraphNode.java}
 614 \end{footnotesize}
 615
 616 \subsection{Road.java}
 617 \begin{footnotesize}
 618   \verbatiminput{../src/Road.java}
 619 \end{footnotesize}
 620
 621 \subsection{GraphTest.java}
 622 \begin{footnotesize}
 623   \verbatiminput{../test/GraphTest.java}
 624 \end{footnotesize}
 625
 626 \subsection{MySearcherLatexTest.java}
 627 \begin{footnotesize}
 628   \verbatiminput{../test/MySearcherLatexTest.java}
 629 \end{footnotesize}
 630 \end{document}