performance - 回溯对比贪心算法最大独立集

Question

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

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 的不同图大小上运行算法后，我凭经验发现反向跟踪算法总能找到比贪心算法更小的最大独立集。这是预期的吗？

Answer 1

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

这个问题可以通过多种方式解决，例如:

• 遗传编程，
• 详尽搜索，
• 解决对偶图问题(最大团问题)。