【Rust】BFS（幅優先探索）のクレートがあった

適当にRustのクレート見て回ってたらBFSのクレートがあってお？ってなったので眺めてみた。

docs.rs

以下の形式で、

pub fn bfs<N, FN, IN, FS>(
    start: &N,
    successors: FN,
    success: FS,
) -> Option<Vec<N>>
where
    N: Eq + Hash + Clone,
    FN: FnMut(&N) -> IN,
    IN: IntoIterator<Item = N>,
    FS: FnMut(&N) -> bool,

開始点（start）と、現在いるノードからの到達可能先（successors）と、ゴールかどうかチェックする関数（success ）を渡すことで、BFSによりスタートからゴールまで辿り着けるか探索し、結果の経路をOptionのベクタ型で返してくれるものらしい。

上記サイトに載っているチェスの例を、少し書き換えたもの（main関数などの追加）を以下に載せる。

use pathfinding::prelude::bfs;

#[derive(Clone, Debug, Eq, Hash, Ord, PartialEq, PartialOrd)]
struct Pos(i32, i32);

impl Pos {
    fn successors(&self) -> Vec<Pos> {
        let &Pos(x, y) = self;
        vec![
            Pos(x + 1, y + 2),
            Pos(x + 1, y - 2),
            Pos(x - 1, y + 2),
            Pos(x - 1, y - 2),
            Pos(x + 2, y + 1),
            Pos(x + 2, y - 1),
            Pos(x - 2, y + 1),
            Pos(x - 2, y - 1),
        ]
    }
}

fn main() {
    static GOAL: Pos = Pos(4, 6);
    let result = bfs(&Pos(1, 1), |p| p.successors(), |p| *p == GOAL);
    println!("{:?}", result);
}

チェス盤をイメージしたときに、スタート地点（1, 1）から、ゴール地点（4, 6）のマスに、Knightの動き（将棋でいうとこの桂馬の全方位可能版みたいなの）で辿り着けるかを判定するプログラムになっている。

bfsの第一引数にスタート地点を指定し、第二引数には、Knightが動ける場所をPos#successorsで指定している。第三引数は、ゴールに辿り着いたかをboolで返す関数を指定している。

これを実行すると、以下の結果となる。

Some([Pos(1, 1), Pos(2, 3), Pos(3, 5), Pos(2, 7), Pos(4, 6)])

今回のケースだと、（1, 1）から（4, 6）は辿り着けるので、その経路が得られている。

実際には盤外などの処置も必要だと思うが、中々面白そうなのでクレートのソースも今度見てみる。

ちなみに上記の出力結果を図にするとこんな感じ（KがKnightの位置）。

スタート（1, 1）

1手目（2, 3）

2手目（3, 5）

3手目（2, 7）

ゴール（4, 6）