8

これは、Vazirani による Algorithms book の問題です。

この問題への入力は、エッジに整数の重みを持つツリー T です。重みは、負、ゼロ、または正のいずれかです。T で最短の単純なパスを見つけるための線形時間アルゴリズムを与えます。パスの長さは、パス内のエッジの重みの合計です。頂点が繰り返されない場合、パスは単純です。パスの終点は制約されていないことに注意してください。

ヒント: これは、ツリー内で最大の独立集合を見つける問題と非常によく似ています。

この問題を線形時間で解決するにはどうすればよいですか?

これが私のアルゴリズムですが、深さ優先と何ら変わらないので、線形時間であるかどうか疑問に思っています:

  1. トラバース ツリー (深さ優先)
  2. インデックス (ノード) を保持する
  3. 値を追加します
  4. (1) ツリーの終わりまで行う
  5. 合計を比較し、パスと合計を出力します

この問題はこのトピックに似ていますが、特定の答えはありません。

4

1 に答える 1

6

この問題は、最小和部分列問題とほとんど同じであり、動的計画法によって同様の方法で解くことができます。

DF 検索を使用して、次の配列を計算します。

dw1[i] = minimum sum achievable by only using node i and its descendants.
pw1[i] = predecessor of node i in the path found for dw1[i].
dw2[i] = second minimum sum achevable by only using node i and its descendants,
         a path that is edge-disjoint relative to the path found for dw1[i].

これらを計算できたら、min(dw1[k], dw1[k] + dw2[k])すべて引き継いでkください。これは、パスが次の基本的な形状のいずれかを取るためです。

  k              k
  |     or     /   \
  |           /     \
  |

これらはすべて、私たちが取っている金額によってカバーされています。

dw1 の計算

ルート ノードから DFS を実行します。DFS で、現在のノードとその親ノードを追跡します。各ノードで、その子が であると仮定しますd1, d2, ... dk。それからdw1[i] = min(min{dw1[d1] + cost[i, d1], dw1[d2] + cost[i, d2], ..., dw1[dk] + cost[i, dk]}, min{cost[i, dk]})。dw1[i] = 0葉ノードに設定します。pw1[i]選択した前任者で更新することを忘れないでください。

dw2 の計算

ルート ノードから DFS を実行します。に対して行ったのと同じことを行いますdw1。ただし、ノードiからその子の 1 つに移動する場合kは、更新するdw2[i]場合にのみpw1[i] != k. ただし、すべての子に対して関数を再帰的に呼び出します。擬似コードでは次のようになります。

df(node, father)
    dw2[node] = inf
    for all children k of node
        df(k, node)

        if pw1[node] != k
            dw2[node] = min(dw2[node], dw1[k] + cost[node, k], cost[node, k])
于 2011-02-12T11:14:23.027 に答える