3

我使用贪心算法和回溯算法实现了回溯算法。回溯算法如下：

MIS(G= (V,E): a graph): largest set of independent vertices
1:if|V|= 0
then return .
3:end if
if | V|= 1 
then return V
end if
pick u ∈ V
Gout←G−{u}{remove u from V and E }
Gn ← G−{ u}−N(u){N(u) are the neighbors of u}
Sout ←MIS(Gout)
Sin←MIS(Gin)∪{u}
return maxsize(Sout,Sin){return Sin if there’s a tie — there’s a reason for this.
 }

贪心算法是迭代地选择度数最小的节点，将其放入MIS中，然后将其及其邻居从G中删除。

在边存在的概率为 0.5 的不同图形大小上运行算法后，我凭经验发现与贪心算法相比，反向跟踪算法总是找到更小的最大独立集。这是预期的吗？

4

2 回答 2

0

你的解决方案很奇怪。回溯通常用于是/否问题，而不是优化。您编写的算法在很大程度上取决于您如何选择u. 它绝对不是回溯，因为你从不回溯。

可以通过多种方式解决此类问题，例如：

  • 基因编程，
  • 详尽的搜索，
  • 解决对偶图问题（最大团问题）。
于 2013-05-28T23:01:06.700 回答
0

根据Wikipedia，这是一个 NP 难题：

A maximum independent set is an independent set of the largest possible size for a given graph G.
This size is called the independence number of G, and denoted α(G).
The problem of finding such a set is called the maximum independent set problem and is an NP-hard optimization problem.
As such, it is unlikely that there exists an efficient algorithm for finding a maximum independent set of a graph.

因此，为了找到图的最大独立集，您应该测试所有可用状态（使用其时间复杂度为指数的算法）。所有其他更快的算法（如贪心算法、遗传算法或随机算法）都找不到确切的答案。他们可以保证找到一个最大的独立集，但不是最大的独立集。

总之，我可以说您的回溯方法较慢且准确；但贪心方法只是一种近似算法。

于 2019-05-23T12:00:42.677 回答