Commits

Rhys !  committed 44df01f Draft Merge

merge in IDGBFS

  • Participants
  • Parent commits 34256bf, 04abd0d

Comments (0)

Files changed (2)

                , depthFirst
                , aStar
                , greedyBF
-               , search, iterativeDFS) where
+               , search, iterativeDFS, iterativeGBFS) where
 \end{code}
 
 Next, we import a few Haskell modules that contain some useful
       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
   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
 \section{Utility Definitions}
 \begin{itemize}
               , Path
               , SearchResult
               , actions
-              , search, iterativeDFS
+              , search, iterativeDFS, iterativeGBFS
               , aStar, breadthFirst, depthFirst, greedyBF )
 import NMPuzzle (NMPuzzle, expand, hTaxicab, mkPuzzle)
 
           , ("BFS", search . const breadthFirst)
           , ("GBFS", search . greedyBF . hTaxicab)
           , ("AS", search . aStar snd . hTaxicab)
-          , ("IDDFS", const (iterativeDFS snd)) ]
+          , ("IDDFS", const (iterativeDFS snd))
+          , ("IDGBFS", iterativeGBFS snd . hTaxicab) ]
 
 main :: IO ()
 main = do