| 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]
- dfsN :: Ord a => (a -> [a]) -> [a] -> [a]
- dfsOn :: Ord r => (a -> r) -> (a -> [a]) -> a -> [a]
- dfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
- bfs :: Ord a => (a -> [a]) -> a -> [a]
- bfsN :: Ord a => (a -> [a]) -> [a] -> [a]
- bfsOn :: Ord r => (a -> r) -> (a -> [a]) -> a -> [a]
- bfsOnN :: Ord r => (a -> r) -> (a -> [a]) -> [a] -> [a]
- data AStep a = AStep {
- astepNext :: a
- astepCost :: !Int
- astepHeuristic :: !Int
- astar :: Ord a => (a -> [AStep a]) -> a -> [(a, Int)]
- astarN :: Ord a => (a -> [AStep a]) -> [a] -> [(a, Int)]
- astarOn :: Ord b => (a -> b) -> (a -> [AStep a]) -> a -> [(a, Int)]
- astarOnN :: Ord b => (a -> b) -> (a -> [AStep a]) -> [a] -> [(a, Int)]
Depth-first search
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) | state characterization |
| -> (a -> [a]) | successors function |
| -> [a] | initial states |
| -> [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.
Breadth-first search
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.
A* search
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
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.