boost :: graph astar算法無例外

我正在閱讀boost :: graph文檔以備將來使用。我對A *算法特別感興趣。boost :: graph astar算法無例外

看看boost :: graph :: astar_search的用法示例，似乎停止算法的方法是引發異常並將其捕獲到算法的外部。

由於我不想拋出任何異常，導致C++中的異常處理非常複雜，效率不高，我不知道boost :: graph是否提供了另一種方法來在達到目標時停止算法。

有沒有人有另一個例子沒有使用任何例外？

2013-04-26 neodelphi

'原因的異常處理在C++中是非常複雜的，不是很efficient'在哪裏你從這裏得到這個？ – 2013-04-26 21:54:43

@dauphic看看異常被捕獲時真正發生在彙編中的情況（真正有很多代碼在運行！）。爲了性能比較，還測試了一些「返回代碼VS異常」。例外情況應該保持例外，我認爲將它用於算法目的不是一個好主意。 – neodelphi 2013-04-26 22:11:20

根據FAQ，早期退出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-29 13:50:28

感謝提到常見問題解答。得出相同的結論，即需要修改算法。 – neodelphi 2013-05-30 20:13:53

boost :: graph astar算法無例外

回答

相關問題