Kyle's Notebook

如何用图论解决 Secret Santa 问题?(译)

Word count: 2.5kReading time: 8 min
2021/05/16

原文链接:How to solve the Secret Santa Problem using graph theory

如何用图论解决 Secret Santa 问题?

关于图论,哈密尔顿回路,NP 问题,回溯搜索问题。

每年我们家都会举办一次 Secret Santa 活动:随机分配接收者,使得每个人都会从一位匿名的圣诞老人处得到一份礼物。

因此需要开发一个简单的网站,每位家庭成员都可以在活动开始时注册,填写愿望清单并取得收件人的姓名。虽然许多网站或应用都可以达到这种效果,但开发自己的服务可便于对排序算法进行一些修改。每位参与者注册后,运行排序算法确定谁向谁赠送礼物。为了解决 Secret Santa 问题需要找到这种排序算法。

使用一个数组存放所有参与者。首先随机抽取第一名,假设名为 Bob。然后从初始数组中删除 Bob 并从中获得随机参与者。假设参与者名为 Alice,即 Bob 把礼物送给 Alice。然后从数组中删除 Alice,并得到一名随机参与者,该参与者将成为 Alice 礼物的接收者,等等。

重复以上过程直到数组为空,最后一位参加者将是第一位 Bob 的 Secret Santa,此时圣诞老人链完成。

这种算法被称为朴素算法,其每个步骤都是显而易见的,它模仿了人们从帽子或彩票机中获取代币的过程。在大多数情况下朴素算法不是最佳算法,并且性能不高,但是其工作方式非常简单,以至于朴素算法是最佳算法,具有 O(n) 时间复杂度和 O(1) 空间复杂度。

下一步是对原问题做出改动,并对算法添加一些附加条件(这就是需要自定义服务的原因)。 有时基于纯粹的随机可以得到一个 Secret Santa,却出于某种原因使它无法保密。 例如当 Santa 是我的妻子,就几乎无法将其保密了。

因此对原问题添加约束,例如 Alice 和 Bob 参加活动,但不想互相送礼物。此时需要将此数据添加到算法中并考虑这个约束。可以稍微修改算法:当需要为有约束条件的参与者(Bob)挑选接收者时,从参与者池中删除这些约束条件(Alice),然后像之前一样随机选择一位。

有了这种约束,朴素算法在某些情况下可能会失败。如果为 Bob 选择一位接收者是算法的最后一步,而 Alice 是池中剩下的唯一选择时应该怎么办?在这种情况下如果要满足所有约束,将没有合适的选项,因此没有解决方案。

img

最简单的解决方法是重启算法直到获得解决方案。如果没有限制则应该会很安全,实际上在服务的第一个版本中完全采用这种方式进行修复,其非常适合 10 个参与者和 2 个约束,并且一次运行即可找到解决方案。有时需要重新启动 1 或 2 次,但不会无限循环。

但这仅是对原问题粗糙的解决方案。要找到合适的算法来解决所有输入数据的问题,可能需要使用另一种形式表示数据。已知有一些参与者以及不想互赠礼物的参与者的约束条件,当已知一些对象以及它们之间的联系时,就该考虑使用图了。

img

上图中的节点是参与者,节点之间的边表明它们可以互相提供礼物。Bob 和 Alice 无法互赠礼物,因此他们之间没有直接相连。现在可以看到这种解决方案是基于图中的路径,它必须从任何节点开始,然后确切地遍历一次整图再回到起点,因此这意味着该路径实际上是一个循环。 穿过所有节点的路径曾经被称为哈密尔顿路径(Hamiltonian Path)。 因此该回路是哈密尔顿回路(Hamiltonian Path)。

这意味着 Secret Santa 本质上是哈密尔顿回路问题,可以在书中或网上找到正确的算法。

如何在图中找到哈密尔顿回路?

但 Google 的结果令人很失望,因为显然没有快速的算法可以在图中找到哈密尔顿路径或回路:这是一个 NP 问题(不确定性多项式问题),意味着没有多项式复杂度的算法。 NP 问题中最著名的(或者说是臭名昭著的)NP 问题是旅行商问题(简称 TSP):

给定一个城市列表以及每个城市两两之间的距离,找出遍历所有城市一次并回到起点的最短路径。

