Crate space_search

space-search

A library providing basic utilities for performing generic depth-first, breadth-first, and heuristic-guided search space exploration algorithms.

Implement Searchable to perform breadth-first or depth-first searching, and implement ScoredSearchable to perform heuristically guided search space exploration. Pass them to the Searcher and ScoredSearcher structs respectively to create iterators that will search the space for a solution.

Implement Eq + Hash + Clone for your search space state type to benefit from prior explored state checking optimization; if youre unable to, then use the ScoredSearcher or ScoredUnhashableSearcher iterators, which do not require these additional bounds, but will likely explore the space much less efficiently.

When implementing ScoredSearcher, make sure that higher 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 {
    type NextMoveIterator = vec::IntoIter<Pos>;

    fn next_states(&self) -> Self::NextMoveIterator {
        let &Pos(x, y) = self;
        vec![
            Pos(x - 1, y),
            Pos(x, y - 1),
            Pos(x + 1, y),
            Pos(x, y + 1),
        ].into_iter()
    }

    fn is_solution(&self) -> bool {
        let &Pos(x, y) = self;
        x == 5 && y == 5
    }
}

let mut searcher = Searcher::new(Pos(0, 0));
assert_eq!(searcher.next(), Some(Pos(5, 5)));

Structs

• ScoredSearcher
  Optimized heuristic-guided search space exploration iterator.
• ScoredUnhashableSearcher
  Unoptimized heuristic-guided search space exploration iterator.
• Searcher
  Optimized breadth-first / depth-first state space exploration iterator.
• UnhashableSearcher
  Unoptimized breadth-first / depth-first search space exploration iterator.

Traits

• ScoredSearchable
  Trait for search space exploration guided by a heuristic.
• Searchable
  Basic trait for depth-first and breadth-first search space exploration.