14 stable releases (6 major)
7.0.0 | Aug 18, 2024 |
---|---|
6.0.1 | Aug 3, 2024 |
5.0.0 | Aug 3, 2024 |
4.1.0 | Jul 29, 2024 |
1.0.0 | Jul 19, 2024 |
#470 in Algorithms
56KB
1.5K
SLoC
space-search
A library providing basic generic depth-first, breadth-first, heuristic-guided, and A* based search space exploration algorithms.
Implement Searchable
+ SolutionIdentifiable
to perform breadth-first or depth-first searching. Implement Scoreable
as well to perform heuristically guided search space exploration. Finally, additionally implement CostSearchable
to perform A* based search exploration. Pass them to Searcher
to create an iterator that will search for a solution.
Searcher
requires that you specify a Manager
type that determines the strategy, return result, and optimization of the search algorithm. Choose one of the searchers defined in the hierarchy of the search
module to fit your individual needs.
- Implement
Scoreable
to utilize theguided
search strategy based managers, which will prioritize searching states with a lower associated cost first. Additionally, implementCostSearchable
to make use of the A* based search managers in thea_star
module. If implementingScoreable
is too complex or unnecessary for your use case, then you may use theunguided
search managers, which explore the space naively in a depth-first or breadth-first manner, toggleable by a flag on the manager itself. - Use a
route
based manager to yield results consisting of the sequence of steps taken from the starting state to the ending state. Use ano_route
manager to just yield the solution state alone. Route based managers require that your state type implementClone
. - Implement
Eq
+std::hash::Hash
+Clone
for yourSearchable
type to benefit from prior explored state checking optimization using ahashable
manager; if youre unable to, then use anunhashable
manager, which does not require these additional bounds, but will likely explore the space much less efficiently unless cyclic traversal is not an inherent property of your search space.
When implementing Scoreable
, make sure that lower scoring states are closer to a solution.
use space_search::*;
use std::{vec, hash::Hash};
#[derive(Clone, Debug, PartialEq, Eq, Hash)]
struct Pos(i32, i32);
impl Searchable for Pos {
fn next_states(&self) -> impl Iterator<Item = Self> {
let &Pos(x, y) = self;
vec![
Pos(x - 1, y),
Pos(x, y - 1),
Pos(x + 1, y),
Pos(x, y + 1),
].into_iter()
}
}
impl SolutionIdentifiable for Pos {
fn is_solution(&self) -> bool {
let &Pos(x, y) = self;
x == 5 && y == 5
}
}
let mut searcher: Searcher<search::unguided::no_route::hashable::Manager<_>> = Searcher::new(Pos(0, 0));
assert_eq!(searcher.next(), Some(Pos(5, 5)));
Dependencies
~465KB