3

「Far Vertices」という名前のinterviewstreetで、動的プログラミングの問題に遭遇しました。

問題は次のようなものです:

N 個の頂点と N-1 個のエッジを持つツリーが与えられます。タスクは、マークされていない 2 つの頂点間の最大距離が K 以下になるように、できるだけ少数の頂点をマークすることです。この値を出力に書き込む必要があります。2 つの頂点 i と j の間の距離は、頂点 j から頂点 i に到達するために通過する必要があるエッジの最小数として定義されます。

サブセットのすべてのペアがKを超える距離を持たないように、ノードの最大接続サブセットを見つけるために、ツリーのすべてのノードからdfsを実行しようとしていました。しかし、状態を定義できず、間の遷移州。

私を助けてくれる人はいますか？

ありがとう。

4

2 に答える 2

3

この問題は、基本的に、直径 <= k の最大のサブツリーを見つけ、そのサイズを n から差し引くことで構成されます。DPで解けます。

いくつかの有用な観察:

ノード v (T(v)) をルートとするツリーの直径は次のとおりです。

  • n に子がない場合は 1、
  • max(直径 T(c), 高さ T(c) + 1) 子 c が 1 つの場合、
  • v のすべての子 c に対して max(max(直径 T(c))、v のすべての子 c1、c2 に対して max(高さ T(c1) + 高さ T(c2) + 2)、c1 != c2)

ツリーのサイズとバウンディング ツリーの直径を最大化することに関心があるため、上記をひっくり返して、各サブツリーの制限を提案できます。

  • v をルートとする任意のツリーの場合、対象のサブツリーの深さは最大で k です。
  • n が T(v) のノードであり、v から <= k 離れた子がない場合、その最大サイズは 1 です。
  • n に 1 つの子 c がある場合、直径 <= k の T(n) の最大サイズは最大サイズ T(c) + 1 です。

トリッキーなビットです。n に複数の子がある場合、使用可能な深さを各子に割り当てた結果、可能なすべてのツリー サイズを見つける必要があります。たとえば、深さ 3、k = 7 にいるとします。4 つの深さで遊ぶことができます。3 人の子供がいる場合、4 つすべてを子供 1 に、3 を子供 1 に、1 を子供 2 に、2 を子供 1 に、1 を子供 2 と 3 に、というように割り当てることができます。直径 k を超えてはなりません。これは、ローカル DP で行うことができます。

各ノードに必要なのは、maxSize(d) を計算することです。これは、直径 <= k で深さ d までのノードをルートとするツリーの最大サイズを示します。0 個と 1 個の子を持つノードは、上記のように簡単に計算できます (たとえば、子が 1 つの場合、v.maxSize(i) = c.maxSize(i - 1) + 1、v.maxSize(0) = 1)。 . 2 つ以上の子を持つノードの場合、dp[i][j] を計算します。これにより、最大で j の深さを占める i 番目の子までを使用して、k 直径にバインドされたツリーの最大サイズが得られます。再帰は dp[i][j] = max(child(i).maxSize(m - 1) + dp[i - 1][min(j, k - m)] で、m は 1 から j までです。 i][0] = 1. これは、i 番目の子に 1 から j の深さを与えてみて、前のノードに利用可能な深さの残りを与える. 「利用可能な深さの残り」は j の最小値であり、深さ私たちは、またはk - m、子 i に与えられた深さ + 残りに与えられた深さは k を超えることができないためです。dp の最後の行の値をこのノードの maxSize テーブルに転送します。深さが制限された DFS を使用して上記を実行すると、必要なすべての maxSize エントリが正しい順序で計算され、ノード v の答えは v.maxSize(k) になります。次に、ツリー内のすべてのノードに対してこれを 1 回実行すると、見つかった最大値が答えになります。

説明が雑で申し訳ありません。考えるのが難しく、説明するのが難しかったです。いくつかの簡単な例を見てみると、より明確になるはずです。複雑さは計算していませんが、n は小さく、Scala ではすべてのテスト ケースを 0.5 から 1 秒で通過しました。

于 2013-03-06T06:11:16.990 に答える
2

私が気付くことができるいくつかの基本的なこと（おそらく他の人には非常に明白です）：1。与えられた2つの頂点の間で可能なルートは1つだけです。2.最も遠い頂点は、出力エッジが1つしかない頂点になります。

今問題を解決するために。

  1. まず、エッジが1つしかない頂点のセットから始めて、EDGE []と呼び、EDGE[]の頂点間の距離を計算します。これにより、（EDGE [i]、EDGE [j]、distance）の値のペアが得られます

  2. 距離がKより大きいEDGEのすべての頂点ペアについて、DO EDGE [i] .occur ++、EDGE [i] .distance = MAX（EDGE [i] .distance、distance）EDGE [j] .occur ++、EDGE [ j] .distance = MAX（EDGE [j] .distance、distance）

  3. EDGE []で、max（occur）でマークしたものからmax（distance）を持つ候補を検索します。

  4. すべてのエッジ頂点ペアの距離がK以下になるまで繰り返します

于 2013-02-20T07:27:09.190 に答える