10个听起来怪异但很酷的算法

你尝试过从三维离散标量场中提取多边形网格吗？

没有？

好吧，早在 1987 年，通用电气的两位程序员做到了——他们最终发明了 Marching Cubes 算法。这就是医生如何将医学扫描转化为可以挽救数百万人生命的 3D 模型的原因。

这就是算法的力量。

每当你通过代码指示机器解决问题时，你就是在设计一种将比特转化为意义的过程。 有些算法很快。有些很优雅。还有一些如此奇怪，它们感觉像是魔法。

在这篇文章中，我们将深入探讨十个最怪异、最聪明的算法——这些算法帮助在几毫秒内搜索数十亿行代码，从无到有生成无限地图，并将量子怪异转化为实用逻辑。

1、波函数坍缩

科学中最奇怪的事情之一是双缝实验：当你不观察时，粒子表现得像波；但当你观察时，它们会立即变成粒子。这很奇怪——而且出人意料地有用。

“波函数坍缩”这个概念听起来很抽象，但它已经被转化为一个非常实用的算法。

想象一下你在设计一个横向滚动的视频游戏地图。你想让这个世界感觉是手工制作的，但也希望它能够永远延续下去。你不能用手画一个无限的地图，所以选择程序化生成。

在开始时，地图上的每个瓦片都像是一种“波”——它还不是任何具体的东西。它是充满可能性的。但是随着玩家向前移动——观察世界——算法“坍缩”了这种不确定性。世界固化成特定的瓦片，但它这样做是根据你设定的规则进行的。道路连接，河流流向正确的地方，一切都感觉像是有意设计的。

这是一种带有目的性的随机性，所有这一切都没有使用任何生成式人工智能。这只是奇怪而美丽的逻辑。

2、扩散模型

人工智能真的很奇怪。

扩散模型——这是像 DALL·E 和 Stable Diffusion 这样的图像生成器背后的技术——基于热力学中的一个概念：扩散，其中粒子自然地从高浓度区域扩散到低浓度区域。

在机器学习中，这个过程被反转了。

不是从有序到混乱，而是算法从纯噪声开始——比如一张猫的图片——并学习如何逐步将其细化为有意义的图像。你从随机性（高熵）开始，最终得到清晰连贯的输出（低熵）。

但你需要一个模型来很好地完成这个任务。扩散算法分为两个阶段。

首先，在训练期间，模型会拿真实的图像并逐渐添加噪声，直到它们变得无法辨认。然后，它学习如何逆转这个过程——将其重构回连贯的图像。

对数百万张标记的图像进行这样的操作，你就得到了一个可以从头开始生成新图像的模型。太空中的猫。皮克斯风格的古罗马。超现实主义的牛油果椅子。你可以随意命名。

这需要大量的计算资源。但它不仅仅局限于图像。扩散已经在重塑我们生成音乐、音频的方式，接下来就是视频。

3、模拟退火

编程中最令人沮丧的部分之一是很少有一个正确的解决方案——只有一片尚可的解决方案，以及少数几个真正优秀的解决方案。有点像组织亚马逊仓库：有几十种方法可以做到，但在大规模上只有少数几种真正有意义。

模拟退火的名字来源于冶金学，在那里金属被反复加热和冷却以去除缺陷。同样的概念也适用于优化。你试图在一个充满局部高峰和山谷的混乱景观中找到最佳解决方案。

想象一下你在寻找山脉范围内的最高山峰。一个基本的爬山算法会让你停留在第一个看起来很有希望的小山丘上。但模拟退火更聪明。它从一个较高的“温度”开始，这意味着它可以自由探索——有时甚至接受较差的路径以逃离局部陷阱。随着温度逐渐下降，它变得更加挑剔，只接受最好的动作。

这里的关键在于探索与利用之间的权衡。它不仅在代码中有用——这也是学习编码的一个很好的隐喻。早期，你会在不同的语言、工具和框架之间跳来跳去。但最终，你会冷静下来，锁定目标，专精一门。

4、睡眠排序

不谈算法就无法提及排序——也许最荒谬但又聪明绝顶的算法是睡眠排序。

传统的排序算法，如快速排序或归并排序，使用分治策略递归地将数组分成子数组并高效地排序。但在 4chan 上，一位疯狂的天才提出了一个完全不同的方法。

以下是它的运作方式：对于数组中的每个数字，启动一个新的线程。每个线程休眠一定数量的毫秒，等于其值，然后打印出数字醒来时的值。因为较小的数字休眠的时间较短，它们会先被打印出来——从而产生排序的输出。

