3

二分木をk個の同様のサイズの部分に分割しようとしていました（k-1個のエッジを削除することにより）。この問題に対する効率的なアルゴリズムはありますか? それともNP困難ですか？論文、問題定義などへのポインタはありますか?

-- パーティショニングの品質を評価するための 1 つの妥当なメトリックは、最大パーティションと最小パーティションのサイズのギャップです。別のメトリックは、できるだけ多くの頂点を持つ最小のパーティションを作成することです。

4

2 に答える 2

3

多項式の決定論的解は次のとおりです。

  1. ツリーがルート化されており、2 つの固定値があると仮定しましょう:MINおよびMAX- 1 つのコンポーネントの最小許容サイズと最大許容サイズ。

  2. 次に、動的計画法を使用して、各コンポーネントのサイズが と の間にあるようなパーティションがあるかどうかを確認できMINますMAX。

  3. 条件 2) が成り立つように、頂点が に接続されるように のサブツリーを正確にカットする方法がf(node, cuts_count, current_count)あるtrue場合に限り、 を仮定しましょう。cuts_countnodecurrent_countnode

  4. 葉の基本ケースは次のとおりです: f(leaf, 1, 0)(親から葉へのエッジを切り取る) は、 and (切り取らないでください) が常に( andの他のすべての値に対して) であるtrue場合にのみです。 MIN <= 1MAX >= 1 f(leaf, 0, 1)truefalsecuts_countcurrent_count

  5. (リーフではない)を計算するfにはnode、次のアルゴリズムを使用できます。

    //Combine all possible children states.
for cuts_left in 0..k
    for cuts_right in 0..k
         for cnt_left in 0..left_subtree_size
            for cnt_right in 0..right_subtree_size
                if f(left_child, cuts_left, cnt_left) is true and
                   f(right_child, cuts_right, cnt_right) is true and then
                      f(node, cuts_left + cuts_right, cnt_left + cnt_right + 1) = true
//Cut an edge from this node to its parent.
for cuts in 0..k-1
    for cnt in 0..node's_subtree_size
       if f(node, cuts, node's_subtree_size) is true and MIN <= cnt <= MAX: 
           f(node, cuts + 1, 0) = true

    この疑似コードが行うことは、ノードの子のすべての可能な状態を組み合わせて、このノードの到達可能なすべての状態を計算し (for ループの最初の束)、このノードとその親の間のエッジを切断することによって残りの到達可能な状態を生成します (2 番目のループ)。 forループの束）（状態はタプルを意味します。私はそれを到達可能と(node, cuts_count, current_count)呼びます）。 これは、2 つの子を持つノードの場合であり、1 つの子を持つノードの場合も同様に処理できます。f(state)true

  6. 最後に、条件 2) を階層化するパーティションを見つけることが可能であり、それ以外の場合は不可能ですf(root, k, 0)。trueここでカットを行ったと「ふりをする」必要があります。これは、ルートを計算するときに (コーナー ケースを避けるためk)、ルートからその親 (このエッジとこの親は実際には存在しません) への架空のエッジもカットするためです。f

  7. このアルゴリズムの空間計算量 (固定MINおよびMAX) はO(n^2 * k)(nはノード数) であり、時間計算量はO(k^2 * n^2)です。複雑さは実際には のように見えるかもしれませんが、O(k^2 * n^3)そうではありません。なぜなら、ノードの左右のサブツリーの頂点の数の積は、最小共通の祖先がこのノードであるようなノードのペアの数とまったく同じだからです。しかし、ノードのペアの総数は ですO(n^2)(そして、各ペアには最小共通祖先が 1 つだけあります)。したがって、すべてのノードの左右のサブツリー サイズの積の合計は ですO(n^2)。

  8. MIN考えられるすべての値と値を単純に試してMAX、最適なものを選択することもできますが、その方が速く実行できます。重要な所見は、 と の解がある場合、 と の解もMIN常にMAX存在するということです。したがって、 （異なる値）のすべての可能な値を反復し、二分探索を適用して、有効な解を与える最小のものを見つけることができます（反復）。したがって、全体の時間計算量はです。ただし、 ( と の差を最小化するのではなく)最大化したい場合は、単純にこのアルゴリズムを使用して、どこでも値を無視することができます (その値を に設定することにより)。その後、二分探索はありませんMINMAX + 1MINn / kMAXlog nO(n^2 * k^2 * n / k * log n) = O(n^3 * k * log n)MINMAXMINMAXnMAXが必要になりますが、MIN代わりにバイナリ検索を実行してO(n^2 * k^2 * log n)解を得ることができます。

  9. パーティション自体を再構築するにはf(root, k, 0)、計算fに使用したステップから開始して適用できますが、今回は反対方向 (ルートからリーフ) に適用します。各状態の値を取得する方法に関する情報 (結合された子の状態またはエッジが切断される前の状態) に関する情報を保存し (および の初期計算中に適切に更新f)、パーティションを再構築することもできます。このデータを使用します (このステップの説明があまり明確でない場合は、動的プログラミングに関する記事を読んで答えを再構築すると役立つ場合があります)。

