algorithm - 归纳图中的顶点和 - 动态规划

Question

这是一道家庭作业题，我很乐意得到提示。

我有一个图 G，其中每个顶点 v 都有一个权重 w(v)。

S(G)是图中所有顶点的权重之和。

我需要找到一种算法来确定是否存在一组顶点 A，当 G[A](A 导出的 G 的图)是一棵树时，进行 S(G[A])=S(G[ V\A]).

我知道我应该遍历所有顶点，对它们的权重求和，然后尝试找到一棵达到该总和一半的树，但我不确定具体如何。我很确定它涉及动态规划。

非常感谢，

亚龙。

Answer 1

这不是一个真正的动态规划问题，它是一个搜索问题，关键是你要找到一棵树。

如果您仔细想想，您就会知道一两个算法可以告诉您最小生成树。按照同样的逻辑，您可以创建最大生成树。例如，如果你找到最大生成树并且它的权重之和小于 50%(或任何目标值)，那么你就知道这个问题是不可能的。

因此，按照此逻辑，您可以像在制作生成树一样继续前进，并拒绝超过目标数量的任何路径。这种策略被称为“分支定界”。让我们想象一下我们如何使用 Kruskal 算法做到这一点:

(1) 你会有一组树；从每个顶点开始作为一个单独的“树”

(2) 维护一个你还没有使用的边队列，从小到大排序

(3) 维护一堆你用过的边

(4) 寻​​找一条边(a) 连接两棵不同的树，并且(b) 两棵树的总和小于(或等于目标值，即一个解)

(4a) 如果不存在这样的边，则从堆栈中弹出一个值(移除边并分离树)并尝试队列中的下一个值

(4b) 如果确实存在这样的边，则添加边(合并两棵树)，将其压入堆栈并返回步骤 4

显然，有不同的方法可以完成相同的过程。例如，您也可以使用 Prim 算法的变体。