4

nノードとmエッジを持つ有向グラフを考えてみましょう。各エッジに重みが付けられます。開始ノードsと終了ノードがありますe。次のようなノードの最大数を持つからsへのパスを見つけたいとします。e

  1. 合計距離が定数より小さいd
  2. s から始めて、パス内の各ノードは、前のノードよりもノードに近いですe。(つまり、パスをトラバースすると、残りのパスのエッジ ウェイトに関して、目的地に近づいていますe。)

グラフにはサイクルがないと仮定できます。負の重みはありません。この問題に対する効率的なアルゴリズムは既に存在しますか? この問題に名前はありますか？

4

1 に答える 1

3

最終的に何をするにしても、最初から BFS/DFS を実行して、到達できるsかどうかを確認します。eこれには O(n+m) しかかからないため、問題が複雑になることはありません (とにかくすべての頂点とエッジを調べる必要があるため)。また、重みのあるすべてのエッジは0、2 番目の基準を満たさないため、他の操作を行う前に削除してください。

編集:アルゴリズムを考え出しました。これは多項式ですが、グラフのサイズによっては、まだ十分に効率的ではない場合があります。さらに下の編集を参照してください。

次に、いくつかの複雑さについて説明します。ここで最初に考えるべきことは、実際に持つことができるパスの数の上限です。そのためd、エッジの選択と重みに応じて、潜在的なアルゴリズムの複雑さにも上限があります。

DAG にはいくつのエッジを含めることができますか? 答えは ですn(n-1)/2。これは厳密な境界です。n頂点を取り、それらを 1 から に並べますn。2 つの頂点iとに対して、グラフ iff にjエッジを追加します。このように、頂点のすべてのペアに対して、それらの間に有向エッジが 1 つだけ存在するため、合計すると の合計になります。i->ji<jn(n-1)/2n

上記のグラフで、ある頂点から別の頂点へのパスはいくつありますか? 答えは 2 n-2です。帰納法による証明:

上記のように 2 つの頂点でグラフを取得します。1 = 2 0 = 2 2-2頂点 1 から頂点 2 へのパスがあります: (1->2)。
誘導ステップ:上記の頂点グラフの number の頂点から number の頂点への 2 n-2パスがあると仮定し、各頂点の数を増やし、必要なエッジと共に新しい頂点を追加します。とラベル付けされた頂点への独自のエッジがあります。さらに、 [2;n] のすべての頂点への 2 i-2パスがあります (他の頂点が集合的に持っている頂点へのすべてのパスがあり、それぞれが edge で「プレフィックス」されています)。これにより、1 + Σ nが得られます。1nn1nn+1in+11->ik=2 (2 k-2 ) = 1 + Σ n-2 k=0 (2 k-2 ) = 1 + (2 n-1 - 1) = 2 n-1 = 2 (n+1)-2 .

したがって、頂点のいくつかのペアの間に 2 n-2の異なるパスを持つ DAG があることがわかります。d重みと の選択によっては、すべてを考慮する必要がある場合があるため、これは少し暗い見通しです。ただし、これ自体は、何らかの最適な形式 (探しているもの) を効率的に選択できないという意味ではありません。

編集：わかりましたので、ここに私がすることを示します：

  1. 2 番目の基準を満たすことはできないため、重みが 0 のすべてのエッジを削除します (より小さいが除外しました)。
  2. グラフのトポロジカル ソートを実行します。以下では、s から e へのグラフのトポロジカル ソートの部分だけを考えてみましょう。これを整数間隔 [s;e] と呼びましょう。厳密にはその間隔内にないグラフからすべてを削除します。つまり、インシデント エッジと共にその範囲外にあるすべての頂点を意味します。topSort 中に、s から e へのパスがあるかどうかも確認できるため、s-...->e のパスがあるかどうかがわかります。この部分の複雑さは O(n+m) です。
  3. 実際のアルゴリズムは次のとおりです。
    • [s;e] の頂点を、トポロジカル ソートによって課された順序でトラバースします
    • すべての頂点 v について、情報の 2 次元配列を格納します。これを pre v [][]と呼びましょう。これは、ノードに向かうパス上のノードの先行者に関する情報を保存するためです。
    • in pre v [i][j] に、j がそのパス上の現在の頂点の前身である場合、長さ i の合計パスの長さ (頂点でカウント) をエッジの重みの合計として保存します。たとえば、pre s+1 [1][s] にはエッジ s->s+1 の重みが含まれますが、pre s+1 の他のすべてのエントリは 0/未定義になります。
    • 新しい頂点 v の配列を計算するとき、入力エッジをチェックし、それらのエッジの開始頂点の配列を反復処理するだけです。たとえば、頂点 v に頂点 w からの入力エッジがあり、重みが c であるとします。エントリ pre v [i][w] がどうあるべきかを考えてみましょう。エッジ w->v があるので、pre v [i][w] in v を
      min(pre w[i-1][k] すべての k に対して、ただし 0) + c のエントリは無視します (配列の添え字に注意してください!); w に至る長さ i - 1 のパスのコストを効果的に取り、エッジ w->v のコストを追加します。なんで最低？頂点 w は、長さ i - 1 のパスに対して多くの先行ノードを持つことができます。ただし、各頂点で貪欲な最小化を行うことで、コスト制限を超えないようにしたいと考えています。[1;sv] のすべての i に対してこれを行う必要があります。
    • 頂点の配列を計算するときは、コストが d を超えるパスを与えるエントリを設定しないでください。すべてのエッジには正の重みがあるため、各エッジでよりコストのかかるパスしか取得できないため、それらは無視してください。
    • e に到達し、 pre eの計算が終了したら、アルゴリズムのこの部分は完了です。
  4. pre e [es]から始めて、 pre eを繰り返します。サイクルがないため、すべてのパスは単純なパスであり、s から e への最長パスは es エッジを持つことができます。pre e [i] がゼロ以外の (定義されていることを意味する) エントリを持つような最大の i を見つけます。存在しない場合、基準に適合するパスはありません。他の頂点の配列を使用して、既存のパスを再構築できます。

これで、O(n^3) の空間の複雑さと O(n²m) の時間の複雑さが得られます。配列には O(n²) 個のエントリがあり、エッジごとに 1 つの配列で、O(m) 個の配列を反復処理する必要があります。しかし、ここでのデータ構造の無駄な使用が、ハッシュ構造や配列以外のものを使用して最適化できる場所は非常に明白だと思います。または、1 次元配列を使用して、毎回再計算する代わりに現在の最小値のみを保存することもできます (パスのエッジの重みの合計を先行頂点と一緒にカプセル化する必要がありますが、先行を知る必要があるためです)。これにより、配列のサイズが n² から n に変更されます。これは、頂点へのパス上のノード数ごとに 1 つのエントリのみが必要になり、アルゴリズムのスペースの複雑さが O に低下するためです。 (n²) と O(nm) への時間計算量。e、それらも安全に無視できるためです。

于 2013-03-15T00:07:55.073 に答える