4

N個の重み付き頂点とN-1個のエッジを持つグラフを3つの部分に分割して、各部分のすべての頂点の重みの合計の最大値が最小になるようにします。これは私が解決しようとしている実際の問題です、http：//www.iarcs.org.in/inoi/contests/jan2006/Advanced-1.php

次の方法を考えました

/*Edges are stored in an array E, and also in an adjacency matrix for depth first search.
Every edge in E has two attributes a and b which are the nodes of the edge*/
min-max = infinity
for i -> 0 to length(E):
   for j -> i+1 to length(E):
     /*Call depth first search on the nodes of both the edges E[i] and E[j]
     the depth first search returns the sum of weights of the vertices it visits,
     we keep track of the maximum weight returned by dfs*/
     Adjacency-matrix[E[i].a][E[i].b] = 0;
     Adjacency-matrix[E[j].a][E[j].b] = 0;
     max = 0
     temp = dfs(E[i].a) 
     if temp > max then max = temp
     temp = dfs(E[i].b) 
     if temp > max then max = temp
     temp = dfs(E[i].a) 
     if temp > max then max = temp
     temp = dfs(E[i].a) 
     if temp > max then max = temp

     if max < min-max
        min-max = max
     Adjacency-matrix[E[i].a][E[i].b] = 1;
     Adjacency-matrix[E[j].a][E[j].b] = 1;
    /*The depth first search is called four times but it will terminate one time
   if we keep track of the visited vertices because there are only three components*/

  /*After the outer loop terminates what we have in min-max will be the answer*/

上記のアルゴリズムはO（n ^ 3）時間かかります。これは、エッジの数がn-1になるため、外側のループが（n-1）実行されるためです。O（n ^ 2）かかる時間、dfsは各頂点に1つだけアクセスするため、O（n）時間になります。

ただし、問題は、nが<= 3000になる可能性があり、O（n ^ 3）時間がこの問題に適していないことです。リンク内の質問の解決をn^3より速く計算する他の方法はありますか？

編集：

@BorisStrandjevのアルゴリズムをcに実装しました。質問のテスト入力に対して正しい答えが得られましたが、他のすべてのテスト入力に対しては間違った答えが得られました。ここにideonehttp://ideone.comのコードへのリンクがあります。 / 67GSa2、ここでの出力は390であるはずですが、プログラムは395を出力します。

コードに間違いがないか調べようとしていますが、何も表示されません。誰かがここで私を助けてくれますか？私のコードが与えた答えは正解に非常に近いので、アルゴリズムに何か他のものがありますか？

編集2：

次のグラフでは-

ここに画像の説明を入力してください@BorisStrandjev、アルゴリズムは反復の1つでiを1、jを2として選択しますが、3番目の部分（3,4）は無効です。

編集3

私はついに私のコードに間違いを犯しました。V[i]がiとそのすべての子孫の合計を格納する代わりに、V [i]とその祖先を格納しました。そうでなければ、上記の例を正しく解決します。 。

4

3 に答える 3

3

はい、より速い方法があります。

必要な補助行列はほとんどなく、それらの作成と初期化の正しい方法はあなたに任せます。

まず、木を植えます。つまり、グラフを有向にします。各頂点の配列を計算VAL[i]します - 頂点とそのすべての子孫の乗客の量 (私たちが植えたことを思い出してください。今ではこれは理にかなっています)。また、頂点が頂点の子孫でdesc[i][j]ある場合に真になるブール行列を計算します。次に、次の操作を行います。ij

best_val = n
for i in 1...n
  for j in i + 1...n
    val_of_split = 0
    val_of_split_i = VAL[i]
    val_of_split_j = VAL[j]
    if desc[i][j] val_of_split_j -= VAL[i] // subtract all the nodes that go to i
    if desc[j][i] val_of_split_i -= VAL[j]
    val_of_split = max(val_of_split, val_of_split_i)
    val_of_split = max(val_of_split, val_of_split_j)
    val_of_split = max(val_of_split, n - val_of_split_i - val_of_split_j)
    best_val  = min(best_val, val_of_split)

このサイクルの実行後、答えは になりますbest_val。アルゴリズムは明らかにO(n^2)、計算方法を理解する必要があるだけでありdesc[i][j]、VAL[i]非常に複雑ですが、それほど複雑なタスクではありません。自分で理解できると思います。

編集ここでは、問題全体のコードを疑似コードに含めます。OPが自分で試して解決する前に、意図的にコードを含めませんでした：

int p[n] := // initialized from the input - price of the node itself
adjacency_list neighbors := // initialized to store the graph adjacency list

int VAL[n] := { 0 } // the price of a node and all its descendants
bool desc[n][n] := { false } // desc[i][j] - whether i is descendant of j

boolean visited[n][n] := {false} // whether the dfs visited the node already
stack parents := {empty-stack}; // the stack of nodes visited during dfs

