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}) och information om vilken nod
 153 den har besökts ifrån (\textbf{parent}).
 154
 155 \subsection{Oinformerade sökalgoritmer}
 156 Följande sökalgoritmer tar emot två parametrar, \textit{from} och
 157 \textit{to} som anger från vilken nod i grafen algoritmen ska börja
 158 och till vilken nod som ska sökas.
 159
 160 Förutom att algoritmerna använder olika typer av datastrukturer för
 161 att lagra noder så agerar de enligt följande procedur:
 162 \begin{enumerate}
 163 \item Lägg till första noden i en \textit{datastruktur}.
 164 \item Ta ut en nod \textbf{n} ur \textit{datastrukturen}.\label{Otaut}
 165   \begin{enumerate}
 166   \item Markera noden som besökt.
 167   \item Om noden som besöks är målnoden avslutas sökningen och
 168     resultat returneras.
 169   \item Annars läggs alla obesökta grannoder till i
 170     \textit{datastrukturen}, om de inte redan finns representerade i
 171     den, och en länk till noden \textbf{n} sparas i ett attribut
 172     \textbf{parent}.\label{Oparent}
 173   \end{enumerate}
 174 \item Börja om från steg \ref{Otaut}.
 175 \end{enumerate}
 176
 177 För varje besökt nod läggs dess namn till i en sträng. Anledningen
 178 till att man sparar föregående besökt nod i ett attribut
 179 \textbf{parent}, i steg \ref{Oparent}, är att när målet har nåtts blir
 180 det möjligt att stega tillbaka med hjälp av dessa attribut för att
 181 hitta vägen algoritmen valt mellan start och mål.
 182
 183 Har algoritmen hittat målnoden returneras en sträng som innehåller alla
 184 besökta noder och en sträng innehållande den hittade vägen från
 185 startnod till målnod.
 186
 187 Är \textit{datastrukturen} i steg \ref{Otaut} tom, så är alla noder
 188 besökta utan att något mål är hittat. En sträng som förklarar det
 189 inträffade returneras.
 190
 191 \subsubsection{breadthFirst(String from, String to)}
 192 Bredden-först använder datastrukturen stack för att spara noder. Detta
 193 medför att den först besökta nodens alla barn kommer att besökas innan
 194 algoritmen går vidare nästa steg djupare i kartan, därav namnet
 195 Bredden-först.
 196
 197 \subsubsection{depthFirst(String from, String to)}
 198 Djupet-först algoritmen sparar noder i datastrukturen kö. Detta medför
 199 att noderna kommer att plockas ut enligt ''Första in första
 200 ut''-principen, således vandrar algoritmen på djupet i grafen innan
 201 den går på bredden.
 202
 203 \subsection{Informerade sökalgoritmer}
 204 Följande algoritmer använder sig av någon typ av evalueringsfunktion
 205 $f$ som används för bedömning av vilket väg som är bäst att ta.
 206 Evalueringsfunktionen i sin tur beror av någon typ av heuristik,
 207 dvs. någon nivå av kunskap eller information om världen den evaluerar.
 208
 209 \subsubsection{greedySearch(String from, String to)}
 210 Metoden \textit{greedySearch} utför en sökning efter en väg mellan
 211 platserna \verb!from! och \verb!to! efter en ''girig'' algoritm.
 212 Algoritmen börjar på den plats som \verb!from! representerar och
 213 undersöker vilka noder den kan gå till i nästa steg. För dessa
 214 noder undersöker den vilket steg som leder till att den färdas
 215 geografiskt närmare målnoden \verb!to! och väljer detta.
 216
 217 \subsubsection{aStar(String from, String to, boolean fastest)}
 218 Algoritmen $A^*$ (uttalas ''A-sjärna'') fungerar ungefär som
 219 \textit{greedySearch} men den använder ett annat sätt att välja vägen
 220 som den ska ta. Om parametern \verb!fastest! har värdet \verb!true!
 221 söker algoritmen efter den snabbaste vägen (som namnet antyder),
 222 annars söker den efter den kortaste vägen. Funktionen som bestämmer
 223 vilken väg som ska tas i kartan beror på två saker: 1) hur långt den
 224 nod man undersöker ligger från målnoden och 2a) hur långt man färdats
 225 totalt från startnoden eller 2b) hur lång tid det tagit att färdats
 226 från startnoden.
 227
 228 \section{Begränsningar}
 229 % Vilka problem och begränsningar har vår lösning
 230
 231 \section{Reflektioner}
 232 % Vad var krångligt, hur löste vi det. Allmänna synpunkter.
 233
 234 \section{Testkörningar}
 235 % Redogör för sökalgoritmernas för- och nackdelar, samt hur de
 236 % presterade på den givna uppgiften
 237
 238 \subsection{Test Bredden-först}
 239 \subsubsection{From: Tegsbron to Nydala}
 240
 241 \textbf{All expanded nodes:}
 242 Tegsbron, Teg, I20, Rondellen, Station, Obs, Kyrkan, TreKorvar, Gamlia, Foa, Begbilar, NUS, Flygplatsen, On, Berghem, Mariehem, Sofiehem, MIT, Nydala
 243
 244
 245 \textbf{Path to goal:}
 246 Tegsbron, I20, Obs, Foa, Mariehem, Nydala
 247
 248 \subsubsection{From: Flygplatsen to Begbilar}
 249
 250 \textbf{All expanded nodes:}
 251 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, NUS, Station, Tegsbron, Sofiehem, Gamlia, I20, Obs, Alidhem, GimonAs, Berghem, Foa, Begbilar
 252
 253
 254 \textbf{Path to goal:}
 255 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 256
 257 \subsubsection{From: MIT to Flygplatsen}
 258
 259 \textbf{All expanded nodes:}
 260 MIT, Berghem, Alidhem, Nydala, Mariehem, Gamlia, Sofiehem, Ok, Foa, NUS, Station, GimonAs, Begbilar, Obs, Kyrkan, I20, Rondellen, Tegsbron, TreKorvar, Teg, Flygplatsen
 261
 262
 263 \textbf{Path to goal:}
 264 MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 265
 266 \subsubsection{From: Nydala to Gamlia}
 267
 268 \textbf{All expanded nodes:}
 269 Nydala, Ok, Mariehem, MIT, Alidhem, Berghem, Foa, Sofiehem, Gamlia
 270
 271
 272 \textbf{Path to goal:}
 273 Nydala, Mariehem, Berghem, Gamlia
 274
 275 \subsubsection{From: Teg to Foa}
 276
 277 \textbf{All expanded nodes:}
 278 Teg, Tegsbron, Rondellen, I20, Kyrkan, TreKorvar, Station, Obs, NUS, Flygplatsen, On, Gamlia, Foa
 279
 280
 281 \textbf{Path to goal:}
 282 Teg, Tegsbron, I20, Obs, Foa
 283
 284 \subsection{Test Djupet-först}
 285 \subsubsection{From: Tegsbron to Nydala}
 286
 287 \textbf{All expanded nodes:}
 288 Tegsbron, I20, Obs, Foa, Mariehem, Nydala
 289
 290
 291 \textbf{Path to goal:}
 292 Tegsbron, I20, Obs, Foa, Mariehem, Nydala
 293
 294 \subsubsection{From: Flygplatsen to Begbilar}
 295
 296 \textbf{All expanded nodes:}
 297 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 298
 299
 300 \textbf{Path to goal:}
 301 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 302
 303 \subsubsection{From: MIT to Flygplatsen}
 304
 305 \textbf{All expanded nodes:}
 306 MIT, Alidhem, Ok, Sofiehem, GimonAs, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen
 307
 308
 309 \textbf{Path to goal:}
 310 MIT, Alidhem, Sofiehem, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen
 311
 312 \subsubsection{From: Nydala to Gamlia}
 313
 314 \textbf{All expanded nodes:}
 315 Nydala, Mariehem, Berghem, Gamlia
 316
 317
 318 \textbf{Path to goal:}
 319 Nydala, Mariehem, Berghem, Gamlia
 320
 321 \subsubsection{From: Teg to Foa}
 322
 323 \textbf{All expanded nodes:}
 324 Teg, Tegsbron, I20, Obs, Foa
 325
 326
 327 \textbf{Path to goal:}
 328 Teg, Tegsbron, I20, Obs, Foa
 329
 330 \subsection{Test A* snabbast}
 331 \subsubsection{From: Tegsbron to Nydala}
 332
 333 \textbf{All expanded nodes:}
 334 Tegsbron, I20, Teg, Station, Gamlia, Rondellen, Obs, Berghem, NUS, Kyrkan, TreKorvar, MIT, Nydala
 335
 336
 337 \textbf{Path to goal:}
 338 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 339
 340 \subsubsection{From: Flygplatsen to Begbilar}
 341
 342 \textbf{All expanded nodes:}
 343 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, Station, NUS, Tegsbron, Obs, Begbilar
 344
 345
 346 \textbf{Path to goal:}
 347 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 348
 349 \subsubsection{From: MIT to Flygplatsen}
 350
 351 \textbf{All expanded nodes:}
 352 MIT, Alidhem, Berghem, Sofiehem, Nydala, GimonAs, Gamlia, NUS, Ok, Mariehem, Station, Kyrkan, Rondellen, I20, TreKorvar, Flygplatsen
 353
 354
 355 \textbf{Path to goal:}
 356 MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 357
 358 \subsubsection{From: Nydala to Gamlia}
 359
 360 \textbf{All expanded nodes:}
 361 Nydala, MIT, Berghem, Gamlia
 362
 363
 364 \textbf{Path to goal:}
 365 Nydala, MIT, Berghem, Gamlia
 366
 367 \subsubsection{From: Teg to Foa}
 368
 369 \textbf{All expanded nodes:}
 370 Teg, Tegsbron, Rondellen, I20, Kyrkan, TreKorvar, Obs, Foa
 371
 372
 373 \textbf{Path to goal:}
 374 Teg, Tegsbron, I20, Obs, Foa
 375
 376 \subsection{Test A* kortast}
 377 \subsubsection{From: Tegsbron to Nydala}
 378
 379 \textbf{All expanded nodes:}
 380 Tegsbron, I20, Teg, Station, Rondellen, Gamlia, Berghem, NUS, Kyrkan, TreKorvar, Obs, MIT, Sofiehem, Nydala
 381
 382
 383 \textbf{Path to goal:}
 384 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 385
 386 \subsubsection{From: Flygplatsen to Begbilar}
 387
 388 \textbf{All expanded nodes:}
 389 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, Station, NUS, Tegsbron, Gamlia, Obs, Sofiehem, Begbilar
 390
 391
 392 \textbf{Path to goal:}
 393 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 394
 395 \subsubsection{From: MIT to Flygplatsen}
 396
 397 \textbf{All expanded nodes:}
 398 MIT, Alidhem, Berghem, Nydala, Sofiehem, Gamlia, GimonAs, Ok, NUS, Station, Mariehem, Kyrkan, I20, Rondellen, TreKorvar, Flygplatsen
 399
 400
 401 \textbf{Path to goal:}
 402 MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 403
 404 \subsubsection{From: Nydala to Gamlia}
 405
 406 \textbf{All expanded nodes:}
 407 Nydala, MIT, Ok, Berghem, Gamlia
 408
 409
 410 \textbf{Path to goal:}
 411 Nydala, MIT, Berghem, Gamlia
 412
 413 \subsubsection{From: Teg to Foa}
 414
 415 \textbf{All expanded nodes:}
 416 Teg, Rondellen, Tegsbron, Kyrkan, I20, TreKorvar, NUS, Station, Obs, On, Flygplatsen, Gamlia, Sofiehem, Foa
 417
 418
 419 \textbf{Path to goal:}
 420 Teg, Tegsbron, I20, Obs, Foa
 421
 422 \subsection{Test Girig sökning}
 423 \subsubsection{From: Tegsbron to Nydala}
 424
 425 \textbf{All expanded nodes:}
 426 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 427
 428
 429 \textbf{Path to goal:}
 430 Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala
 431
 432 \subsubsection{From: Flygplatsen to Begbilar}
 433
 434 \textbf{All expanded nodes:}
 435 Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, Obs, Begbilar
 436
 437
 438 \textbf{Path to goal:}
 439 Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar
 440
 441 \subsubsection{From: MIT to Flygplatsen}
 442
 443 \textbf{All expanded nodes:}
 444 MIT, Alidhem, Sofiehem, GimonAs, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 445
 446
 447 \textbf{Path to goal:}
 448 MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen
 449
 450 \subsubsection{From: Nydala to Gamlia}
 451
 452 \textbf{All expanded nodes:}
 453 Nydala, MIT, Berghem, Gamlia
 454
 455
 456 \textbf{Path to goal:}
 457 Nydala, MIT, Berghem, Gamlia
 458
 459 \subsubsection{From: Teg to Foa}
 460
 461 \textbf{All expanded nodes:}
 462 Teg, Tegsbron, I20, Obs, Foa
 463
 464
 465 \textbf{Path to goal:}
 466 Teg, Tegsbron, I20, Obs, Foa
 467
 468 \section{Diskussion}
 469 * Angående att vi måste loopa igenom alla noder två gånger:
 470     Detta beror på att det inte går att lägga till en väg mellan en
 471     nod och en nod som inte ännu existerar i minnet. Detta skulle
 472     kanske kunnat lösas genom att man faktiskt skapar den nod som inte
 473     finns och lägger till information om nodens position när man
 474     kommer till de noderna senare när man kommer till den noden i
 475     DOM-dokumentet. Metoder hade då behövt skrivas för att sätta
 476     koordinaternas värden för en nod. Vi valde att gå igenom noderna
 477     två gånger i stället därför att det kändes lättast då vi skrev
 478     metoden.
 479
 480 \newpage
 481 \appendix
 482 \section{Källkod}
 483 \pagenumbering{roman}
 484
 485 \subsection{MySearcher.java}
 486 \begin{footnotesize}
 487   \verbatiminput{../src/MySearcher.java}
 488 \end{footnotesize}
 489
 490 \subsection{Graph.java}
 491 \begin{footnotesize}
 492   \verbatiminput{../src/Graph.java}
 493 \end{footnotesize}
 494
 495 \subsection{GraphNode.java}
 496 \begin{footnotesize}
 497   \verbatiminput{../src/GraphNode.java}
 498 \end{footnotesize}
 499
 500 \subsection{GraphTest.java}
 501 \begin{footnotesize}
 502   \verbatiminput{../test/GraphTest.java}
 503 \end{footnotesize}
 504
 505 \subsection{MySearcherTest.java}
 506 \begin{footnotesize}
 507   \verbatiminput{../test/MySearcherTest.java}
 508 \end{footnotesize}
 509 \end{document}