From 1d4d6ed846e27817cd9d655bb99421e97f89182f Mon Sep 17 00:00:00 2001 From: Victor Zamanian Date: Fri, 17 Oct 2008 17:29:17 +0200 Subject: [PATCH] Added greedySearch and aStar sections; fixed section title for setMap. --- rapport/rapport.tex | 28 +++++++++++++++++++++++----- 1 file changed, 23 insertions(+), 5 deletions(-) diff --git a/rapport/rapport.tex b/rapport/rapport.tex index c33e542..ed2ede1 100644 --- a/rapport/rapport.tex +++ b/rapport/rapport.tex @@ -67,10 +67,9 @@ \pagenumbering{arabic} \section{Problemspecifikation} -Denna laborationsrapport redovisar för hur en karta och olika -sökalgoritmer implementeras i programmeringsspråket Java. Huvudfokus i -rapporten ligger på analys och jämförelse mellan de olika -sökalgoritmerna. +Denna rapport redogör för hur en karta och olika sökalgoritmer +implementeras i programmeringsspråket Java. Huvudfokus i rapporten +ligger på analys och jämförelse mellan de olika sökalgoritmerna. Fyra algoritmer av två olika typer är implementerade. Bredden-först sökning och Djupet-först sökning är två oinformerade sökningar som @@ -99,7 +98,7 @@ vägen mellan noderna. \section{Metod- och Algoritmbeskrivning} -\subsection{\verb!public void setMap (File mapFile)!} +\subsection{setMap(File mapFile)} Denna metod läser in en karta i form av en XML-fil och representerar den i en graf. Implementationen av grafen är en modifierad version av Graph.java som vi använde i kursen Datastrukturer och Algoritmer. @@ -116,6 +115,25 @@ 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{greedySearch(String from, String to)} +Metoden \textit{greedySearch} utför en sökning efter en väg mellan +platserna \verb!from! och \verb!to! efter en ''girig'' algoritm. +Algoritmen börjar på den plats som \verb!from! representerar och +undersöker vilka noder den kan gå till i nästa steg. För dessa +noder undersöker den vilket steg som leder till att den färdas +geografiskt närmare målnoden \verb!to! och väljer detta. + +\subsection{aStar(String from, String to, boolean fastest)} +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), +annars söker den efter den kortaste vägen. Funktionen som bestämmer +vilken väg som ska tas i kartan beror på två saker: 1) hur långt den +nod man undersöker ligger från målnoden och 2a) hur långt man färdats +totalt från startnoden eller 2b) hur lång tid det tagit att färdats +från startnoden. + \section{Begränsningar} \section{Reflektioner} \section{Testkörningar} -- 2.11.4.GIT