python - 使用最少数量的组件形成节点集

Question

我有一个包含 n 个节点的图。我得到了图的 k 个分区，每个分区包含 m1、m2 ...mk 个节点。

我想从组件中找到一个子集，使得这些子集中的节点的并集给出图形的节点集。在这样做时，我想确保我使用所需的最少组件数。我正在为节点集和组件使用 python 列表。让我举个例子:

node set - [49,57,3,95,98,100,44,40]
components - [57, 49, 100, 44], [57, 3, 95, 44], [3, 95, 44], [95, 44], [98, 44], [100, 44], [44], [40]

因此，如果我选择组件 [49, 100, 44]、[57, 3, 95, 44] 和 [98, 44]。这些集合的联合给了我节点集。我还可以选择其他包含 4 个或更多组件的组合，但这是不希望的。 请有人帮忙!! 谢谢

编辑 - 我试图解决的原始问题具有以下限制:

1. 每个节点都根据其相关性进行编号*
2. 组件中连续节点的相关性之间的差异应大于给定值。 (节点的顺序很重要，在下一点提到)
3. 组件中节点的顺序应与它们在原始节点集中的顺序相同。

Answer 1

这个答案是基于假设你的“分区”或“组件”可以是节点集的任意子集，所以你的问题是set cover的优化形式，一个已知的 NP-hard 问题。对子集的任何约束都可能使其更易于处理，因此请将它们添加到问题中。

对于任何 NP-hard 问题都没有已知的多项式时间精确算法，除非 P==NP 否则不可能存在。 .

您基本上有两种选择，蛮力和近似。蛮力可能适用于较小的子集集，它只是尝试所有可能的解决方案，从最小的开始，一直持续到找到覆盖为止。

您的示例有 8 个子集，因此有 8 个大小为 1 的候选解决方案，(8*7)/(2!)=28 个大小为 2 的候选解决方案，以及 (8*7*6)/(3!)=大小为 3 的 56 个候选者。由于存在大小为 3 的解决方案，因此算法到此为止。这在计算上是非常可行的。您可以通过存储 N 个子集的并集并使用它们来计算 N+1 个子集的并集来节省一些时间。

正如 NP-hard 问题的精确解所预期的那样，时间随着问题的大小呈指数增长，因此它不会扩展到更大的问题。

或者，引用文章包含一个贪心近似算法。如果这些想法都不适合您，请考虑使用任何限制可接受方法的术语搜索“设置封面”。