查找访问树的所有节点的最低成本

Question

给定树的根,其中每个边具有相关的成本.找到访问树的每个节点的最低成本.

我想到的一个递归解决方案是:

1. 当节点是叶返回0时的基本情况.
2. 对于节点的每个子节点c递归地计算成本.
3. 将所有这些成本加起来,并且从节点到子节点两次添加边缘成本两次(因为我们需要回溯).
4. 减去具有最大成本的孩子的边缘成本.("贪婪" - 我们不想从具有最大成本的孩子回溯).

这种方法是否正确？

有没有更好的方法来解决这个问题？

Answer 1

1. 从节点访问所有子树并返回到节点,它将花费edges * 2属于该子树的所有子树.
2. 所以我们应该在树中找到路径成本最大的路径.我们只是通过路径,如果我们遇到一些不在路径中的节点,我们只是访问它并返回.因此路径中的边将只访问一次,剩余边将访问两次.
3. 如何找到最高成本的路径？因为它是一棵树,你可以递归地找到它.

答案应该是:

sum(cost(edge)*2) - sum(edge which in the path)

我检查了你的解决方案,我认为这是错误的(如果我误解了你的解决方案,请发表评论):

减去具有最高成本的孩子的边缘成本.("贪婪" - 我们>不想从具有最高成本的孩子回溯).

那个孩子将是一棵树,一些边缘必须访问两次.例如:

    A
   / \
  B   C
 / \
D   E

您无法访问该子树所有边一次访问所有节点.