読者です 読者をやめる 読者になる 読者になる

Boost.Graph A*アルゴリズムで最短経路

C++

まだよく理解しないで書いてるので、あまり参考にはしないでください。
edge weightとcost両方が必要なあたりがよくわからない。ヒューリスティック関数の実装むずかしい。

#include <iostream>
#include <string>
#include <utility>
#include <boost/graph/adjacency_list.hpp>
#include <boost/graph/astar_search.hpp>
 
using Graph = boost::adjacency_list<boost::listS, boost::vecS, boost::directedS,
                                    boost::no_property, boost::property<boost::edge_weight_t, int>>;
using Edge = std::pair<int, int>;
enum { A, B, C, D, E, N };
const std::string Names = "ABCDE";
 
Graph make_graph()
{
    const std::vector<Edge> edges = {
        {A, B}, {A, C}, {A, D},
        {B, E}, {C, E}, {D, E}
    };
    const std::vector<int> weights = {
        3, 1, 4, 5, 2, 6
    };
    return Graph(edges.begin(), edges.end(), weights.begin(), N);
}
 
// ヒューリスティック関数
template <class Graph, class CostType>
class distance_heuristic : public boost::astar_heuristic<Graph, CostType> {
public:
    using Vertex = typename boost::graph_traits<Graph>::vertex_descriptor;
 
    distance_heuristic(Vertex goal, Graph& g)
        : goal_(goal), graph_(g) {}
 
    CostType operator()(Vertex u) const
    {
        // てきとうなコスト計算。
        // 頂点番号の比較をしてるだけ。
        return get(boost::vertex_index, graph_, goal_) - get(boost::vertex_index, graph_, u);
    }
 
private:
    Vertex goal_;
    Graph& graph_;
};
 
struct found_goal {};
 
template <class Vertex>
class astar_goal_visitor : public boost::default_astar_visitor
{
public:
    astar_goal_visitor(Vertex goal) : m_goal(goal) {}
 
    // 頂点を調べる
    template <class Graph>
    void examine_vertex(Vertex u, Graph&)
    {
        if (u == m_goal) // ゴールが見つかった
            throw found_goal();
    }
private:
    Vertex m_goal;
};
 
int main()
{
    Graph g = make_graph();
 
    using Vertex = boost::graph_traits<Graph>::vertex_descriptor;
    using Cost = int;
 
    Vertex start = vertex(A, g);
    Vertex goal = vertex(E, g);
 
    std::vector<Vertex> parents(boost::num_vertices(g));
    std::vector<Cost> distances(boost::num_vertices(g));
 
    try {
        boost::astar_search_tree(g, start,
           distance_heuristic<Graph, Cost>(goal, g),
           boost::predecessor_map(&parents[0]).
           distance_map(&distances[0]).
           visitor(astar_goal_visitor<Vertex>(goal)));
    }
    catch (found_goal fg) {
        // 経路なし
        if (parents[goal] == goal) {
            std::cout << "no path" << std::endl;
            return 1;
        }
 
        // 最短経路の頂点リストを作成
        std::deque<Vertex> route;
        for (Vertex v = goal; v != start; v = parents[v]) {
            route.push_front(v);
        }
        route.push_front(start);
 
        // 最短経路を出力
        for (const Vertex v : route) {
            std::cout << Names[v] << std::endl;
        }
    }
}
A
C
E