Safe Haskell | Safe |
---|---|
Language | Haskell2010 |
This module contains a collection of generalized graph search algorithms, for when you don't want to explicitly represent your data as a graph. The general idea is to provide these algorithms with a way of generating "next" states (and associated information), a way of determining when you have found a solution, a way of pruning out "dead ends", and an initial state.
- bfs :: Ord state => (state -> [state]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe [state]
- dfs :: Ord state => (state -> [state]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe [state]
- dijkstra :: (Num cost, Ord cost, Ord state) => (state -> [(cost, state)]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe (cost, [(cost, state)])
- aStar :: (Num cost, Ord cost, Ord state) => (state -> [(cost, cost, state)]) -> [state -> Bool] -> (state -> Bool) -> state -> Maybe (cost, [(cost, state)])
Documentation
:: Ord state | |
=> (state -> [state]) | Function to generate "next" states given a current state |
-> [state -> Bool] | List of ways to prune search. These are predicates which, if |
-> (state -> Bool) | Predicate to determine if solution found. |
-> state | Initial state |
-> Maybe [state] | First path found to a state matching the predicate, or |
bfs next prunes found initial
performs a breadth-first search over a set
of states, starting with initial
, generating neighboring states with
next
, and pruning out any state for which a function in prunes
returns
True
. It returns a path to a state for which found
returns True
.
Returns Nothing
if no path is possible.
Example: Making change problem
>>>
:{
countChange target = bfs add_one_coin [(> target)] (== target) 0 where add_one_coin amt = map (+ amt) coins coins = [25, 10, 5, 1] :}
>>>
countChange 67
Just [25,50,60,65,66,67]
:: Ord state | |
=> (state -> [state]) | Function to generate "next" states given a current state |
-> [state -> Bool] | List of ways to prune search. These are predicates which, if |
-> (state -> Bool) | Predicate to determine if solution found. |
-> state | Initial state |
-> Maybe [state] | First path found to a state matching the predicate, or |
dfs next prunes found initial
performs a depth-first search over a set
of states, starting with initial
, generating neighboring states with
next
, and pruning out any state for which a function in prunes
returns
True
. It returns a depth-first path to a state for which found
returns True
. Returns Nothing
if no path is possible.
Example: Simple directed graph search
>>>
import qualified Data.Map as Map
>>>
graph = Map.fromList [(1, [2, 3]), (2, [4]), (3, [4]), (4, [])]
>>>
dfs (graph Map.!) [] (== 4) 1
Just [3,4]
:: (Num cost, Ord cost, Ord state) | |
=> (state -> [(cost, state)]) | Function to generate list of incremental cost and neighboring states given the current state |
-> [state -> Bool] | List of ways to prune search. These are predicates which, if |
-> (state -> Bool) | Predicate to determine if solution found. |
-> state | Initial state |
-> Maybe (cost, [(cost, state)]) |
dijkstra next prunes found initial
performs a shortest-path search over
a set of states using Dijkstra's algorithm, starting with initial
,
generating neighboring states and their incremental costs with next
, and
pruning out any state for which a function in prunes
returns True
.
This will find the least-costly path from an initial state to a state for
which found
returns True
. Returns Nothing
if no path to a solved state
is possible.
Example: Making change problem, with a twist
>>>
:{
-- Twist: dimes have a face value of 10 cents, but are actually rare -- misprints which are worth 10 dollars countChange target = dijkstra add_one_coin [(> target)] (== target) 0 where add_one_coin amt = map (\(true_val, face_val) -> (true_val, face_val + amt)) coin_values coin_values = [(25, 25), (1000, 10), (5, 5), (1, 1)] :}
>>>
countChange 67
Just (67,[(1,1),(1,2),(5,7),(5,12),(5,17),(25,42),(25,67)])
:: (Num cost, Ord cost, Ord state) | |
=> (state -> [(cost, cost, state)]) | Function which, when given the current state, produces a list whose elements are (incremental cost to reach neighboring state, estimate on remaining cost from said state, said state). |
-> [state -> Bool] | List of ways to prune search. These are predicates which, if |
-> (state -> Bool) | Predicate to determine if solution found. |
-> state | Initial state |
-> Maybe (cost, [(cost, state)]) |
aStar next prunes found initial
performs a best-first search using
the A* search algorithm, starting with the state initial
, generating
neighboring states, their cost, and an estimate of the remaining cost with
next
, and pruning out any state for which a function in prunes
returns
True
. This returns a path to a state for which found
returns True
.
If the estimate is strictly a lower bound on the remaining cost to reach a
solved state, then the returned path is the shortest path. Returns
Nothing
if no path to a solved state is possible.
Example: Path finding in taxicab geometry
>>>
:{
neighbors (x, y) = [(x, y + 1), (x - 1, y), (x + 1, y), (x, y - 1)] dist (x1, y1) (x2, y2) = abs (y2 - y1) + abs (x2 - x1) nextTowards dest pos = map (\p -> (1, dist p dest, p)) (neighbors pos) :}
>>>
aStar (nextTowards (0, 2)) [(== (0, 1))] (== (0, 2)) (0, 0)
Just (4,[(1,(1,0)),(1,(1,1)),(1,(1,2)),(1,(0,2))])