無向グラフG=（V、E）が与えられると、各ノードiは「Ci」個のオブジェクトに関連付けられます。各ステップで、すべてのノードiについて、Ciオブジェクトはiの隣接ノード間で均等に分割されます。Kステップ後、オブジェクトが最も多い上位5ノードのオブジェクト数を出力します。
1つのステップで行われることの1つの例を次に示します
。AのオブジェクトはBとCによって均等に分割されます。B
のオブジェクトはAとCによって均等に分割されます。C
のオブジェクトはAとBによって均等に分割されます。
いくつかの制約：| V | <10 ^ 5、| E | <2 * 10 ^ 5、K <10 ^ 7、Ci <1000
私の現在の考えは、各ステップの変換を行列で表すことです。この問題は、行列のべき乗の計算に変換されます。しかし、| V |を考慮すると、このソリューションは遅すぎます。10^5にすることができます。
それを行うためのより速い方法はありますか？
単一ステップの行列方程式はのようM x = x'になります。ここxで、は現在のノードの内容のベクトルであり、x'は1ステップ後の内容です。つまり、x' = M x。その後のステップの内容はですx" = M x' = M(M x)。Mの例を次に示します。ここで、グラフの隣接行列が左側に示されています。見出しの列#nbrは、ノードa、b...eの隣接ノードの数です。行列Mは、各1を同じ列の1の数に等しい分数で置き換えることにより、隣接行列から形成されます。
a b c d e #nbr matrix M
a 0 0 1 1 0 2 0 0 1/3 1/4 0
b 0 0 0 1 0 1 0 0 0 1/4 0
c 1 0 0 1 1 3 1/2 0 0 1/4 1/2
d 1 1 1 0 1 4 1/2 1 1/3 0 1/2
e 0 0 1 1 0 2 0 0 1/3 1/4 0
初期コンテンツから始まるKステップを実行するにはx、を計算するだけ(M^K) xです。2を底とする対数lg Kを表す、行列の乗算を必要とするべき乗法を使用しますlg。行列の乗算は通常O（n ^ 3）の複雑さであるため、この方法は、単純に実装されている場合はO（lg K * n ^ 3）、またはO（lg K * n ^ 2.376）Coppersmith/Winogradアルゴリズムを使用している場合。Mを（P ^ -1）APの形式に対角化することにより、複雑さをO（n ^ 2.376）に減らすことができます。つまり、lg K乗数を削除できます。これは、O（n lg K）演算であり、次のようになります。全体的にO（n ^ 2.376）。対角化は通常O（n ^ 3）のコストがかかりますが、Coppersmith / Winogradアルゴリズムを使用するとO（n ^ 2.376）になります。M^K = (P^-1)(A^K)PA^K