10

以下は消費税です。

G を n 個の頂点と m 個の辺を持つ重み付き有向グラフとし、すべての辺に正の重みを付けます。有向サイクルは、同じ頂点で開始および終了し、少なくとも 1 つのエッジを含む有向パスです。O(n^3) アルゴリズムを与えて、最小総重量の G の有向サイクルを見つけます。O((n^2)*m) アルゴリズムには部分的なクレジットが与えられます。

これが私のアルゴリズムです。

私はしDFSます。を見つけるたびにback edge、有向サイクルがあることがわかります。

parent array次に、 (サイクル内のすべての頂点を移動するまで) に沿って一時的に逆戻りし、を計算しtotal weightsます。

total weight次に、このサイクルの を と比較しminます。minは常に最小の総重量を取ります。DFS が終了すると、最小有向サイクルも検出されます。

では、時間の複雑さについてです。

正直なところ、私のアルゴリズムの時間計算量はわかりません。

DFS の場合、トラバーサルには O(m+n) かかります (m がエッジの数で、n が頂点の数の場合)。頂点ごとに、その祖先の 1 つを指す場合があり、循環を形成します。サイクルが見つかった場合、重みの合計を合計するには O(n) かかります。

したがって、合計時間は O(m+n*n) だと思います。しかし、物品税に記載されているように、最適な時間は O(n^3) であり、通常の時間は O(m*n^2) であることは明らかです。

誰でも私を助けることができます:

  1. 私のアルゴリズムは正しいですか？
  2. アルゴリズムが正しい場合、時間計算量はどのくらいですか?
  3. この問題に対するより良いアルゴリズムはありますか?
4

4 に答える 4

25

ここでFloyd-Warshallアルゴリズムを使用できます。

Floyd-Warshall アルゴリズムは、頂点のすべてのペア間の最短経路を見つけます。

この場合、アルゴリズムは非常に単純で、すべてのペア(u,v)を調べて、最小化dist(u,v)+dist(v,u)されたペアuをu見つけますdist(u,v)+dist(v,u)。グラフで自己ループ (エッジ(u,u)) も許可されている場合は、それらのサイクル (およびそれらのみ) がアルゴリズムによってチェックされていないため、それらを単独でチェックする必要もあります。

擬似コード:

run Floyd Warshall on the graph
min <- infinity
vertex <- None
for each pair of vertices u,v
    if (dist(u,v) + dist(v,u) < min):
           min <- dist(u,v) + dist(v,u)
           pair <- (u,v)
return path(u,v) + path(v,u)

path(u,v) + path(v,u)は、実際には u から v へ、次に v から u へのパスであり、サイクルです。

アルゴリズムの実行時間はです。O(n^3)ループに時間がかかるため、floyd-warshall がボトルネックであるためO(n^2)です。

ここでの正しさは些細なことだと思いますが、私に同意しない場合はお知らせください。よりよく説明できるように努めます。

于 2012-05-05T06:52:52.620 に答える
5

私のアルゴリズムは正しいですか？

いいえ、反例を挙げましょう。から DFS を開始したとします。からへuの 2 つのパスp1とp2からuへvの 1つのパスがあり、は よりも短くなっています。p3vup1p2

p2への道をたどることから始めて、道を通ってvに戻ると仮定uしますp3。1 つのサイクルが見つかりましたが、最小値ではないようです。その後u、p1パスをたどって探索を続けますが、v完全に探索されているため、DFS は最小サイクルを見つけられずに終了します。

于 2012-10-20T10:27:09.587 に答える
2

「頂点ごとに、その祖先の 1 つを指す可能性があるため、サイクルを形成します」

Nを意味する祖先のいずれかを指す可能性があると思います

また、dfs から出たときにどのように頂点をマークするのですか? 他の頂点から再びそこに来て、別のサイクルになる可能性があります。したがって、これはもはや (n+m) dfs ではありません。

  1. だからあなたのアルゴリズムは不完全です
  2. こっちも一緒

3. 1 つの dfs の間、頂点は見えないかチェックされているべきだと思います。チェックされた場合、開始頂点へのパスの最小重みを格納できます。したがって、他のステージでその頂点へのエッジを見つけた場合、このパスをもう検索する必要はありません。この dfs は、最初の頂点を含む最小有向サイクルを見つけます。そしてそれはO（n ^ 2）です（グラフをリストとして保存する場合はO（n + m））

したがって、他の頂点から行う場合は、O(n^3) (O(n*(n+m)) になります。

申し訳ありませんが、私の英語と私は専門用語が苦手です

于 2012-05-05T04:13:07.930 に答える