graph - 3 点間の最短経路

Question

グラフでは、2 点間の最短経路を見つけ、途中で 1 つのチェックポイントを訪れる必要があります。また、各頂点にアクセスできるのは 1 回だけです。ネットワークフローと関係があると思いますが、それを実装する方法がわかりません。

Answer 1

これは、キャパシテイテッド マルチコモディティ最小コスト フロー問題として完全にモデル化できます。頂点を 2 回使用せずに A から C 経由で B に移動したい。A から C へのフロー (商品 1) および B から C へのフロー (商品 2) としてモデル化できます。ノードが 2 回使用されるのを避けるには、(モデル内の) すべてのノードで次のトリックを実行する必要があります。

p 個の入力エッジと t 個の出力エッジを持つノード X が与えられた場合、新しいノード Y を作成し、リンクを再配線します。p 個の着信リンクはすべて X に到着し、q 個の発信エッジはすべて Y から出発します。X から Y へのリンク (L) を 1 つだけ追加します。L リンクの容量を 1 に設定することにより、各ノードのみが使用されます。一度。

その後、(M)ILP として書き留めて、解決することができます。ILP は、正しい解決策が存在する場合に提供します。アプリケーションによっては、やり過ぎかもしれません。高速なヒューリスティックが必要な場合は、2 つの A* 検索を使用して、それらが重複しないことを願ってください。