| Copyright | (c) Eric Mertens 2019-2021 |
|---|---|
| License | ISC |
| Maintainer | emertens@gmail.com |
| Safe Haskell | None |
| Language | Haskell2010 |
Advent.Search
Description
These implementations provide a lazily-generated list of visited states with the order defined by the search strategy.
Synopsis
- dfs :: Ord a => (a -> [a]) -> a -> [a]
- dfsOn :: Ord r => (a -> r) -> (a -> [a]) -> a -> [a]
- bfs :: Ord a => (a -> [a]) -> a -> [a]
- bfsOn :: Ord r => (a -> r) -> (a -> [a]) -> a -> [a]
- bfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
- bfsOnInt :: (a -> Int) -> (a -> [a]) -> a -> [a]
- astar :: Ord a => (a -> [AStep a]) -> a -> [(a, Int)]
- astarOn :: Ord b => (a -> b) -> (a -> [AStep a]) -> a -> [(a, Int)]
- data WithCost a = WC !Int a
- data AStep a = AStep {
- astepNext :: a
- astepCost :: !Int
- astepHeuristic :: !Int
Documentation
Arguments
| :: Ord r | |
| => (a -> r) | state characterization |
| -> (a -> [a]) | successors function |
| -> a | initial state |
| -> [a] | visited states in depth-first order |
Depth-first search.
Generates the list of unique visited states from a given starting state. States are unique up to the characterizing function.
Arguments
| :: Ord r | |
| => (a -> r) | representative function |
| -> (a -> [a]) | successor state generator |
| -> a | initial state |
| -> [a] | reachable states |
Enumerate the reachable states in breadth-first order given a successor state function and initial state.
States are compared for equality using the representative function. If the representatives are equal the state is considered already visited.
Arguments
| :: Ord r | |
| => (a -> r) | representative function |
| -> (a -> [a]) | successor state generator |
| -> [a] | initial states |
| -> [a] | reachable states |
Generalization of bfsOn allowing multiple
initial states to be considered.
Arguments
| :: Ord b | |
| => (a -> b) | state characterization |
| -> (a -> [AStep a]) | step function (new state, step cost, distance heuristic) |
| -> a | starting state |
| -> [(a, Int)] | list of states visited |
A* graph search producing a list of reached states and the minimum cost of reaching that state.
Returned states will be unique up to the characterization function. This allows extra information of a node to be ignored for the purposes of the search. For example, a node might remember the path used to reach it while for the search the particular path taken might not matter.
A step in the A* graph search annotated with its cost and an estimate of the distance remaining to the goal. The estimate must be an underapproximation to ensure the search finds the optimal solution