9

入力：グラフG（すべてのエッジに単位の重みがあると仮定）、ソースと宛先の頂点のペア（X1、Y1）、（X2 Y2）、...、（Xk、Yk）（すべてが異なる）。

出力：ルートR1（X1からY1）、R2（X2からY2）、...、Rk（XkからYk）は、R1、R2、...、Rkがそれらの間で頂点を共有しないようにします。ルートの長さを最適化する必要はありません。

どのアルゴリズムを使用しますか？この問題の複雑さは何でしょうか？ヒューリスティックなほとんどの場合のソリューションではなく、理論的に強力なソリューションが必要です。

最も明白な解決策は、各自由頂点（X1、X2、.. Xk、またはY1、Y2、...、Ykではない）をk個のパスの1つに割り当て、それらが実際に必要な方法でパスを形成するかどうかを確認することです。n ^ kの割り当てが可能です（より正確には（n-2k）^ k）。もっと上手くできますか？グラフを2Dグリッド構造と仮定するとどうなりますか？（ https://play.google.com/store/apps/details?id=com.bigduckgames.flowゲームを解決するのと同じ ですが、すべての正方形の要件を満たす必要はありません）。

4

3 に答える 3

10

この論文で考えられる解決策の1つを見つけることができます：川林健一、小林裕介、ブルース・リードによる「二次時間における互いに素な経路の問題」（pdf）。

このソリューションは簡単ではありませんが効率的です。O（N 2）の時間計算量のみです。ここで、Nは頂点の数です。Kが小さな定数である場合にのみ効率的です。

これを多品種フロー問題として解決することも可能です。しかし、複数の商品に固有のアルゴリズムが十分に効率的であるとは思えません。一般的な多品種フロー問題（少なくとも1つの商品のフローが1より大きい場合）はNP困難であるためです。

これが単一商品の流れの問題として解決できる可能性は低いです。たとえば、次の提案の反例は次のとおりです。

... SをX2に、TをY2のエッジを容量0.5に制限しますか？必要なマッチアップを持つ互いに素なルートのペアがある場合、SからTまでの合計フローは1.5になる可能性があります...この方法では、互いに素なパス。

                                           反例グラフ

容量1.5のフローを見つけるのは簡単です（このフローは図に示されています）。ただし、頂点の両方（緑と赤）のペアを互いに素なパスで接続する方法はありません。

于 2012-12-04T17:03:37.273 に答える
6

MaxFlowを使用してこの問題を解決できます。Flowに慣れていない場合は、Flowに関する資料を読むことができます。

アルゴリズム

  1. 1つのスーパーシンク頂点Sと1つのスーパーターゲット頂点Tを作成します。いくつかの新しいエッジをリンクしますS->X1、S-> X2、Y1-> T、Y2-> T .....、S-> Xk、Yk-> T、およびエッジの各ペアの容量を設定します1、0.75、0.5....。
  2. 各頂点pを2つの新しい頂点p'とp"に分離し、 p'とp"を容量も1である新しいエッジにリンクします。
  3. MaxFlowをSからTまで実行し、流路の情報を保存します。この新しいグラフのmaxflowが2であることは明らかです。そして、2つのフローパスが必要なルートを示しています。アルゴリズムは常に最大フローを検出するため、最終的なフローパスはX1-> Y1、X2-> Y2 ...Xk->Ykである必要があります。

証拠

各頂点を分離し、容量が1の1つのエッジに置き換えるため、元のグラフの各頂点は1つのフローで走査できます。つまり、各頂点が1つのパスに属することができるということでもあります。

拡張する

2つのパスの全長を最小化したい場合は、アルゴリズムを拡張するだけです。新しいグラフの各エッジに、コストという1つのプロパティを追加します。原点グラフからのエッジのコストは0になります。個別の頂点を示す新しいエッジのコストは1になります。Min-Cost-Max-Flowアルゴリズムを実行して、必要な情報を取得できます。

複雑

MaxFlowの複雑さは、Dinicアルゴリズムを使用した場合のO（N * N * M）です。また、Min-Cost-Max-Flowの複雑さも約O（N * N * N）です。

于 2012-11-27T05:26:09.343 に答える
2

完全な解決策はありませんが、最初のステップとして使用できる削減があります。まず、グラフを2重連結コンポーネントに分解します。この分解により、カットされたすべての頂点が識別されます。頂点は、削除されると、グラフを2つのコンポーネントに切断します。切断点ごとに、ソース頂点と宛先頂点のペアは、非分割ペアとしてカットの同じ側にあるか、分割ペアとしてカットの反対側にあります。（切断点がソースまたはターゲットのいずれかである場合は、分割ペアとしてカウントします。）

  • 切断点に2つ以上の分割ペアがある場合、両方のパスが切断点を通過する必要があるため、問題は解決されません。（これは、上記の私のコメントの五分位グラフの例の一般化です。）

  • 分割ペアがない場合、問題は2つの小さな問題に解決されます。各コンポーネントに1つずつあります。解決策は、小さい方のそれぞれの解決策の組み合わせです。

  • 分割ペアが1つだけある場合は、問題をより小さな問題のペアに減らします。1つは各コンポーネントの関連バージョンで、切断点はグラフ間で複製されます。切断点がX_1何らかのコンポーネントにあると仮定します。そのコンポーネントで、複製された切断点にラベルを付けますY_1。他のコンポーネントの場合はその逆です。前と同じように、解決策は2つの小さいものの組み合わせです。

このソリューションの本質は鳩の巣原理です。これは、2つのパスが1つのポイントを通過できないためです。1つ上に移動すると、3つのポイントが2つのポイントを通過することはできません。これにより、すぐに3つに接続されたコンポーネントを調べ、SPQRツリーを使用することになります。この構造から、すべての2点カットを列挙できます。前と同じように、頂点を2つのセットに分割し、同様に進みます。ただし、分割されたペアのすべての順列を考慮する必要があります。サブ問題はすべて、3つに接続されたコンポーネントにあります。

これがどこにつながるかがわかります。SPQRツリーがより高度な接続性に一般化されているかどうかはわかりません。たとえそうだったとしても、一般的に組み合わせ爆発が予想されます。そして、これはすべて難しい問題につながります。

最初は、この問題は平面グラフでは扱いやすいと思いました。そうではありません; 上記の論文を参照してください。NP完全のままです。

上記のアルゴリズムが与えられると、2重連結グラフで問題を想定できます。ここでの違いは、平面グラフには「ローカル」エッジしかないことです（グラフを球に埋め込むことで確認できます）。「リモート」エッジは他のエッジと交差する必要があります。これは、最小限のカットセットの動作がはるかに適切に動作することを意味します。しかし、問題を機能させるのに十分な振る舞いはありません。

于 2012-12-04T02:08:08.827 に答える