随机性如何改进算法

自计算机科学诞生之日起——这个领域以其有条不紊地解决问题的方法而闻名——随机性就发挥了重要作用。在世界上第一台通用电子计算机上运行的第一个程序使用随机性来模拟核过程。此后，类似的方法被用于天体物理学、气候科学和经济学。在所有这些情况下，在算法的某些步骤插入随机数有助于研究人员解释复杂过程可以发挥作用的多种方式的不确定性。

但是，将随机性添加到算法中也可以帮助您计算出明确判断真假问题的正确答案。 “你只要说‘好吧，让我放弃，让我不要尝试，让我随机挑选一些东西，’”滑铁卢大学的计算机科学家埃里克布莱斯说。 “对于太多的问题，这最终成为一种成功的方法。”

假设您要确定给定数字是质数（只能被 1 和它本身整除）还是合数（也可以被其他整数整除）。您可以简单地尝试将其除以所有可能的因数，但对于大数，这种“蛮力”方法和其他因式分解算法速度极慢。如果结果是合数，分解算法会告诉你它的除数的值——比你要求的更多的信息。如果您只关心数字的“素性”，是否有更高效的算法？

如果你使用随机性的话。基本思想可以追溯到 17 世纪法国数学家皮埃尔·德·费马 (Pierre de Fermat) 的一个结果，即他的“ 小定理”。费马考虑了两个整数——称它们为N和x 。他证明了如果N是质数，则x ^N − x始终是N的倍数，而不管x的值如何。等价地，如果x ^N − x不是N的倍数，则N不可能是质数。但逆命题并不总是正确的：如果^xN − x是N的倍数，则N通常但不总是素数。

要将费马小定理变成素数检验，只需取您感兴趣的N ，随机选择x ，然后将这两个数代入^xN − x 。如果结果不是N的倍数，那么您就完成了：您知道N绝对是合数。如果结果是N的倍数，则N可能是素数。现在选择另一个随机x并重试。在大多数情况下，经过几十次尝试，您几乎可以肯定地得出N是质数的结论。 “你这样做的次数很少，”布莱斯说，“不知何故，现在你出错的概率小于从现在到你看到答案时小行星撞击地球的概率。”

使用随机算法（基于对费马小定理的改进）的第一个素数测试开创了一个新时代。事实证明，与非随机或确定性算法相比，用随机算法解决一个又一个问题要容易得多。关键是将每个问题重新定义为可以在给定某个数字x的适当值的情况下快速解决的问题，然后证明几乎任何x都可以。即使研究人员不知道如何确定任何特定选择是否是一个好的解决方案，该解决方案仍然有效。数学家开玩笑说，这个不寻常的挑战就像大海捞针。

但这些成功让研究人员想知道为什么随机性应该有助于解决诸如素数测试之类的问题，这些问题都是关于寻找隐藏的、非随机的模式。 “这有点自相矛盾，”牛津大学计算机科学家Rahul Santhanam说。 “纯粹的随机性正在帮助你掌握解决问题的结构。”

1994 年，计算机科学家诺姆·尼桑 (Noam Nisan) 和 阿维·威格德森 (Avi Wigderson)通过证明随机性虽然有用但可能并非必需，帮助解决了这一困惑。他们证明了以下两件事之一必须是正确的：要么所有可以使用随机性有效解决的问题也有快速确定性算法，要么许多众所周知的难题实际上很容易。计算机科学家认为第二种可能性极小。

事实上，计算机科学家经常发现通过从随机版本开始然后“去随机化”它来开发确定性算法更容易。布朗大学计算机科学家Eli Upfal说：“一旦我有了它，我突然想到了一种非常明显的方法来让它具有确定性。” “但如果我不以随机方式将其视为概率问题，我可能不会想到它。”

在 Nisan 和 Wigderson 具有里程碑意义的证明之后将近 30 年，随机算法仍然一如既往地流行，因为去随机化可能很棘手，而确定性算法通常仅在原则上有效。直到 2002 年，三位研究人员才找到一种去随机化素性测试的方法，实际上他们的算法比最好的随机算法慢得多。对于其他问题，甚至不知道从哪里开始——最著名的算法有一个鸡和蛋的问题，你只能通过随机性来解决。

图论最近的突破就是这种情况。去年，三位计算机科学家开发了一种快速算法，用于通过图形（由线段连接的节点网络）找到最短路径，即使某些线段从总路径长度中减去而不是添加，该算法也能正常工作。他们的算法涉及通过删除某些段将图形转换为更简单的图形，解决简化图形的问题，然后考虑删除的段。他们可以证明，如果没有最短路径经过太多已删除的段，算法将运行得很快——否则，最后一步将花费太长时间。

但是如何决定首先删除哪些段呢？确定性地找到理想的一组细分不仅困难，而且是不可能的。该集合取决于最短的路径，这正是三位研究人员试图解决的问题。但即使他们找不到要删除的最佳片段集，他们也可以证明大多数随机选择都很好，这足以打破自我参照循环。在极少数情况下，算法做出了一个不幸的选择并在最后一步陷入困境，他们可以停止并再次运行它。

“随机性基本上是一种在不知道最佳解决方案的情况下确保最佳解决方案为真的方法，”新算法的作者之一亚伦伯恩斯坦说。

随机性在计算机科学中发现了无数其他用途，从密码学到​​博弈论再到机器学习。很有可能，它会留在这里。