c++20 实现bp搜索

BP搜索（双向广搜）是一种搜索算法，它从起点和终点同时开始搜索，直到两个搜索路径相交为止。C++20中可以使用std::bidirectional_iterator_tag来实现BP搜索。

以下是一个简单的C++20实现BP搜索的示例代码：

#include <iostream>
#include <vector>
#include <queue>
#include <unordered_set>
#include <algorithm>

template<typename State>
struct BfsState {
    State state;
    int depth;
    bool forward;
};

template<typename State>
struct BfsStateHash {
    std::size_t operator()(const BfsState<State>& s) const {
        std::size_t h = std::hash<State>()(s.state);
        h ^= std::hash<int>()(s.depth) + 0x9e3779b9 + (h << 6) + (h >> 2);
        h ^= std::hash<bool>()(s.forward) + 0x9e3779b9 + (h << 6) + (h >> 2);
        return h;
    }
};

template<typename State, typename Action>
class BidirectionalBfs {
public:
    BidirectionalBfs(const State& start, const State& goal, const Action& action)
        : start_(start), goal_(goal), action_(action) {}

    std::vector<State> search() const {
        std::queue<BfsState<State>> q1, q2;
        std::unordered_set<BfsState<State>, BfsStateHash<State>> visited1, visited2;

        q1.push(BfsState<State>{start_, 0, true});
        q2.push(BfsState<State>{goal_, 0, false});

        visited1.insert(BfsState<State>{start_, 0, true});
        visited2.insert(BfsState<State>{goal_, 0, false});

        while (!q1.empty() && !q2.empty()) {
            if (q1.size() > q2.size()) {
                std::swap(q1, q2);
                std::swap(visited1, visited2);
            }

            auto [state, depth, forward] = q1.front();
            q1.pop();

            for (const auto& action : action_(state)) {
                auto next_state = action.next_state;
                auto next_depth = depth + 1;
                auto next_forward = forward;

                auto bfs_state = BfsState<State>{next_state, next_depth, next_forward};
                if (visited1.count(bfs_state) || visited2.count(bfs_state)) {
                    continue;
                }

                if (visited2.count(BfsState<State>{next_state, 0, !next_forward})) {
                    auto path1 = get_path(bfs_state, visited1);
                    auto path2 = get_path(BfsState<State>{next_state, 0, !next_forward}, visited2);
                    path2.pop_back();
                    path1.insert(path1.end(), path2.rbegin(), path2.rend());
                    return path1;
                }

                visited1.insert(bfs_state);
                q1.push(bfs_state);
            }
        }

        return {};
    }

private:
    std::vector<State> get_path(const BfsState<State>& state, const std::unordered_set<BfsState<State>, BfsStateHash<State>>& visited) const {
        std::vector<State> path;
        auto bfs_state = state;
        while (true) {
            path.push_back(bfs_state.state);
            if (bfs_state.depth == 0) {
                break;
            }
            auto prev_depth = bfs_state.depth - 1;
            auto prev_forward = !bfs_state.forward;
            bfs_state = *visited.find(BfsState<State>{bfs_state.state, prev_depth, prev_forward});
        }
        std::reverse(path.begin(), path.end());
        return path;
    }

    State start_;
    State goal_;
    Action action_;
};

// Example usage:
struct Node {
    int x, y;
};

struct Action {
    std::vector<Node> next_state(const Node& node) const {
        std::vector<Node> next_states;
        next_states.push_back({node.x + 1, node.y});
        next_states.push_back({node.x - 1, node.y});
        next_states.push_back({node.x, node.y + 1});
        next_states.push_back({node.x, node.y - 1});
        return next_states;
    }
};

int main() {
    Node start{0, 0};
    Node goal{10, 10};
    auto bfs = BidirectionalBfs<Node, Action>{start, goal, Action{}};
    auto path = bfs.search();
    if (path.empty()) {
        std::cout << "No path found.\n";
    } else {
        std::cout << "Path found:\n";
        for (const auto& node : path) {
            std::cout << "(" << node.x << ", " << node.y << ")\n";
        }
    }
    return 0;
}

该示例代码使用了一个Node结构体表示搜索状态，Action结构体表示搜索状态的转移，BidirectionalBfs类实现了BP搜索算法。在main函数中，我们将起点和终点分别设置为(0,0)和(10,10)，然后调用BidirectionalBfs的search函数搜索路径。如果找到了路径，则输出路径上的节点坐标。否则，输出“未找到路径”。