使用贪婪算法寻找最小独立支配集 [英] Finding minimum indepedent dominating set using a greedy algorithm

问题描述

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

该算法使用蛮力方法:

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

对于少量节点而言，这没有什么区别，但是对于大量节点，程序确实很慢.

有没有其他方法可以使它运行得更快?

谢谢

解决方案

不幸的是，找到最小的独立控制集的问题是NP-complete.因此，任何已知的，完善的算法都是无效的.

一种可能的方法是使用不完整的算法(即本地搜索).例如，已知以下算法具有近似(1 + log | V |)的因子:

1.选择一个具有最大邻居数的节点，然后将其添加到主导集中.
2.从图中删除该节点及其所有邻居.
3.重复直到图中没有其他节点.

I developed an algorithm that finds the minimum independent dominating set of a graph based on a distance constraint. (I used Python and NetworkX to generate graphs and get the pairs)

The algorithm uses a brute force approach:

• Find all possible pairs of edges
• Check which nodes satisfy the distance constraint
• Find all possible independent dominating sets
• Compare the independent dominating sets found and find the minimum dominating set

For small number of nodes it wouldnt make a difference but for large numbers the program is really slow.

Is there any way that I could make it run faster using a different approach?

Thanks

解决方案

Unfortunately, the problem of finding the minimum independent dominating set is NP-complete. Hence, any known algorithm which is sound and complete will be inefficient.

A possible approach is to use an incomplete algorithm (aka local search). For example, the following algorithm is known to have a factor (1 + log|V|) approximation:

1. Choose a node with the maximal number of neighbors and add it to the dominating set.
2. Remove the node and all of it's neighbors from the graph.
3. Repeat until there are no more nodes in the graph.

这篇关于使用贪婪算法寻找最小独立支配集的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！