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 dit06***/ait/lab2, där *** är antingen ''ajn''
  87 eller ''vzy'', genom att ange följande kommando:
  88
  89 \begin{verbatim}
  90 java -cp lib/jdom.jar:bin/prod SearchInterface MySearcher <sökväg till karta> <metod> [startnod [slutnod]]
  91 \end{verbatim}
  92
  93 Om varken startnod eller slutnod anges efterfrågas de av
  94 programmet. Om en (1) nod anges som parameter antas den vara startnod
  95 och då efterfrågas bara slutnod av programmet. Annars, om både
  96 startnod och slutnod anges körs vald metod (algoritm) för att hitta
  97 vägen mellan noderna.
  98
  99 \section{Metod- och Algoritmbeskrivning}
 100
 101 \subsection{setMap(File mapFile)}
 102 Denna metod läser in en karta i form av en XML-fil och representerar
 103 den i en graf. Implementationen av grafen är en modifierad version av
 104 Graph.java som vi använde i kursen Datastrukturer och Algoritmer.
 105
 106 När XML-filen lästs in och tolkats som ett DOM-dokument skaffas alla
 107 noder fram ur detta och sparas i grafen som objekt av typen
 108 \verb!GraphNode!. Dessa objekt innehåller x- och y-koordinater för
 109 noden och ett ''ID'' vilket är namnet på platsen på kartan som noden
 110 representerar. Sedan gås alla noder igenom ännu en gång för att lägga
 111 till vägar och hastighetsbegränsningar mellan dem. Metoden skriver
 112 även ut felmeddelanden om filen 1) inte hittas, 2) inte kan läsas av
 113 någon annan anledning, 3) om det är något fel på innehållet i filen
 114 och vilket felet är, och 4) om någon av koordinaterna för någon nod
 115 inte kan tolkas som ett heltal. Programmet avslutas om något av
 116 ovanstående fel uppstår.
 117
 118 \subsection{greedySearch(String from, String to)}
 119 Metoden \textit{greedySearch} utför en sökning efter en väg mellan
 120 platserna \verb!from! och \verb!to! efter en ''girig'' algoritm.
 121 Algoritmen börjar på den plats som \verb!from! representerar och
 122 undersöker vilka noder den kan gå till i nästa steg. För dessa
 123 noder undersöker den vilket steg som leder till att den färdas
 124 geografiskt närmare målnoden \verb!to! och väljer detta.
 125
 126 \subsection{aStar(String from, String to, boolean fastest)}
 127 Algoritmen A* (uttalas ''A-sjärna'') fungerar ungefär som
 128 \textit{greedySearch} men den använder ett annat sätt att välja vägen
 129 som den ska ta. Om parametern \verb!fastest! har värdet \verb!true!
 130 söker algoritmen efter den snabbaste vägen (som namnet antyder),
 131 annars söker den efter den kortaste vägen. Funktionen som bestämmer
 132 vilken väg som ska tas i kartan beror på två saker: 1) hur långt den
 133 nod man undersöker ligger från målnoden och 2a) hur långt man färdats
 134 totalt från startnoden eller 2b) hur lång tid det tagit att färdats
 135 från startnoden.
 136
 137 \section{Begränsningar}
 138 \section{Reflektioner}
 139 \section{Testkörningar}
 140 \section{Diskussion}
 141 * Angående att vi måste loopa igenom alla noder två gånger:
 142     Detta beror på att det inte går att lägga till en väg mellan en
 143     nod och en nod som inte ännu existerar i minnet. Detta skulle
 144     kanske kunnat lösas genom att man faktiskt skapar den nod som inte
 145     finns och lägger till information om nodens position när man
 146     kommer till de noderna senare när man kommer till den noden i
 147     DOM-dokumentet. Metoder hade då behövt skrivas för att sätta
 148     koordinaternas värden för en nod. Vi valde att gå igenom noderna
 149     två gånger i stället därför att det kändes lättast då vi skrev
 150     metoden.
 151
 152 \newpage
 153 \appendix
 154 \section{Källkod}
 155 \pagenumbering{roman}
 156
 157 \subsection{MySearcher.java}
 158 \begin{footnotesize}
 159   \verbatiminput{../src/MySearcher.java}
 160 \end{footnotesize}
 161
 162 \subsection{Graph.java}
 163 \begin{footnotesize}
 164   \verbatiminput{../src/Graph.java}
 165 \end{footnotesize}
 166
 167 \subsection{GraphNode.java}
 168 \begin{footnotesize}
 169   \verbatiminput{../src/GraphNode.java}
 170 \end{footnotesize}
 171
 172 \subsection{GraphTest.java}
 173 \begin{footnotesize}
 174   \verbatiminput{../test/GraphTest.java}
 175 \end{footnotesize}
 176
 177 \subsection{MySearcherTest.java}
 178 \begin{footnotesize}
 179   \verbatiminput{../test/MySearcherTest.java}
 180 \end{footnotesize}
 181 \end{document}