聪明之处在于？它跳过了所有通常的逻辑，将 CPU 的线程调度器变成了排序引擎。无需比较。无需递归。只需睡眠和打印。

但它的实用性很差。它在负数、重复值或大数值时会失效。它也很低效，创建一个线程对应于每个数字。并且它依赖于睡眠时间，而这并不准确。

睡眠排序既搞笑又无用——这是一个聪明并不总是有用的完美例子。

5、BOGO 排序

BogoSort 是一种玩笑算法：它随机打乱数组一次又一次，直到纯靠运气，结果是排序好的。它效率极低——就像靠猜测找到正确答案一样。

现在想象一下结合量子力学和多元宇宙的概念。理论上，如果所有可能的结果存在于无限的平行宇宙中，那么在某个宇宙中，你的数组已经是排序好的。

这项技术目前还没有实现，但“量子 BogoSort”可以通过同时创建所有这些可能性，然后瞬间坍缩到数组已排序的宇宙中——本质上让量子随机性为你完成工作。

当然，这只是科幻小说，不是计算机科学。我们无法随意观察或坍缩多元宇宙。但这是一个关于蛮力随机性被推向逻辑（和荒谬）极限的有趣思想实验。

6、BOID

这是我最喜欢的一个。我发现算法最酷的地方在于它们有时可以模仿自然。1986 年，Craig Reynolds 的 Boids 程序就是其中之一——它是最早的仿真人工生命之一，模仿鸟类群飞。但最令人惊叹的是它用了多么少的代码就能得到如此生动的东西。

每只鸟（或“boid”）遵循三条简单的规则：避免撞到邻居（分离）、与它们的方向对齐（对齐），并向群体中心移动（凝聚）。

就这么简单。没有人指挥。但当你模拟许多这些简单行为时，你会看到令人着迷的有机模式，它们像真正的鸟群一样变化和流动。

这里的美不在于代码——而在于它所产生的一切。这些复杂的群体动态不需要显式编程。它们只是发生。就像偶然发现了自然界去中心化协调的捷径。

7、Shor 算法

让人们能够锁住邮箱并用独特的签名签署信件的想法基于密码学中的一个重要概念：分解大数的难度。

大多数加密方法背后的保护机制依赖于这样一个简单的数学事实——将大数相乘很容易，但找出产品背后的两个原始质数——这个问题被称为质因数分解——它极其困难且耗时。

事实上，它如此困难，以至于你的笔记本电脑可能需要数万亿年才能暴力破解解决方案——除非，当然，我们开始使用量子计算机。量子计算机有可能比任何经典算法快得多地解决整数分解问题，这要归功于像 Shor 算法这样的算法。

Shor 算法可以比传统方法更快地将大数分解为其质因数。质因数分解本身很简单，但这个算法的工作原理才是真正的怪异之处。

Shor 算法的核心是量子力学概念，如量子比特、叠加态和纠缠态。这些使得量子计算机能够并行执行大规模计算，这是经典计算机无法接近的。

尽管该算法本身是合法的，但其实际应用仍处于早期阶段。事实上，迄今为止使用量子计算分解的最大数字仅为 21。IBM 最先进的量子系统 Q System One 在分解一个简单的数字 35 时失败了。

话虽如此，量子突破正在发生。最近，一个中国团队成功地使用量子计算机分解了一个巨大的数字，但他们使用的算法对更大数字的扩展性不佳，这意味着它尚未适用于一般用途。

然而，如果量子计算机足够强大，并且有人能想出如何将这些算法扩展到真正大的数字，预计会对网络安全领域造成严重破坏。一旦量子计算能够可靠地破解加密，我们当前的所有安全协议都可能面临风险。

8、Marching Cubes

在本文开头，我们提到了 Marching Cubes 算法——但值得深入探讨，因为它对可视化 3D 数据，尤其是在医学领域，是一个重大转折点。

想象一下你有一份人体的 3D 扫描，比如来自核磁共振成像。核磁共振不会给你一个 3D 模型，而是一大块数字——一个 3D 标量场。该场中的每个点都包含一个代表某种东西的值，比如组织密度或信号强度。这些数据在空间上是连续的，但我们需要将其转化为视觉的东西——一个表面、一个形状、计算机可以绘制的东西。

这就是 Marching Cubes 发挥作用的地方。该算法将这个 3D 场域逐小立方体地遍历。每个立方体由场中的八个相邻数据点形成。

现在这里的关键部分来了：每个点要么高于要么低于阈值（例如皮肤变为骨骼）。因此，每个角都会根据它是否位于你想要提取的表面上而分配一个 0 或 1。

