2

在我最近的采访中，我被问到以下问题：有一个没有循环的双向图 G。每个边缘都有一些重量。还有一组节点 K 应该彼此断开（通过删除一些边）。K集合中任意两个节点之间只有一条路径。目标是最小化移除边的总权重，并将所有节点（从集合 K）彼此断开。

我的方法是为 K 集中的每个节点运行 BFS，并确定来自 K 的所有节点对之间的所有路径。所以我将拥有一组路径（每条路径都是一组边）。我的下一步是应用动态规划方法来找到移除边缘的最小总重量。在这里我卡住了。您能否帮助我（直接指导我）应该如何完成 DP。

谢谢。

4

2 回答 2

2

这听起来像树中的多路切割问题，假设“双向”图​​就像一个无向图。它可以通过简单的动态规划在多项式时间内求解。参见 Chopra 和 Rao：“ On the multiway cut polyhedron ”，Networks 21(1):51–89, 1991。另请参见这个问题。

于 2012-11-06T22:52:35.683 回答
2

这个问题可以使用不相交的集合来解决。在这个问题中，您需要像森林一样设置每个顶点。然后，通过图中的边连接属于两个不同集合的顶点，使得 -

1）如果集合中的一个包含在k个节点集合中提到的节点，则该节点成为代表元素。

2）如果两个集合都包含不需要的节点（节点存在于k个节点集合中），则在两个集合中找到最小权重边并进行比较，然后将其中最小的一个与要连接的边进行比较并找到最低。然后删除我们找到的边，这样它们就没有路径存在了。

3）如果集合中没有一个包含不需要的节点，则将一个集合连接到另一个集合。

通过这种方式，您可以在 O(nlogn) 量级的非常好的时间复杂度中找到被破坏边缘的最小总权重。你的方法也行得通，但在时间复杂度方面证明是昂贵的。

这是完整的代码 - (GameAlgorithm.cpp) https://github.com/KARTHEEKCIC/RoboAttack

于 2017-04-14T17:58:19.483 回答