したがって、二分木にはこの問題の多項式解があります (任意のグラフでは NP 困難ですが)。

于 2014-07-29T20:32:48.590 に答える
3

できるだけ多くの頂点を持つ最小のパーツを作成するための非常に高速なソリューションを提案できます。

最小部分のサイズ S を推測し、それが正しいかどうかを確認したいとします。最初に、いくつかのステートメントを作成したいと思います。

  1. ツリーの合計サイズが S よりも大きい場合、S よりも大きいサブツリーが少なくとも 1 つ存在し、そのサブツリーのすべてのサブツリーが小さくなります。(両方の最大をチェックするだけで十分です。)

  2. 最小部分のサイズ >= S でツリーを分割する何らかの方法があり、サブツリー T があり、そのすべてのサブツリーが S よりも小さい場合、T 内のエッジが削除されないことを認めることができます。(そのような削除により、S よりも小さいパーティションが作成されるため)

  3. 最小部分のサイズ >= S でツリーを分割する何らかの方法があり、サイズ >= S で、内部に削除されたエッジがなく、部分の 1 つではないサブツリー T がある場合、ツリーを別の方法で分割できます。サブツリー T はパーツ自体の 1 つになり、すべてのパーツは S よりも小さくなりません (余分な頂点を元のパーツから他のパーツに移動するだけで、この他のパーツは小さくなりません)。

そこで、木を S 以上の k 個の部分に分割できるかどうかをチェックするアルゴリズムを次に示します。

  1. すべての適切な頂点 (サイズ >= S のサブツリーのルートと両方の子のサイズ < S) を見つけて、それらをリストに追加します。サブツリーが S より大きい間は、ルートから開始してすべての頂点を移動できます。

  2. リストが空ではなく、パーツの数が K より少ない場合、リストから頂点を取得し、ツリーから切り取ります。親頂点のサブツリーのサイズを更新し、そのうちの 1 つが適切になった場合にリストに追加します。すべての親頂点を更新する必要さえありません。新しいサブツリーのサイズが S より大きいことが最初にわかるまで、親頂点はまだリストに追加するのに適しておらず、後で更新できます。

  3. 頂点に割り当てられた元のサブツリー サイズを復元するために、ツリーを構築し直す必要がある場合があります。

これで、二分法を使用できます。上限は Smax = n/k として決定でき、下限は式 (2*Smin- 1)*(K - 1) + Smin = N から取得できます。サイズ Smin - それぞれ 1 の 2 つの子サブツリーで、サイズ Smin の部分が残ります。Smin = (n + k -1)/(2*k - 1) これで、S = (Smax + Smin)/2 を確認できます 上記の方法を使用してパーティションを構築できた場合、S はその最大値より小さいか等しいまた、構築されたパーティションの最小部分は S よりも大きい可能性があり、失敗した場合は、S の代わりに新しい下限を設定できます。S は可能な値よりも大きくなります。

1 回のチェックの時間の複雑さは、k に毎回更新される親ノードの数を掛けたものです。更新されたノードのバランスの取れたツリー数は一定です (前に説明したトリックを使用し、すべての親ノードを更新するわけではありません)。 /k) 最終的に不均衡なツリーの最悪のケース。適切な頂点の検索は、非常によく似た動作をします (検索中に渡されたすべての頂点は後で更新されます)。

n/k と (n + k -1)/(2*k - 1) の差は、n/k に比例します。

したがって、サブツリーのサイズが事前に計算されている場合は、最良の場合で O(k * log(n/k))、サブツリーのサイズが事前に計算されていない場合は O(n)、最悪の場合は O(n * log(n/k)) の時間計算量になります。場合。

この方法は、最後のパーツが比較的大きくなる状況につながる可能性がありますが、提案された方法を取得したら、それを最小限に抑えるためのいくつかの改善点を理解できると思います.

于 2014-08-01T23:54:49.717 に答える