問題タブ [boost-property-map]

次のコードはコンパイルされません。

頂点リストを vecS http://coliru.stacked-crooked.com/a/abeb9e3f96e92af0に変更した後に機能します。

DFS が確定的なアクセスを必要とするため、この制限はありますか?

ありがとうございました、

http://www.boost.org/doc/libs/1_37_0/libs/graph/example/astar-cities.cppにある例から始めて、ブーストA *アルゴリズムで遊んでいます。

そのヒューリスティックとビジターをオーバーライドして、ある種のカスタム調整を行うことができることがわかりましたが、学習例として、次のようなことの概念はまだよくわかりません。アルゴリズムに移動時間 (エッジの重み) が X より大きい場合 (たとえば 100 分) は、エッジ都市 - 都市を選択しないでください。(可能であれば、他のパスが見つからない場合は、パスが見つからない代わりにその都市を選択する必要があります)

その都市を選択しないように「だます」ために、実際よりも長い時間を返すカスタムのヒューリスティック クラスを試しましたが、問題は、このトリックを使用すると、罰せられた都市が破棄され、その後のやり取りでも破棄されることです。(次の例で説明します: B->D はより良いパスが見つかったために破棄されますが、都市 D は破棄されません (次の繰り返しで選択されていることがわかります)

そこで、問題をさらに単純化しました。

この例 (元のコードをベースとして使用) では、次のルートが得られます。

開始頂点: A

ゴール頂点：E

A から E への最短経路: A -> B -> D -> E

総移動時間: 204.5

問題は、B -> D パスです。これは非常に長い距離です (たとえば、しきい値が 100 であると仮定すると、A -> B -> C -> D -> E のようなパスが望ましいでしょう)。 、2 つの都市間の距離が 100 を超えていない (もちろん、可能な場合のみ、他にパスがない場合は、いずれかを選択する必要があります)

私はそれを次善の方法で解決しました：カスタム関数は、エッジを追加すると（または手動で重みを設定します）return travelTime > 100 ? travelTime * 2 : travelTime、次の方法でテストできます：

この方法で目的A -> B -> C -> D -> Eの が得られますが、この方法は問題のハック/回避策であり、内部で入力データを変更するものであり、最善の解決策ではないと思います。

距離/移動時間を手動で変更せずにこれを達成するためのより良い方法はありますか?

BGL では、bfs/dfs 検索中にアクセスされたときに、グラフ内の頂点の固有の色 (未処理の場合は白、訪問済みの場合は灰色、完了した場合は黒) にアクセスする方法がよくわかりません。

誰かが dfs/bfs ビジター内から頂点の色にアクセスする方法を説明できますか? たとえば、カスタムexamine_edge?

boost::graphアルゴリズムの使用法を新しい実装クラスのセットに変換するのに苦労しています。私は疑問に思っています:参照boost::graphのみを保存する場合、オブジェクトのプロパティにアクセスすることさえ可能std::shared_ptrですか? 次のように:

std::shared_ptr実装のグラフ ラベル ライターwrite_graphvizまたはその他のプロパティで使用する のメンバーにアクセスすることは可能ですか?

ありがとうございました！

質問はここから始まりましたが、すべての更新の後、すでに別のタイトルの別の質問になっています。

私のGraphタイプは次のように定義されています。

CostTypeたまたまどこにあるint。

次のように、鎌田川井春のレイアウトを取得しようとしています。

gccバージョン 4.8.2 は不平を言います:

このメッセージは不可解すぎて私には理解できません。int [2][2]に変換できないことと関係がありdouble (*)[2]ます。CostTypeこれは であるという事実に関連していintますか? しかし、なぜそれができないのですか？私が間違っていることを理解するのに非常に役立ちます。

BGL でconnected_components()( で構築された) 双方向グラフに対して実行することは可能ですか? ::boost::bidirectionalSそのように構築されたグラフで次のようなものを実行すると、セグメンテーション違反が発生します。

これは驚くべきことではありません。ドキュメントによると、無向グラフに対してのみ使用できることが示されているからです。

それができない場合、検索アルゴリズム (BFS または DFS) のいずれかを逆方向に使用することは可能ですか? たとえば、終端の頂点 (アウトバウンド エッジのない頂点) から検索を開始し、逆方向に作業したいと考えています。

私も間違った質問をしている可能性があります。私がしようとしているのは、特定の終端頂点へのパスを持つすべての頂点のサブグラフを見つけることです。BGLでそれを行うより直接的な方法はありますか?

もちろん、すべて自分で行うこともできますが、できれば BGL 機能を使用したいと考えています。

dijkstra_shortest_paths で使用する add_edge_by_label を使用するこのラベル付きグラフに重みを追加するにはどうすればよいですか? 例を使用しようとしています ありがとう