Crate space_search

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 the guided search strategy based managers, which will prioritize searching states with a lower associated score first. Additionally, implement CostSearchable to make use of the A* based search managers in the a_star module. If implementing Scoreable is too complex or unnecessary for your use case, then you may use the unguided 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 a no_route manager to just yield the solution state alone. Route based managers require that your state type implement Clone.
• Implement Eq + std::hash::Hash + Clone for your Searchable type to benefit from prior explored state checking optimization using a hashable manager; if youre unable to, then use an unhashable 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;
        [
            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)));

Modules

search

Module containing all available search managers, organized into a feature-based hierarchy.

Structs

NoContext

Internal.

Searcher

State space exploration iterator.

StateCumulativeCost

Internal.

StateParent

Internal.

StateParentCumulativeCost

Internal.

Traits

CostSearchable

Trait for search space exploration guided by a cost function & heuristic.

ExplorationManager

Internal.

Scoreable

Trait for search space exploration guided by a heuristic.

Searchable

Basic trait for depth-first and breadth-first search space exploration.

SolutionIdentifiable

Trait that allows a state to be identified as a solution.