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

Question

我开发了一种算法，可以根据距离约束找到图的最小独立支配集。（我使用 Python 和 NetworkX 来生成图表并获取对）

该算法使用蛮力方法：

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

对于少量节点，它不会有所作为，但对于大量节点，程序真的很慢。

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

谢谢

Answer 1

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

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

1. 选择具有最大邻居数的节点并将其添加到支配集。
2. 从图中删除节点及其所有邻居。
3. 重复直到图中不再有节点。