3

我正在阅读 boost::graph 文档以备将来使用。我对 A* 算法特别感兴趣。

看一下 boost::graph::astar_search 使用示例，似乎停止算法的方法是抛出异常并将其捕获到算法之外。

由于我不想抛出任何异常，导致 C++ 中的异常处理非常复杂且效率不高，我想知道 boost::graph 是否提出了另一种在达到目标时停止算法的方法。

有没有人有一个不使用任何异常的替代示例？

4

1 回答 1

5

根据常见问题解答，提前退出 BFS 的唯一方法是抛出异常并“查看 boost 邮件列表了解详细信息”，但我从未找到此类详细信息。

要在 A* 中不使用异常，您必须修改算法并使用停止条件介绍您自己的访问者：

#include <boost/graph/astar_search.hpp>


namespace boost { namespace graph {

template < class Visitors = null_visitor >
struct stopable_astar_visitor : public astar_visitor<Visitors> {
    stopable_astar_visitor() {}
    stopable_astar_visitor(Visitors vis) : astar_visitor<Visitors>(vis) {}

    template < class Vertex, class Graph >
    bool should_stop(Vertex &v, Graph &g) {
        return true;
    }
};

template <typename VertexListGraph, typename AStarHeuristic,
          typename AStarVisitor, typename PredecessorMap,
          typename CostMap, typename DistanceMap,
          typename WeightMap,
          typename CompareFunction, typename CombineFunction,
          typename CostZero>
inline void
stoppable_astar_search_no_init_tree
  (const VertexListGraph &g,
   typename graph_traits<VertexListGraph>::vertex_descriptor s,
   AStarHeuristic h, AStarVisitor vis,
   PredecessorMap predecessor, CostMap cost,
   DistanceMap distance, WeightMap weight,
   CompareFunction compare, CombineFunction combine,
   CostZero zero)
{
  typedef typename graph_traits<VertexListGraph>::vertex_descriptor
    Vertex;
  typedef typename property_traits<DistanceMap>::value_type Distance;
  typedef d_ary_heap_indirect<
            std::pair<Distance, Vertex>,
            4,
            null_property_map<std::pair<Distance, Vertex>, std::size_t>,
            function_property_map<graph_detail::select1st<Distance, Vertex>, std::pair<Distance, Vertex> >,
            CompareFunction>
    MutableQueue;
  MutableQueue Q(
    make_function_property_map<std::pair<Distance, Vertex> >(graph_detail::select1st<Distance, Vertex>()),
    null_property_map<std::pair<Distance, Vertex>, std::size_t>(),
    compare);
    int counter = 0;
  vis.discover_vertex(s, g);
  Q.push(std::make_pair(get(cost, s), s));
  while (!Q.empty()) {
      counter++;
    Vertex v;
    Distance v_rank;
    boost::tie(v_rank, v) = Q.top();
    Q.pop();
    if (vis.should_stop(v, g)) {
        return;
    }
    vis.examine_vertex(v, g);
    BGL_FORALL_OUTEDGES_T(v, e, g, VertexListGraph) {
      Vertex w = target(e, g);
      vis.examine_edge(e, g);
      Distance e_weight = get(weight, e);
      if (compare(e_weight, zero))
        BOOST_THROW_EXCEPTION(negative_edge());
      bool decreased =
        relax(e, g, weight, predecessor, distance,
              combine, compare);
      Distance w_d = combine(get(distance, v), e_weight);
      if (decreased) {
        vis.edge_relaxed(e, g);
        Distance w_rank = combine(get(distance, w), h(w));
        put(cost, w, w_rank);
        vis.discover_vertex(w, g);
        Q.push(std::make_pair(w_rank, w));
      } else {
        vis.edge_not_relaxed(e, g);
      }
    }
    vis.finish_vertex(v, g);
  }
}
}} // end namespace boost::graph
于 2013-05-29T13:50:28.710 回答