python - 使用贪心算法寻找最小独立支配集

Question

我开发了一种算法，可以根据距离约束找到图的最小独立支配集。 (我使用 Python 和 NetworkX 生成图形并得到对)

该算法使用蛮力方法:

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

对于少量节点，它不会产生影响，但对于大量节点，程序真的很慢。

有什么方法可以使用不同的方法让它运行得更快？

谢谢

Answer 1

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

一种可能的方法是使用不完整的算法(也称为局部搜索)。例如，已知以下算法具有因子 (1 + log|V|) 近似值:

1. 选择一个邻居数最多的节点加入支配集。
2. 从图中删除节点及其所有邻居。
3. 重复直到图中不再有节点。