From 3637267e788507529fa67c2b1e05966920e54f09 Mon Sep 17 00:00:00 2001 From: Anton Johansson Date: Mon, 20 Oct 2008 12:52:41 +0200 Subject: [PATCH] Added comments on section and some other stuff --- rapport/rapport.tex | 208 ++++++++++++++++++++++++++++++---------------------- 1 file changed, 121 insertions(+), 87 deletions(-) diff --git a/rapport/rapport.tex b/rapport/rapport.tex index b49014f..0ed1090 100644 --- a/rapport/rapport.tex +++ b/rapport/rapport.tex @@ -83,12 +83,32 @@ Labbspecifikation finns att läsa på:\\ \verb!http://www.cs.umu.se/kurser/5DV063/HT08/lab2.html! \section{Användarhandledning} -Programmet körs från dit06***/ait/lab2, där *** är antingen ''ajn'' -eller ''vzy'', genom att ange följande kommando: +Programmet körs från dit06vzy/edu/ai/lab2 med följande kommando: +\begin{footnotesize} +\verb!java -cp lib/jdom.jar:bin/prod SearchInterface MySearcher \! \\ +\verb! [startnod [slutnod]]! +\end{footnotesize} + +Där \verb!! ska hänvisa till en karta sparad i +xml-format enligt följande utseende: + +\begin{footnotesize} \begin{verbatim} -java -cp lib/jdom.jar:bin/prod SearchInterface MySearcher [startnod [slutnod]] + + + + + + + ... + \end{verbatim} +\end{footnotesize} + +Metoden som ska angivas, \verb!!, är \verb!B! för bredden +först, \verb!D! för djupet först, \verb!Ad! för $A^*$ kortaste vägen och +\verb!At! för $A^*$ snabbaste vägen. Om varken startnod eller slutnod anges efterfrågas de av programmet. Om en (1) nod anges som parameter antas den vara startnod @@ -96,7 +116,7 @@ och då efterfrågas bara slutnod av programmet. Annars, om både startnod och slutnod anges körs vald metod (algoritm) för att hitta vägen mellan noderna. -\section{Metod- och Algoritmbeskrivning} +\section{Algoritmbeskrivning} \subsection{setMap(File mapFile)} Denna metod läser in en karta i form av en XML-fil och representerar @@ -115,6 +135,19 @@ och vilket felet är, och 4) om någon av koordinaterna för någon nod inte kan tolkas som ett heltal. Programmet avslutas om något av ovanstående fel uppstår. +\subsection{Graph.java} +Klassen Graph används för att abstrahera och spara undan alla noder i +kartan. Klassen innehåller en Hashtabell där Kartans namn på noder +sparas som nyckel och själva noden av typ GraphNode sparas som +värde. Metoderna som används mest i denna implementation är de för att +sätta in noder och kanter mellan noderna. + +\subsection{GraphNode.java} +Klassen GraphNode används för att spara undan städerna ur +kartan. GraphNode har en Hashtabell som sparar länkar till sina +grannar som nycklar och vikten som värde. + + \subsection{Oinformerade sökalgoritmer} Följande sökalgoritmer tar emot två parametrar, \textit{from} och \textit{to} som anger från vilken nod i grafen algoritmen ska börja @@ -177,7 +210,7 @@ noder undersöker den vilket steg som leder till att den färdas geografiskt närmare målnoden \verb!to! och väljer detta. \subsubsection{aStar(String from, String to, boolean fastest)} -Algoritmen A* (uttalas ''A-sjärna'') fungerar ungefär som +Algoritmen $A^*$ (uttalas ''A-sjärna'') fungerar ungefär som \textit{greedySearch} men den använder ett annat sätt att välja vägen som den ska ta. Om parametern \verb!fastest! har värdet \verb!true! söker algoritmen efter den snabbaste vägen (som namnet antyder), @@ -188,183 +221,184 @@ totalt från startnoden eller 2b) hur lång tid det tagit att färdats från startnoden. \section{Begränsningar} +% Vilka problem och begränsningar har vår lösning + \section{Reflektioner} +% Vad var krångligt, hur löste vi det. Allmänna synpunkter. + \section{Testkörningar} +% Redogör för sökalgoritmernas för- och nackdelar, samt hur de +% presterade på den givna uppgiften -\subsection{Test Breadthfirst} +\subsection{Test Bredden-först} \subsubsection{From: Tegsbron to Nydala} -\textbf{All visited nodes:} -Tegsbron, I20, Teg, Station, Obs, Rondellen, Obs, Gamlia, Foa, -Begbilar, TreKorvar, Kyrkan, Foa, Begbilar, NUS, Berghem, Mariehem, -Begbilar, On, Flygplatsen, NUS, Mariehem, Sofiehem, Mariehem, MIT, -Nydala +\textbf{All expanded nodes:} +Tegsbron, Teg, I20, Rondellen, Station, Obs, TreKorvar, Kyrkan, Gamlia, Foa, Begbilar, On, Flygplatsen, NUS, Berghem, Mariehem, Sofiehem, MIT, Nydala \textbf{Path to goal:} -Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala +Tegsbron, I20, Obs, Foa, Mariehem, Nydala \subsubsection{From: Flygplatsen to Begbilar} -\textbf{All visited nodes:} -Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, Station, NUS, -Tegsbron, I20, Obs, Gamlia, Sofiehem, Gamlia, I20, Obs, Foa, Begbilar +\textbf{All expanded nodes:} +Flygplatsen, TreKorvar, On, Rondellen, Teg, Kyrkan, Tegsbron, NUS, Station, I20, Gamlia, Sofiehem, Obs, Berghem, Alidhem, GimonAs, Foa, Begbilar -\textbf{Path to goal:} Flygplatsen, TreKorvar, Rondellen, Teg, -Tegsbron, I20, Obs, Foa, Begbilar +\textbf{Path to goal:} +Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar \subsubsection{From: MIT to Flygplatsen} -\textbf{All visited nodes:} MIT, Nydala, Alidhem, Berghem, Ok, -Mariehem, Ok, Sofiehem, Mariehem, Gamlia, Foa, GimonAs, NUS, Foa, NUS, -Station, Obs, Begbilar, Kyrkan, Obs, Begbilar, Kyrkan, Obs, I20, -Begbilar, I20, Rondellen, I20, Rondellen, I20, Tegsbron, Tegsbron, -Teg, TreKorvar, Tegsbron, Teg, TreKorvar, Tegsbron, Teg, Teg, -Flygplatsen +\textbf{All expanded nodes:} +MIT, Berghem, Alidhem, Nydala, Gamlia, Mariehem, Sofiehem, Ok, NUS, Station, Foa, GimonAs, Kyrkan, Obs, I20, Begbilar, Rondellen, Tegsbron, TreKorvar, Teg, Flygplatsen -\textbf{Path to goal:} MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, -TreKorvar, Flygplatsen +\textbf{Path to goal:} +MIT, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen \subsubsection{From: Nydala to Gamlia} -\textbf{All visited nodes:} Nydala, Mariehem, MIT, Ok, Berghem, Foa, -Berghem, Alidhem, Alidhem, Gamlia +\textbf{All expanded nodes:} +Nydala, Ok, MIT, Mariehem, Alidhem, Berghem, Foa, Sofiehem, Gamlia -\textbf{Path to goal:} Nydala, MIT, Berghem, Gamlia +\textbf{Path to goal:} +Nydala, MIT, Berghem, Gamlia \subsubsection{From: Teg to Foa} -\textbf{All visited nodes:} Teg, Tegsbron, Rondellen, I20, TreKorvar, -Kyrkan, Obs, Station, Flygplatsen, On, Station, NUS, Foa +\textbf{All expanded nodes:} +Teg, Tegsbron, Rondellen, I20, Kyrkan, TreKorvar, Station, Obs, NUS, Flygplatsen, On, Gamlia, Foa -\textbf{Path to goal:} Teg, Tegsbron, I20, Obs, Foa +\textbf{Path to goal:} +Teg, Tegsbron, I20, Obs, Foa -\subsection{Test Depthfirst} +\subsection{Test Djupet-först} \subsubsection{From: Tegsbron to Nydala} -\textbf{All visited nodes:} Tegsbron, Teg, Rondellen, TreKorvar, On, -Flygplatsen, Kyrkan, Station, Obs, Foa, Begbilar, Mariehem, Berghem, -MIT, Alidhem, Ok, Nydala +\textbf{All expanded nodes:} +Tegsbron, Teg, Rondellen, Kyrkan, Station, Obs, Begbilar, Foa, Mariehem, Berghem, MIT, Alidhem, Sofiehem, GimonAs, Ok, Nydala -\textbf{Path to goal:} Tegsbron, Teg, Rondellen, Kyrkan, Station, Obs, -Foa, Mariehem, Berghem, MIT, Alidhem, Ok, Nydala +\textbf{Path to goal:} +Tegsbron, Teg, Rondellen, Kyrkan, Station, Obs, Foa, Mariehem, Nydala \subsubsection{From: Flygplatsen to Begbilar} -\textbf{All visited nodes:} Flygplatsen, TreKorvar, Rondellen, Teg, -Tegsbron, I20, Obs, Foa, Mariehem, Nydala, MIT, Alidhem, Sofiehem, -NUS, Kyrkan, Station, Gamlia, Berghem, Gamlia, GimonAs, Ok, Ok, -Berghem, Ok, Berghem, Begbilar +\textbf{All expanded nodes:} +Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar -\textbf{Path to goal:} Flygplatsen, TreKorvar, Rondellen, Teg, -Tegsbron, I20, Obs, Foa, Begbilar +\textbf{Path to goal:} +Flygplatsen, TreKorvar, Rondellen, Teg, Tegsbron, I20, Obs, Begbilar \subsubsection{From: MIT to Flygplatsen} -\textbf{All visited nodes:} MIT, Alidhem, Sofiehem, GimonAs, Ok, -Nydala, Mariehem, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, -Flygplatsen +\textbf{All expanded nodes:} +MIT, Alidhem, Sofiehem, GimonAs, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, On, Flygplatsen -\textbf{Path to goal:} MIT, Alidhem, Sofiehem, GimonAs, Ok, Nydala, -Mariehem, Berghem, Gamlia, NUS, Kyrkan, Rondellen, TreKorvar, -Flygplatsen +\textbf{Path to goal:} +MIT, Alidhem, Sofiehem, NUS, Gamlia, Station, I20, Tegsbron, Teg, Rondellen, TreKorvar, Flygplatsen \subsubsection{From: Nydala to Gamlia} -\textbf{All visited nodes:} Nydala, Ok, Alidhem, Sofiehem, NUS, Gamlia +\textbf{All expanded nodes:} +Nydala, Ok, Alidhem, Sofiehem, GimonAs, NUS, Gamlia -\textbf{Path to goal:} Nydala, Ok, Alidhem, Sofiehem, NUS, Gamlia +\textbf{Path to goal:} +Nydala, Ok, Alidhem, Sofiehem, NUS, Gamlia \subsubsection{From: Teg to Foa} -\textbf{All visited nodes:} Teg, Tegsbron, I20, Obs, Foa +\textbf{All expanded nodes:} +Teg, Rondellen, TreKorvar, Flygplatsen, On, Kyrkan, Station, Obs, Begbilar, Foa -\textbf{Path to goal:} Teg, Tegsbron, I20, Obs, Foa +\textbf{Path to goal:} +Teg, Rondellen, Kyrkan, Station, Obs, Foa -\subsection{Test A*} +\subsection{Test $A^*$} \subsubsection{From: Tegsbron to Nydala} -\textbf{All visited nodes:} Tegsbron, I20, Teg, Station, Gamlia, -Rondellen, Obs, Berghem, NUS, Kyrkan, TreKorvar, MIT, Nydala +\textbf{All expanded nodes:} +Tegsbron, I20, Teg, Station, Obs, Rondellen, Gamlia, Berghem, NUS, Kyrkan, TreKorvar, MIT, Nydala -\textbf{Path to goal:} Tegsbron, I20, Station, Gamlia, Berghem, MIT, -Nydala +\textbf{Path to goal:} +Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala \subsubsection{From: Flygplatsen to Begbilar} -\textbf{All visited nodes:} Flygplatsen, TreKorvar, On, Rondellen, -Kyrkan, Teg, Station, NUS, Tegsbron, Obs, Begbilar +\textbf{All expanded nodes:} +Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Teg, Station, NUS, Tegsbron, Obs, Begbilar -\textbf{Path to goal:} Flygplatsen, TreKorvar, Rondellen, Kyrkan, -Station, Obs, Begbilar +\textbf{Path to goal:} +Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar \subsubsection{From: MIT to Flygplatsen} -\textbf{All visited nodes:} MIT, Alidhem, Berghem, Sofiehem, Nydala, -GimonAs, Gamlia, NUS, Ok, Mariehem, Station, Kyrkan, Rondellen, I20, -TreKorvar, Flygplatsen +\textbf{All expanded nodes:} +MIT, Alidhem, Berghem, Sofiehem, Nydala, GimonAs, Gamlia, NUS, Ok, Mariehem, Station, Kyrkan, Rondellen, I20, TreKorvar, Flygplatsen -\textbf{Path to goal:} MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, -TreKorvar, Flygplatsen +\textbf{Path to goal:} +MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen \subsubsection{From: Nydala to Gamlia} -\textbf{All visited nodes:} Nydala, MIT, Berghem, Gamlia +\textbf{All expanded nodes:} +Nydala, MIT, Berghem, Gamlia -\textbf{Path to goal:} Nydala, MIT, Berghem, Gamlia +\textbf{Path to goal:} +Nydala, MIT, Berghem, Gamlia \subsubsection{From: Teg to Foa} -\textbf{All visited nodes:} Teg, Tegsbron, Rondellen, I20, Kyrkan, -TreKorvar, Obs, Foa +\textbf{All expanded nodes:} +Teg, Tegsbron, Rondellen, I20, Kyrkan, TreKorvar, Obs, Foa -\textbf{Path to goal:} Teg, Tegsbron, I20, Obs, Foa +\textbf{Path to goal:} +Teg, Tegsbron, I20, Obs, Foa -\subsection{Test GreedySearch} +\subsection{Test Girig sökning} \subsubsection{From: Tegsbron to Nydala} -\textbf{All visited nodes:} Tegsbron, I20, Station, Gamlia, Berghem, -MIT, Nydala +\textbf{All expanded nodes:} +Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala -\textbf{Path to goal:} Tegsbron, I20, Station, Gamlia, Berghem, MIT, -Nydala +\textbf{Path to goal:} +Tegsbron, I20, Station, Gamlia, Berghem, MIT, Nydala \subsubsection{From: Flygplatsen to Begbilar} -\textbf{All visited nodes:} Flygplatsen, TreKorvar, On, Rondellen, -Kyrkan, Station, Obs, Begbilar +\textbf{All expanded nodes:} +Flygplatsen, TreKorvar, On, Rondellen, Kyrkan, Station, Obs, Begbilar -\textbf{Path to goal:} Flygplatsen, TreKorvar, Rondellen, Kyrkan, -Station, Obs, Begbilar +\textbf{Path to goal:} +Flygplatsen, TreKorvar, Rondellen, Kyrkan, Station, Obs, Begbilar \subsubsection{From: MIT to Flygplatsen} -\textbf{All visited nodes:} MIT, Alidhem, Sofiehem, GimonAs, NUS, -Kyrkan, Rondellen, TreKorvar, Flygplatsen +\textbf{All expanded nodes:} +MIT, Alidhem, Sofiehem, GimonAs, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen -\textbf{Path to goal:} MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, -TreKorvar, Flygplatsen +\textbf{Path to goal:} +MIT, Alidhem, Sofiehem, NUS, Kyrkan, Rondellen, TreKorvar, Flygplatsen \subsubsection{From: Nydala to Gamlia} -\textbf{All visited nodes:} +\textbf{All expanded nodes:} Nydala, MIT, Berghem, Gamlia @@ -373,7 +407,7 @@ Nydala, MIT, Berghem, Gamlia \subsubsection{From: Teg to Foa} -\textbf{All visited nodes:} +\textbf{All expanded nodes:} Teg, Tegsbron, I20, Obs, Foa -- 2.11.4.GIT