树加重节点

Question

给定一棵树，其中节点有一个值（可以是负值），找到最大化路径中节点总和的路径。

我曾尝试使用动态编程技术获得解决方案，但无法突破。

Answer 1

我们将在每棵树叶开始的树上执行洪水填充算法，并在洪水填充期间发现的路径上运行maximum subsequence sum算法。这为每对叶子产生候选最大值;我们选择其中最大的一个作为我们的真实答案。这个解决方案需要O（n^2）个时间：有O（n）个叶子，我们做O（n）来做每个叶子上最大子序列和问题的填充版本，产生O（n^2）候选生产阶段的工作总量。然后，我们做O（n^2）工作，从我们生成的O（n^2）个候选中选择最大路径。

我将在Haskell中给出一个示例实现。一些进口的，你可以忽略大部分：

import Data.List 
import Data.Monoid 

为了简单起见，我们将代表我们的树为函数，给定一个节点，讲述了重量和邻居有什么可用。命名类型和术语时，我将使用w作为权重，n作为节点。

type Tree w n = n -> (w, [n]) 

这将是方便有一种方法来指代的路径，其重量：

type WeightedPath w n = (Sum w, [n]) 

在我们的路，我们将保留两项统计数据，即最大路径在当前结束节点，以及迄今为止我们所见过的最大路径。对于空树对应的“空白摘要”，我们也会有一个常量：没有路径和零权重。

data Summary w n = Summary 
    { endingHere  :: WeightedPath w n 
    , endingAnywhere :: WeightedPath w n 
    } 

emptySummary :: Num w => Summary w n 
emptySummary = Summary mempty mempty 

我们需要一个洪水填充算法。这很简单，虽然它通过“初始摘要”进行参数化，并且可以通过一个额外的加权节点来扩展摘要;这是因为我们将使用洪水填充算法来查找所有树叶并找到候选路径。我们需要注意的一个诀窍是确保我们不会回溯;我们跟踪nPrevious中的前一个节点（如果有）用于此目的。

flood :: Eq n => (w -> n -> s -> s) -> s -> Tree w n -> n -> [s] 
flood extend summary t = go Nothing summary where 
    go nPrevious summary nCurrent = case maybe id delete nPrevious ns of 
     [] -> [summary'] 
     ns -> ns >>= go (Just nCurrent) summary' 
     where 
     (w, ns) = t nCurrent 
     summary' = extend w nCurrent summary 

例如，我们可以通过让我们的“摘要”成为我们看到的最后一个节点来找到所有的叶子。如果树是空的，我们把我们的双手厌恶：

findLeaves :: Eq n => Tree w n -> n -> [n] 
findLeaves = flood (\w n s -> n) undefined 

我们可以通过一个节点链接的算法扩展候选路径的总结：

extend :: (Num w, Ord w, Ord n) => w -> n -> Summary w n -> Summary w n 
extend w n s = answer where 
    answer = s 
     { endingHere = max (0, []) ((Sum w, [n]) <> endingHere s) 
     , endingAnywhere = max (endingHere answer) (endingAnywhere s) 
     } 

此功能插槽分成我们的洪水填充算法很好地找到从特定节点开始候选路径：

findCandidates :: (Num w, Ord w, Ord n) => Tree w n -> n -> [Summary w n] 
findCandidates t n = findLeaves t n >>= flood extend emptySummary t 

顶级功能少了点洪水填充，并挑选最大的候选人。 （方法是任意的，因为他们在extend。）

maximalPath :: (Num w, Ord w, Ord n) => Tree w n -> n -> WeightedPath w n 
maximalPath t n = maximum . map endingAnywhere $ findCandidates t n 

让我们来看看它运行。我们将定义一个非常简单的样本树：它是一个星形树，节点0位于中心，节点1到5每个都连接到中心集线器。该中心的重量为-1，叶子根据它们是哪个节点加权1到5。

sampleTree :: Tree Int Int 
sampleTree 0 = (-1, [1..5]) 
sampleTree n = (n, [0]) 

在ghci中，我们可以发现，现在提供了一个树，树中的任何节点发现的最大路径：

> maximalPath sampleTree 0 
(Sum {getSum = 8},[5,0,4]) 

...它说，最大的一笔是8，它可以通过从外部节点5的路径行进到集线器节点0来实现，然后向外到节点4。

Answer 2

在树计算的每个节点：

1）与最大总和产生往复路径m该节点的任何后代到该节点。

2）具有最大和的路径可以在以该节点为根的子树中找到。

这些都可以使用在该节点的子节点处计算的值来计算。

如果（1）答案是在该节点处开始和停止的0长度路径，或者该节点处的值与任何孩子处的最大值（1）之和。

如果（2）答案是该节点的两个最大（1）值的和，减去该节点的值或来自任何孩子的最大（2）值。

您正在查找的值是根（2）的值，并且您可以添加额外的簿记来计算所涉及的路径。

这里的成本基本上是成本递归遍历树，当你从一个深度优先搜索返回做的大部分工作，所以我认为这是O（n）