dfs ( currentVertex ) {
   VAL[currentVertex] = p[currentVertex]
   parents.push(currentVertex)
   visited[currentVertex] = true
   for vertex : parents // a bit extended stack definition supporting iteration
       desc[currentVertex][vertex] = true
   for vertex : adjacency_list[currentVertex]
       if visited[vertex] continue
       dfs (currentvertex)
       VAL[currentVertex] += VAL[vertex]
   perents.pop

calculate_best ( )
    dfs(0)
    best_val = n
    for i in 0...(n - 1)
      for j in i + 1...(n - 1)
        val_of_split = 0
        val_of_split_i = VAL[i]
        val_of_split_j = VAL[j]
        if desc[i][j] val_of_split_j -= VAL[i]
        if desc[j][i] val_of_split_i -= VAL[j]
        val_of_split = max(val_of_split, val_of_split_i)
        val_of_split = max(val_of_split, val_of_split_j)
        val_of_split = max(val_of_split, n - val_of_split_i - val_of_split_j)
        best_val  = min(best_val, val_of_split)
    return best_val

そして、最良の分割は{descendants of i} \ {descendants of j}、{descendants of j} \ {descendants of i}および{all nodes} \ {descendants of i} U {descendants of j}です。

于 2013-01-07T11:42:05.017 に答える
1

この問題を解決するには、バイナリ検索と DFS を組み合わせて使用​​できます。

これが私がどのように進めるかです：

  1. グラフの重みの合計を計算し、グラフで最も重いエッジを見つけます。それらをSum、MaxEdge respにしましょう。
  2. 次に、この範囲 [maxEdge, Sum] の間でバイナリ検索を実行する必要があります。
  3. 各検索反復では、中央 = (開始 + 終了 / 2) です。ここで、開始ノードを選択して DFS st を実行し、サブグラフで通過したエッジの合計が可能な限り「中間」に近くなるようにします。ただし、この合計は中間よりも小さくしてください。これが 1 つのサブグラフになります。同じ反復で、前の DFS によってマークされていない別のノードを選択します。同じ方法で別の DFS を実行します。同様に、グラフを 3 つの部分に分割する必要があるため、もう一度実行します。
  4. 分。上記で計算された 3 つのサブグラフの重みは、この反復からの解です。
  5. 終了変数が開始変数を超えるまで、この二分探索を実行し続けます。

ステップ 4 で取得したすべての分数の最大値が答えです。3 つのサブグラフを取得するために、追加の簿記を行うことができます。

順序の複雑さ: N log(Sum)ここで、Sum はグラフの重みの合計です。

エッジではなく、加重頂点について話していることに気付きました。その場合、私のソリューションではエッジを頂点として扱います。それはまだ動作するはずです。

于 2013-01-07T11:45:36.333 に答える
1

編集4：これは機能しません!!!

リンク内のノードを3、4、5、6、1、2 の順序で処理すると、6 を処理した後 (私が思うに)、次のセットが得られます: {{3,4},{5}, {6}}、{{3,4,5}、{6}}、{{3,4,5,6}}、それらを再び分割する簡単な方法はありません。

他の誰かが DP アルゴリズムを考えていた場合に備えて、この回答をここに残しておきます。

DPアルゴリズムですでに処理されたすべてのネイバーを調べるとうまくいくかもしれません。

.

私は動的計画法のアルゴリズムを考えています。ここで、マトリックスは (項目 x セット数) です。

n = number of sets
k = number of vertices
// row 0 represents 0 elements included
A[0, 0] = 0
for (s = 1:n)
  A[0, s] = INFINITY
for (i = 1:k)
  for (s = 0:n)
    B = A[i-1, s] with i inserted into minimum one of its neighbouring sets
    A[i, s] = min(A[i-1, s-1], B)) // A[i-1, s-1] = INFINITY if s-1 < 0

編集：DPの説明：

これは、かなり基本的な動的計画法のアルゴリズムです。より良い説明が必要な場合は、さらに読んでください。これは非常に強力なツールです。

A は行列です。行 i は、i までのすべての頂点を含むグラフを表します。列 c は、セット数 = c の解を表します。

したがってA[2,3]、アイテム 0、アイテム 1、およびアイテム 2 と 3 のセットを含むグラフの最良の結果が得られるため、それぞれが独自のセットになります。

次に、項目 0 から開始し、各セット数の行を計算し (唯一有効なのはセット数 = 1 です)、上記の式で項目 1 を実行し、次に項目 2 などを実行します。

A[a, b]は、含まれるセット数と b 個までのすべての頂点を持つ最適解です。したがって、返されるだけですA[k, n](すべての頂点が含まれ、セットの目標数が含まれているもの)。

編集 2: 複雑さ

O(k*n*b)ここで、b はノードの分岐係数です (隣接リストを使用すると仮定します)。

であるためn = 3、これはO(3*k*b)=O(k*b)です。

編集 3: 頂点を追加する隣接セットの決定

k 個の要素からなる n 個の配列をそれぞれ共用体検索構造に保持し、各セットがそのセットの合計を指すようにします。新しい行ごとに、頂点を追加できるセットを決定するために、その隣接リストを使用して、各隣接のセットと値を検索します。最適なオプションが見つかったら、その要素を該当するセットに追加し、追加した要素の値だけ合計を増やします。

アルゴリズムは 1 行しか見ていないので、最後の行を追跡するだけでよく (行列全体を保存する必要はありません)、前の行の n 個の配列をコピーするのではなく変更できます。

于 2013-01-07T11:35:26.540 に答える