这种描述看上去就很熟悉,即需要只访问每个节点一次,然后返回到初始节点。基本上就是在说哈密尔顿回路。TSP 没有快速解决方法,在有关如何更快解决问题的科学论文中,有些人使用启发式算法来减少暴力搜索过程中的选项数量,有些人使用动态规划将其分解为子问题(这些子问题更容易解决)。

而解决 Secret Santa 问题的算法要容易得多了,其主要区别在于 TSP 问题需要一个最佳的哈密尔顿回路(最短或最优),而 Secret Santa 问题只要求任意的哈密尔顿回路。

要对 TSP 进行暴力破解,需要找到所有可能的回路并选择最佳的一条。可能的回路数量是阶乘计算的:将 1 到 N 之间的所有整数相乘。如果图中有 5 个节点,则将有 120 个循环需要暴力计算对于 10 个节点,将有3628800个结果。对于 20 个节点,则有 2432902008176640000 个。 而原问题要简单得多,图中有许多合适的回路,只需要找到第一个即可,因此暴力计算也不是很可怕的。

图中 Alice、Bob 及其朋友的哈密顿回路示例

这个算法目标是通过暴力计算在图中找到一个哈密尔顿回路。

  • 首先从一个随机节点开始,该节点有一些与之相连接的节点。

  • 随机选择一个邻居节点,如果该节点也已连接其它节点,再选择其中尚未被访问的一个等等。

  • 在某些步骤中,可以发现没有可选的节点:由于约束限制没有更多的边可选,或所有的邻居节点已经被访问过。

这看起来像是在使用朴素算法,而使用图,如何后退并选择另一个随机节点则清晰可见。如果退后一步但仍然没有要选择的节点,则再退一步,重复直到访问所有节点并返回第一个节点时循环完成。这种搜索算法被称为回溯搜索或深度优先搜索。可以看一个例子:

步骤 1:从 Alice 开始,随机选择下一个节点。得到节点 C。

步骤 2:节点 C 连接到 E,D,Bob 和 Alice。由于 Alice 已被使用因此排除,随机选择 E。

步骤 3:然后选择节点 D。

步骤 4:从 D 剩下的唯一节点是 Bob,所有其他节点已经被访问过。

步骤 5:路径包含所有节点,需要转到节点 Alice 并完成循环,但是 Bob 和 Alice 之间没有边,需要退后一步,所以回到 D。

步骤 6:只能在第 3 步从 D 转到 Bob,而且已经知道这条路并不能解决问题。因此需要再退一步并返回E。

步骤 7:这次从 E 转到 Bob。

步骤 8:现在唯一的可能是从 Bob 移到 D。

步骤 9:现在可以从 D 转到 Alice,循环完成,找到了解决方案。

如果发现一条死路,并且在多次回溯之后没有找到哈密尔顿回路成功地返回到第一个节点,则该图没有解决方案。由于需要暴力破解所有路径以验证没有合适的回路,这是这是最坏的情况(阶乘函数)。

但是正在为服务解决 Secret Santa 问题,这实际上是一项工程任务,而不是数学任务。如果约束太多,并且图中没有足够的边来找到合适的回路,算法可能会失败。

如果举办 Secret Santa 活动,那可能会很诡异,一些参与者认为他们不希望将几乎所有其他人都视为圣诞老人。可以在界面上添加一些限制,并定义每个参与者最多可以有 3 个约束。这对于每个人就已经足够,并且可防止该算法暴力计算数百万条路径。

在一些测试中,具有 3 个约束时算法有时会进行 1 或 2 次回溯,在大多数情况下它会为 N 个参与者在 N 个步骤中找到解决方案。约束数量越多情况就越差,例如有 100 个参与者,每个参与者有 50 个约束,则暴力计算有时需要 100 步,有时需要 400,000 次,有时需要1,500,000 次。

原问题已经可以解决,并且得到一个具有稳定排序算法的可运行服务。即使有成千上万的参与者,其运行速度也足够快,对于家庭活动而言这就已经足够了。基于此我们还了解了有关哈密尔顿回路,NP 问题和深度优先回溯搜索的知识。

CATALOG
  1. 1. 如何用图论解决 Secret Santa 问题?