研究工作也许是我们培训中最有趣的部分。 我们的想法是在大学期间尝试自己选择的方向。 例如，软件工程和机器学习领域的学生经常去公司（主要是 JetBrains 或 Yandex，但不仅限于）进行研究。
在这篇文章中，我将讨论我的计算机科学项目。 作为我工作的一部分，我研究并付诸实践了解决最著名的 NP 难题之一的方法： 顶点覆盖问题.
如今，一种解决 NP 难题的有趣方法正在快速发展——参数化算法。 我将尽力让您加快速度，告诉您一些简单的参数化算法，并描述一种对我帮助很大的强大方法。 我在PACE挑战赛上展示了我的结果：根据公开测试的结果，我的解决方案获得了第三名，最终结果将于1月XNUMX日揭晓。
关于我
我叫瓦西里·阿尔费罗夫，现在即将在圣彼得堡国立研究大学高等经济学院读完三年级。 我从学生时代起就对算法感兴趣，当时我在莫斯科第 179 学校学习并成功参加了计算机科学奥林匹克竞赛。
有限数量的参数化算法专家进入酒吧......
例子取自书本
想象一下，您是一个小镇的酒吧保安。 每周五，半个城市的人都会来到你的酒吧放松，这给你带来了很多麻烦：你需要把吵闹的顾客赶出酒吧，以防止打架。 最终，您厌倦了并决定采取预防措施。
由于您的城市很小，您可以准确地知道哪对顾客在酒吧里在一起时可能会打架。 你有一份清单吗 n 今晚会来酒吧的人。 您决定将一些镇民拒之门外，以免引起任何人打架。 同时，你的老板不想损失利润，如果你不让超过 k 人。
不幸的是，你面前的问题是一个经典的 NP 难题。 你可能知道她是 ，或作为顶点覆盖问题。 对于此类问题，一般情况下，没有算法可以在可接受的时间内工作。 准确地说，未经证实且相当强的假设ETH（指数时间假说）说这个问题无法及时解决 ，也就是说，你想不出还有什么比完整搜索更好的了。 例如，假设有人要来你的酒吧 N = 1000时 人类。 那么完整的搜索将是 大约有选项 - 疯狂的数量。 幸运的是，你的管理层给了你一个限制 k = 10，因此需要迭代的组合数量要少得多：十个元素的子集数量为 。 这样虽然好一些，但即使在强大的集群上，也不是一日之数。
为了消除酒吧访客之间关系紧张的情况下打架的可能性，您需要将鲍勃、丹尼尔和费多拒之门外。 不存在只留下两个人的解决方案。
这是否意味着是时候让步并让所有人参与了？ 让我们考虑其他选择。 嗯，例如，你不能只让那些可能与很多人打架的人进来。 如果有人至少可以与 k+1 另一个人，那么你绝对不能让他进来——否则你就得把所有人都拒之门外 k+1 镇民，他可以跟他们打架，这肯定会让领导不高兴。
愿你按照这个原则抛弃所有你能抛弃的人。 然后其他人都可以战斗 k 人们。 把他们扔出去 k 伙计，你能阻止的无非就是 冲突。 这意味着如果有超过 如果一个人至少卷入了一场冲突，那么你当然无法阻止所有冲突。 当然，因为你肯定会让完全不冲突的人进来，所以你需要检查两百人中十个人的所有子集。 大约有 ，而这个数量的操作已经可以在集群上整理出来了。
如果你可以安全地带走根本没有冲突的人，那么那些只参与一次冲突的人呢？ 事实上，他们也可以通过关上对手的大门来让他们进来。 事实上，如果爱丽丝只与鲍勃发生冲突，那么如果我们把爱丽丝排除在他们两个之外，我们就不会输：鲍勃可能有其他冲突，但爱丽丝肯定没有这些冲突。 而且，不让我们俩进去也没有意义。 进行此类操作后，不再有任何剩余 命运未卜的客人：我们只有 冲突，每个冲突都有两个参与者，并且每个冲突至少涉及两个人。 所以剩下的就是整理 选项，这可以很容易地在笔记本电脑上考虑半天。
事实上，通过简单的推理，您可以实现更有吸引力的条件。 请注意，我们肯定需要解决所有争议，即从每一对冲突的人中，选择至少一个我们不会让其进入的人。 让我们考虑以下算法：采取任何冲突，我们从中删除一个参与者并从其余参与者递归地开始，然后删除另一个参与者并同样递归地开始。 由于我们每一步都将某人扔出去，因此这种算法的递归树是深度二叉树 k，所以总的来说，该算法的工作原理是 哪里 n 是顶点的数量，并且 m - 肋骨数量。 在我们的例子中，大约是一千万，不仅在笔记本电脑上，甚至在手机上也可以瞬间计算出来。
上面的例子是一个例子 参数化算法。 参数化算法是及时运行的算法 f(k) 聚(n)哪里 p - 多项式， f 是任意可计算函数，并且 k - 一些参数，很可能比问题的规模小得多。
这个算法之前的所有推理都给出了例子 内核化 是创建参数化算法的通用技术之一。 核化是将问题规模减小到受参数函数限制的值。 由此产生的问题通常称为内核。 因此，通过对顶点度数的简单推理，我们获得了顶点覆盖问题的二次核，并通过答案的大小进行参数化。 您还可以为此任务选择其他设置（例如 LP 上方的顶点覆盖），但这是我们将讨论的设置。
步伐挑战
竞争 （参数化算法和计算实验挑战赛）诞生于 2015 年，旨在在参数化算法和实际用于解决计算问题的方法之间建立联系。 前三场比赛致力于寻找图的树宽度（），寻找斯坦纳树（）并搜索一组割环的顶点（）。 今年，您可以尝试解决的问题之一是上述顶点覆盖问题。
这项比赛每年都越来越受欢迎。 如果你相信初步数据的话，今年就有 24 支队伍参加了仅解决顶点覆盖问题的比赛。 值得注意的是，比赛持续的时间不是几个小时甚至一周，而是几个月。 团队有机会研究文献，提出自己的原创想法并尝试实施。 从本质上讲，本次竞赛是一个研究项目。 最有效的解决方案的想法和获奖者的颁奖将与会议同时举行 （参数化和精确计算国际研讨会）作为欧洲最大的年度算法会议的一部分 。 有关比赛本身的更多详细信息，请访问 ，往年的结果是 .
解决方案
为了解决顶点覆盖问题，我尝试使用参数化算法。 它们通常由两部分组成：简化规则（理想情况下会导致内核化）和分割规则。 简化规则是在多项式时间内对输入进行预处理。 应用此类规则的目的是将问题简化为等效的更小的问题。 简化规则是算法中最昂贵的部分，应用这部分会导致总运行时间 而不是简单的多项式时间。 在我们的例子中，分割规则基于以下事实：对于每个顶点，您需要将其或其邻居作为答案。
一般方案是这样的：我们应用简化规则，然后选择一些顶点，并进行两次递归调用：在第一个中，我们将其作为响应，在另一个中，我们将其所有邻居作为响应。 这就是我们所说的沿该顶点的分裂（分支）。
下一段将对该方案添加一个补充。
拆分（早午餐）规则的想法
让我们讨论如何选择发生分裂的顶点。
从算法的角度来看，其主要思想是非常贪婪的：让我们取一个最大度数的顶点并沿着它进行分割。 为什么看起来更好？ 因为在递归调用的第二个分支中我们会通过这种方式删除很多顶点。 您可以指望剩下一个小图表，我们可以快速处理它。
这种方法结合已经讨论过的简单内核化技术，很好地展示了自己，并解决了数千个顶点大小的一些测试。 但是，例如，它不适用于三次图（即每个顶点的度数为三的图）。
还有另一个基于相当简单的想法的想法：如果图是断开的，则其连接组件上的问题可以独立解决，并在最后结合答案。 顺便说一句，这是该方案中承诺的一个小修改，这将显着加快解决速度：以前，在这种情况下，我们致力于计算组件响应的时间乘积，但现在我们致力于总和。 为了加速分支，您需要将连通图变成断开图。
怎么做？ 如果图表中有一个连接点，你就需要努力去争取它。 铰接点是一个顶点，当被删除时，图形将失去其连接性。 可以使用经典算法在线性时间内找到图中的所有连接点。 这种方法显着加快了分支速度。
当删除任何选定的顶点时，图形将分成连接的组件。
我们会这样做，但我们想要更多。 例如，在图中查找小的顶点切割并沿其顶点进行分割。 据我所知，找到最小全局顶点切割的最有效方法是使用 Gomori-Hu 树，它是在立方时间内构建的。 在 PACE 挑战赛中，典型的图大小为数千个顶点。 在这种情况下，需要在递归树的每个顶点执行数十亿次操作。 事实证明，在规定的时间内解决问题根本不可能。
让我们尝试优化解决方案。 任何构造最大流的算法都可以找到一对顶点之间的最小顶点割。 你可以让它进入这样的网络 ，实际上它的工作速度非常快。 我怀疑理论上可以证明对运行时间的估计 ，这已经是可以接受的了。
我多次尝试寻找随机顶点对之间的切割，并采取最平衡的一个。 不幸的是，这在开放 PACE 挑战测试中产生了糟糕的结果。 我将其与最大程度分割顶点的算法进行了比较，并在下降深度限制的情况下运行它们。 试图以这种方式找到切点的算法留下了更大的图。 这是因为切割结果非常不平衡：删除了 5-10 个顶点后，只能分割出 15-20 个顶点。
值得注意的是，有关理论上最快算法的文章使用更先进的技术来选择分裂顶点。 此类技术的实现非常复杂，并且在时间和内存方面的性能通常很差。 我无法确定哪些是可以接受的实践。
如何应用简化规则
我们已经有了内核化的想法。 让我提醒您：
- 如果存在孤立顶点，请将其删除。
- 如果存在度数为 1 的顶点，则将其删除并取其邻居作为响应。
- 如果至少有一个度数的顶点 k+1， 把它收回。
对于前两个，一切都很清楚，对于第三个，有一个技巧。 如果在关于酒吧的漫画问题中，我们给出的上限为 k，那么在 PACE Challenge 中你只需要找到最小尺寸的顶点覆盖即可。 这是搜索问题到决策问题的典型转变；通常两类问题之间没有区别。 在实践中，如果我们为顶点覆盖问题编写求解器，可能会有所不同。 例如第三点。
从实施的角度来看，有两种方法可以进行。 第一种方法称为迭代深化。 如下：我们可以从下面对答案的一些合理约束开始，然后使用这个约束作为对上面答案的约束来运行我们的算法，而递归不会低于这个约束。 如果我们找到了某个答案，那么它肯定是最优的，否则我们可以将此限制增加一并重新开始。
另一种方法是存储一些当前的最佳答案并寻找较小的答案，找到时更改此参数 k 以更好地切断搜索中不必要的分支。
经过几次夜间实验后，我决定将这两种方法结合起来：首先，我在搜索深度上进行某种限制（选择它，以便与主要解决方案相比花费的时间可以忽略不计）运行我的算法，并使用最佳的找到的解决方案作为答案的上限 - 即同一件事 k.
2 次顶点
我们已经处理了 0 度和 1 度的顶点。 事实证明，这可以通过 2 度的顶点来完成，但这需要对图中进行更复杂的操作。
为了解释这一点，我们需要以某种方式指定顶点。 我们将度数为 2 的顶点称为顶点 v，及其邻居 - 顶点 x и y。 接下来我们会讲两个案例。
- 何时 x и y - 邻居。 然后你就可以回答 x и y和 v 删除。 确实，从这个三角形中至少需要取两个顶点作为回报，如果我们取绝对不会输 x и y：他们可能还有其他邻居，并且 v 他们不在这里。
- 何时 x и y - 不是邻居。 然后指出所有三个顶点都可以粘合成一个。 这个想法是，在这种情况下，存在一个最佳答案，其中我们采取 v，或两个顶点 x и y。 此外，在第一种情况下，我们将不得不采取所有邻居的响应 x и y，但在第二个中则没有必要。 这恰好对应于我们不采用粘合顶点作为响应以及采用粘合顶点作为响应时的情况。 只需要注意，在这两种情况下，此类操作的响应都会减少 XNUMX。
值得注意的是，这种方法很难在公平的线性时间内准确实现。 粘合顶点是一项复杂的操作；您需要复制邻居列表。 如果不小心这样做，您可能会得到渐近次优的运行时间（例如，如果您在每次粘合后复制大量边）。 我决定从 2 度顶点找到整个路径，并分析一堆特殊情况，例如来自此类顶点或除一个顶点之外的所有此类顶点的循环。
此外，该操作必须是可逆的，以便当从递归返回时我们将图恢复到其原始形式。 为了确保这一点，我没有清除合并顶点的边列表，然后我只知道哪些边需要去哪里。 这种图的实现也需要准确性，但它提供了公平的线性时间。 而对于几万条边的图，它可以放入处理器缓存中，这在速度上有很大的优势。
线性核
最后是内核中最有趣的部分。
首先，回想一下，在二部图中，可以使用以下方法找到最小顶点覆盖 。 为此，您需要使用算法 为了找到那里的最大匹配，然后使用定理 .
线性核的思想是这样的：首先我们将图分叉，即不是每个顶点 v 让我们添加两个峰值 и ，而不是每条边 紫外线 让我们添加两根肋骨 и 。 生成的图将是二分图。 让我们找到其中的最小顶点覆盖。 原始图的某些顶点会到达那里两次，有些只会到达一次，有些则永远不会。 Nemhauser-Trotter 定理指出，在这种情况下，我们可以删除未命中一次的顶点，并收回命中两次的顶点。 此外，她说，对于剩余的顶点（那些击中一次的顶点），您需要至少取一半作为答案。
我们刚刚学会离开不超过 2k 峰事实上，如果余数答案至少是所有顶点的一半，那么顶点总数不会多于 2k.
在这里我能够向前迈出一小步。 很明显，以这种方式构建的内核取决于我们在二部图中采用的最小顶点覆盖类型。 我想取一个，以便剩余顶点的数量最少。 以前，他们只能及时做到这一点 。 我当时想出了这个算法的实现 ，因此，可以在每个分支阶段的数十万个顶点的图中搜索该核。
导致
实践表明，我的解决方案在数百个顶点和数千个边的测试中效果良好。 在这样的测试中，很可能会在半小时内找到解决方案。 原则上，如果图具有足够多的高阶顶点（例如，阶数 10 及更高），则在可接受的时间内找到答案的概率会增加。
要参加比赛，必须将解决方案发送至 。 根据那里提供的信息判断 ，我的解决方案在公开测试中在二十个中排名第三，与第二有很大差距。 老实说，目前还不完全清楚比赛本身如何评估解决方案：例如，我的解决方案通过的测试比第四名的解决方案要少，但在通过的测试中，它的运行速度更快。
封闭测试的结果将于 XNUMX 月 XNUMX 日公布。
来源： habr.com