Boost :: d_ary_heap_indirect DistanceMapテンプレート引数

Question

私のコードでboost::d_ary_heap_indirectを使用していますが、テンプレート引数の1つであるDistanceMapを理解できません。コメント（完全なソースフィットネスエクササイズhere）は、これは言っている：

// - DistanceMap must be a ReadablePropertyMap from Value to something 
// (typedef'ed as distance_type). 

が、私はそれを見て試してみましたブースト・クラスでの使用ですが、boost::astar_searchで使用されるとき、それは私もあまり理解detail::make_property_map_from_arg_pack_gen<tag::rank_map, D>(D())(g, arg_pack)、によって作成されました...

ソースを見ると、優先度が高いと感じるようになりますが、「距離」と呼ばれるとそれは悲惨なようです。

Answer 1

はい、DistanceMapは、値から優先度までのマップ、別名キーです。 D-aryヒープは一般的にDijkstraのアルゴリズムに使用されます。 Dijkstraのアルゴリズムでは、優先度は、特に、エッジパスコスト（距離）によって表されます。私はそれがなぜこのように名付けられたのかと思う。

たとえば、このマップを返す方法はkeys()です。

// return value-to-key map 
DistanceMap keys() const 
{ 
    return distance; 
}