这给出了一个 8 位数——每个小立方体有 256 种可能的组合。对于每种组合，都预先计算并存储在查找表中的一种特定三角形图案。这些三角形用于近似穿过该立方体的表面。因此，与其每次都要计算复杂的几何图形，算法只需查找即可。

通过重复这个过程——逐个立方体遍历，插入值，查找形状——算法逐渐构建出完整的 3D 网格。你得到的是一个平滑的表面，它代表了扫描中不同材料之间的边界，比如骨骼和组织。

在 1980 年代，这是一项突破性进展，因为它将平面的 MRI 或 CT 扫描切片转化为医生可以旋转、放大和分析的实际 3D 模型。即使在今天，Marching Cubes 仍在许多领域使用——从医学成像和地质学到游戏中的程序生成。

9、实用拜占庭容错

在现代计算中，我们经常处理分布式系统——分布在云中的计算机网络。这引出了分布式计算中最著名的问题之一：拜占庭将军问题。

想象一下：拜占庭军队的几位将军正包围一座城市。他们需要同时进攻才能获胜。但他们只能通过发送信息进行通信，其中一些将军可能是叛徒试图破坏计划。也许一个决定睡懒觉，或者更糟——谎报进攻时间。如果只有一个将军失败或恶意行事，整个战略可能会崩溃。

计算机也面临着同样的挑战。在分布式系统中，某些机器可能会崩溃、变慢，甚至被黑客入侵。当无法信任所有人时，其余网络如何达成一致？

这就是像 PBFT（Practical Byzantine Fault Tolerance）这样的共识算法的用武之地。PBFT 设计用于处理这些类型的故障。它通过一个节点提议一个动作并通过广播“预准备”消息来开始。其他节点响应确认。一旦一定数量的节点（通常是三分之二或更多）同意，他们就会达成共识。最后，原始节点发送“提交”消息，告诉每个人执行该动作。即使多达三分之一的节点出现故障或恶意行为，系统仍然可以正常运行。

像 PBFT 这样的算法是区块链系统和分布式云数据库的支柱，帮助它们保持一致性并值得信赖——即使出现问题。

10、Boyer Moore

最后，我们来到了一个老式的算法，它默默地推动了一些我们今天使用的最快工具——比如 grep。它叫做 Boyer-Moore 字符串搜索，最近让我大开眼界，因为它反直觉：文本越长，它就越快。

以下是它的运作方式。大多数基本的搜索算法从左到右逐字符检查。但 Boyer-Moore 反转了这一点——它从搜索模式的右侧开始扫描，并使用两个聪明的技巧来跳过大量文本。想象一下你在一大段文本中寻找单词“needle”。

1. 坏字符规则：

如果你正在寻找“needle”，而当前文本字符是“z”——那么在这一点或之前不可能开始匹配。因此，算法不是逐字符检查，而是跳过 6 个位置——“needle”的全长——并继续前进。

2. 好后缀规则：

如果你正在寻找“needle”，并且刚刚匹配了“dle”结尾——但下一个字符破坏了匹配——算法不会从下一个字母开始重新检查。相反，它会问：“‘dle’是否在‘needle’中更早出现？”如果是，它将模式向左移动，使更早的“dle”对齐。如果不是，它完全跳过整个“dle”部分。无论哪种方式，它都会智能地向前跳跃，而不是浪费时间重新检查。

这些启发式跳过策略并不完美，但它们比蛮力方法有效得多。

结果？随着文本变长，算法倾向于跳过越来越多的字符，使其相对于输入大小变得更快。这就是为什么像 grep 这样的工具可以以惊人的速度处理千兆字节的日志——这也是为什么这个几十年前的算法今天仍然感觉像是黑魔法。

11、当逻辑遇见想象力：算法的真正力量

无论是将量子不确定性转化为实用的图像生成，用三条简单的规则模仿生物群体行为，还是从右到左搜索文本以更快地找到模式，这些方法表明最不寻常的想法往往会产生最强大的解决方案。

这些算法之所以出色并非因为它们的效率或新颖性——而是因为它们的大胆。它们挑战假设。它们颠倒问题。它们将随机性转化为结构，将混乱转化为秩序，并将抽象理论转化为现实影响。

不仅仅是优雅的数学工具——这十个奇怪的算法是对人类创造力的见证。

原文链接：The 10 Weirdest, Most Brilliant Algorithms Ever Devised and What They Actually Do

汇智网翻译整理，转载请标明出处