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