Commits

Rhys ! committed 04abd0d Draft

updated documentation and CLI name for IDGBFS

  • Participants
  • Parent commits faf59d4

Comments (0)

Files changed (2)

       go procCount [] = (procCount, Nothing)
 \end{code}
 
-\section{Search Methods}\label{methods}\todo[inline]{Custom strategies.}
+\section{Search Methods}\label{methods}
 The difference between the search methods implemented is in how they order the
 frontier\footnote{The frontier is the list of nodes yet to be examined.}, and
 thus the order of node examination. In this implementation, search methods are
     f (Path (at:_) (qt:_)) = h qt + g at
 \end{code}
 
-\subsection{Iterative Deepening DFS}
-Iterative deepening DFS is a depth-first search where the maximum depth of the
-DFS is increased each run until the shallowest goal state is found \cite{iddfs}.
-It is equivalent to breadth-first search in that it will find the optimal
-solution, but it trades a smaller memory footprint for a longer run time.
+\subsection{Iterative Deepening Methods}
+Iterative deepening search is a search method where the maximum depth of the
+search is increased each run until the shallowest goal state is found
+\cite{iddfs}. For a DFS, tt is equivalent to breadth-first search in that it
+will find the optimal solution, but it trades a smaller memory footprint for a
+longer run time.
 
 To start, a function for limiting the depth of an arbitrary |FrontierApp| is
 defined. The function takes a parameter |da| that extracts the depth from the
   q ->
   SearchResult a q
 iterativeDFS da = iterativeSearch (limitApp depthFirst da)
+\end{code}
 
+Similarly, we can define an iterative greedy best-first search |iterativeGBFS|,
+which also takes a $h(n)$ heuristic function. Unlike normal GBFS, this method
+will find the optimal path.\footnote{It should be noted that testing has
+determined that this method is significantly inferior to both GBFS and iterative
+deepening DFS in time performance. It is left in as a curiosity.}
+
+\begin{code}
+iterativeGBFS :: (Eq q, Ord m, Num m, Ord mh, Num mh) =>
+  (a -> m) ->
+  (q -> mh) ->
+  (Path a q -> [Path a q]) ->
+  (q -> Bool) ->
+  q ->
+  SearchResult a q
 iterativeGBFS da h = iterativeSearch (limitApp (greedyBF h) da)
 \end{code}
 \appendix
           , ("GBFS", search . greedyBF . hTaxicab)
           , ("AS", search . aStar snd . hTaxicab)
           , ("IDDFS", const (iterativeDFS snd))
-          , ("IGBFS", iterativeGBFS snd . hTaxicab) ]
+          , ("IDGBFS", iterativeGBFS snd . hTaxicab) ]
 
 main :: IO ()
 main = do