algorithm - 等分断开二分图的顶点

Question

我得到了一个包含许多单独组件的图表。每个组件都是二分的。如何将顶点分配到两组A中B，使两组之间的差异最小？

例子：

1：1 -> 2 ->3 -> 4 -> 5

2：6 -> 7 -> 8

最好的解决方案是

A = {1, 3, 5, 7}

B = {2, 4 ,6, 8}

另一个（非最佳）解决方案是

A = {1, 3, 5, 6, 8}

B = {2, 4, 7}

当图有许多单独的二分组件时，您如何解决这个问题？

Answer 1

这是分区问题，稍加伪装。对于每个二分组件，取独立集合中元素数量的差（实际上是绝对值）。这是分区问题的输入。对于您的示例，它将是 [1,1] （来自 (3-2) 和 (2-1)。）

现在将解决方案转换回图形。对于编号以集合 S1 结尾的每个图，将其较大的集合放入A（并且较小的放入B），对于编号以 S2 结尾的每个图，将其较小的集合放入A（并且较大的放入B。）在您的示例中，解决方案是S1=[1] 和 S2=[1]。回到相关图表，您可以从示例中获得最佳解决方案。

Answer 2

这是分区问题的一种变体，它是 NP 完全的。

对于每个组件，找到任一侧的顶点数，例如 [m,n]，然后您必须决定是将 m 放入池 A 还是池 B，这样池 A 中的项之和与池中的项之和之间的差异池 B 是最小的。

存在通过动态编程以及 IPP 的变体来解决此类问题的现有技术。但是对于大量的组件，您注定要仅靠 NP 完整性。