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 laborationsrapport redovisar för hur en karta och olika
  71 sökalgoritmer implementeras i programmeringsspråket Java. Huvudfokus i
  72 rapporten ligger på analys och jämförelse mellan de olika
  73 sökalgoritmerna.
  74
  75 Fyra algoritmer av två olika typer är implementerade. Bredden-först
  76 sökning och Djupet-först sökning är två oinformerade sökningar som
  77 söker efter ett givit mål utan någon problemspecifik
  78 kunskap. Greedy-Search och A* är två informerade sökningar som
  79 använder sig av problemspecifik kunskap för att förbättra sin
  80 sökning. I det här fallet används till exempel kortaste vägen från
  81 varje nod till målet för att avgöra sökvägar i kartan.
  82
  83 Labbspecifikation finns att läsa på:\\
  84 \verb!http://www.cs.umu.se/kurser/5DV063/HT08/lab2.html!
  85
  86 \section{Användarhandledning}
  87 Programmet körs från dit06***/ait/lab2, där *** är antingen ''ajn''
  88 eller ''vzy'', genom att ange följande kommando:
  89
  90 \begin{verbatim}
  91 java -cp lib/jdom.jar:bin/prod SearchInterface MySearcher <sökväg till karta> <metod> [startnod [slutnod]]
  92 \end{verbatim}
  93
  94 Om varken startnod eller slutnod anges efterfrågas de av
  95 programmet. Om en (1) nod anges som parameter antas den vara startnod
  96 och då efterfrågas bara slutnod av programmet. Annars, om både
  97 startnod och slutnod anges körs vald metod (algoritm) för att hitta
  98 vägen mellan noderna.
  99
 100 \section{Metod- och Algoritmbeskrivning}
 101
 102 \subsection{\verb!public void setMap (File mapFile)!}
 103 Denna metod läser in en karta i form av en XML-fil och representerar
 104 den i en graf. Implementationen av grafen är en modifierad version av
 105 Graph.java som vi använde i kursen Datastrukturer och Algoritmer.
 106
 107 När XML-filen lästs in och tolkats som ett DOM-dokument skaffas alla
 108 noder fram ur detta och sparas i grafen som objekt av typen
 109 \verb!GraphNode!. Dessa objekt innehåller x- och y-koordinater för
 110 noden och ett ''ID'' vilket är namnet på platsen på kartan som noden
 111 representerar. Sedan gås alla noder igenom ännu en gång för att lägga
 112 till vägar och hastighetsbegränsningar mellan dem. Metoden skriver
 113 även ut felmeddelanden om filen 1) inte hittas, 2) inte kan läsas av
 114 någon annan anledning, 3) om det är något fel på innehållet i filen
 115 och vilket felet är, och 4) om någon av koordinaterna för någon nod
 116 inte kan tolkas som ett heltal. Programmet avslutas om något av
 117 ovanstående fel uppstår.
 118
 119 \section{Begränsningar}
 120 \section{Reflektioner}
 121 \section{Testkörningar}
 122 \section{Diskussion}
 123 * Angående att vi måste loopa igenom alla noder två gånger:
 124     Detta beror på att det inte går att lägga till en väg mellan en
 125     nod och en nod som inte ännu existerar i minnet. Detta skulle
 126     kanske kunnat lösas genom att man faktiskt skapar den nod som inte
 127     finns och lägger till information om nodens position när man
 128     kommer till de noderna senare när man kommer till den noden i
 129     DOM-dokumentet. Metoder hade då behövt skrivas för att sätta
 130     koordinaternas värden för en nod. Vi valde att gå igenom noderna
 131     två gånger i stället därför att det kändes lättast då vi skrev
 132     metoden.
 133
 134 \newpage
 135 \appendix
 136 \section{Källkod}
 137 \pagenumbering{roman}
 138
 139 \subsection{MySearcher.java}
 140 \begin{footnotesize}
 141   \verbatiminput{../src/MySearcher.java}
 142 \end{footnotesize}
 143
 144 \subsection{Graph.java}
 145 \begin{footnotesize}
 146   \verbatiminput{../src/Graph.java}
 147 \end{footnotesize}
 148
 149 \subsection{GraphNode.java}
 150 \begin{footnotesize}
 151   \verbatiminput{../src/GraphNode.java}
 152 \end{footnotesize}
 153
 154 \subsection{GraphTest.java}
 155 \begin{footnotesize}
 156   \verbatiminput{../test/GraphTest.java}
 157 \end{footnotesize}
 158
 159 \subsection{MySearcherTest.java}
 160 \begin{footnotesize}
 161   \verbatiminput{../test/MySearcherTest.java}
 162 \end{footnotesize}
 163 \end{document}