space-search

提供基本的通用深度优先、广度优先、启发式引导和基于A*的搜索空间探索算法的库。

实现Searchable + SolutionIdentifiable以执行广度优先或深度优先搜索。同时实现Scoreable以执行启发式引导的搜索空间探索。最后，额外实现CostSearchable以执行基于A*的搜索探索。将它们传递给Searcher以创建一个搜索解决方案的迭代器。

Searcher需要您指定一个Manager类型，该类型确定搜索策略、返回结果和搜索算法的优化。从search模块的层次结构中选择一个搜索器以适应您的特定需求。

• 实现Scoreable以利用基于guided的搜索策略管理器，这些管理器将优先搜索关联成本较低的状态。此外，实现CostSearchable以使用a_star模块中的基于A*的搜索管理器。如果实现Scoreable过于复杂或对于您的用例不必要，则可以使用unguided搜索管理器，这些管理器将以深度优先或广度优先的方式盲目地探索空间，可以通过管理器上的标志进行切换。
• 使用基于route的管理器以产生从起始状态到结束状态的步骤序列的结果。使用no_route管理器仅产生解决方案状态。基于路线的管理器要求您的状态类型实现Clone。
• 为您的Searchable类型实现Eq + std::hash::Hash + Clone，以利用使用hashable管理器的先前探索状态检查优化；如果您无法这样做，则使用unhashable管理器，它不需要这些额外的限制，但除非循环遍历是您搜索空间的一个固有属性，否则可能会以效率较低的方式探索空间。

在实现Scoreable时，请确保得分较低的州更接近解决方案。

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)));