使用贪婪算法寻找最小独立支配集

Question

我开发了一种算法，该算法基于距离约束找到图的最小独立支配集。 （我用Python和NetworkX生成图表，并获得对）

该算法采用蛮力方法：

• 找到所有可能的对边的
• 检查哪些节点满足距离约束
• 查找所有可能的独立支配组
• 比较找到的独立支配组并找到最小支配组

对于少数节点它不会有所作为，但是对于大量的程序来说非常慢。

有没有什么方法可以让我们使用不同的方法更快运行？

谢谢

Answer 1

不幸的是，找到最小独立支配集的问题是NP完全的。因此，任何已知的完善和完整的算法都是低效的。

一种可能的方法是使用不完整的算法（又称局部搜索）。例如，已知下列算法具有因子（1 + log | V |）近似值：

1.选择具有最大邻居数量的节点并将其添加到主导集合中。
2.从图中删除节点及其所有邻居。
3.重复直到图中没有更多节点。