世界上最简单有趣的算法

在这篇文章中，我想告诉你我认为可能是世界上最简单有趣的算法。

顶点覆盖问题。给定一个图，我们想要找到最小的顶点集合，使得每个边都被该集合覆盖。这意味着对于每条边，至少有一条或在其中。

顶点覆盖问题是NP完全的，这意味着很难(或不可能)找到该问题的多项式时间算法。

但我们能做的是找到问题的近似最优解。有一个漂亮而简单的算法，它可以找到一个大小保证在最优因子内的集合。

算法。为了构建我们的集合，我们反复找到一些尚未覆盖的优势，然后将和都添加到我们的集合中。这就是整个算法。

乍一看，这似乎是一个疯狂的算法。当我们只需要其中之一或为了覆盖边缘时，为什么我们要把AND都放进去呢？

这个问题的答案很简单。如果我们定义为顶点覆盖问题的最优解，则必须至少包含或中的一个。通过将的和放入我们的集合中，我们保证至少有一半的元素也会出现在我们的集合中。这意味着，一旦我们的算法完成，我们就可以保证。

一个挑战。这可能是世界上最简单、最有趣的算法(和分析)。但也可能不是。你认为如何？