2

数字でラベル付けされたエッジを持つ DAG があるとします。パスの値をラベルの積として定義します。各 (ソース、シンク) ペアについて、ソースからシンクへのすべてのパスの値の合計を見つけたいと考えています。これは動的計画法を使用して多項式時間で行うことができますが、問題を分解する方法にはまだいくつかの選択肢があります。私の場合、異なるラベル付けで繰り返し評価する必要がある 1 つの DAG があります。私の質問は、特定の DAG について、異なるラベル付けのこれらの値を繰り返し計算するための適切な戦略を事前に計算するにはどうすればよいですか? 掛け算の回数を最小化する方法など、最適な方法を見つけるアルゴリズムがあればいいのですが。しかし、これは質問するには多すぎるかもしれません。適切な分解を提供するアルゴリズムに非常に満足しています。

4

1 に答える 1

1

Sをソースのセット、VをDAGの頂点のセット、Eをエッジのセット、n = | V |、m = | S |、Wをエッジの重みを格納するnxn行列、CをC [i、j]がアルゴリズムの最後に、iからjまでのすべてのパスの値の合計を保持するようなmxn行列。アルゴリズムの説明と正当性の証明を簡単にするために、1からnまでのグラフの頂点は、ノード1からmがソースであるトポロジカル秩序であると仮定します。これにより、アルゴリズムの実行時間にO（| E | + | V |）が追加されます。

アルゴリズムの擬似コードは次のとおりです。

1: set C[i,j] to 1 if i=j and i is a source node, and to 0 otherwise.
2: sort the DAG topologically
3: for k=1 to n (vertex traversal in the topological order)
4:   foreach predecessor k' of vertex k
5:     foreach i in S
6:       C[i,k] += C[i,k']*W[k',k]

2つの外側のループには合計O（| E | + | V |）の反復があります。したがって、アルゴリズムの実行時間は、加算と乗算に一定の時間がかかると仮定すると、O（（| V | + | E |）.m）になります。これには、トポロジカルソートの時間が含まれます。

正当性の証明：最も外側のループのk回目の反復の完了後、C [i、k]はSの各iのiからkまでのすべてのパスの値の合計であることを帰納法で証明します。
基本ケース： k = 1の場合は明らか（最初の要素には先行要素がないため）
帰納法：C [i、j]がすべてのj<kに対して正しく計算されていると仮定します。ソースiからkへのすべてのパスは、kの先行k'を通過する必要があります。トポロジカル順序で反復しているため、k'はkより小さくなければならず、帰納法の仮説によれば、C [i、k']はiからk'へのパスの値の合計です。さらに、特定の先行オブジェクトk'を通過するiからkまでのパスの値の合計は、iからk'までのパスの値の合計、つまりC [i、k']にW[kを掛けたものに等しくなります。 '、k]。したがって、iからkまでのすべてのパスの値の合計は、kのすべての先行k'にわたるC [i、k'] * W [k'、k]の合計です。

同じグラフ構造、異なるW行列：同じ構造であるが異なるWを持つ異なるグラフの行列Cを計算する必要がある場合、次のことができます。C'を、要素が3タプルのリストである行列とします。上記の6行目を次のように置き換えます

C'[i,k].append((i,k',k))

次に、トポロジカル順序で頂点を反復処理し、C'[i、k]のタプルを反復処理することで、グラフ構造を見ずにC [i、k]を計算できます。これは、タプルが暗黙的にグラフ構造を表すためです。複雑さという点では、それは良くも悪くもありません。

于 2012-05-04T18:30:58.600 に答える