我的两岁孩子教会了我约束求解

# 我两岁儿子教我的约束求解之道 来源：https://thecomputersciencebook.com/posts/how-my-2yo-taught-me-constraint-solving/ *在邮件中阅读？可视化内容在浏览器中效果更佳。* 我儿子两岁了，这意味着他拥有阿波罗式的权力意志，喜爱各种机械交通工具和土方工程机械。他尤其喜欢用一套Brio木制火车玩具“玩呜呜”。他喜欢我参与其中，但明确*不*允许我碰火车，于是我通过搭建有趣的轨道布局来自娱自乐。 过了好一阵子，我开始更系统地思考Brio。这些零件显然是设计来拼合成各种形状的，那么设计背后的底层结构是什么？给定我们手中的零件集，我能搭建出最复杂的布局是什么？ 我没有正式的数学背景，但我能看到这是一个有趣的算法问题，就摊在我面前的地板上。当我探索这个问题时，我儿子展现出了迄今为止未被发现的约束求解专长。以下内容是对他所说的话稍加编辑后的记述。 ## Brio 系统 Brio 是一种儿童木制火车玩具，但已被特别有兴趣的成年人深入记录过。我首先查阅了非官方的Brio轨道指南（https://woodenrailway.info/track/brio-track-guide），它给每个零件分配了一个字母代码和尺寸。A 是144毫米的中等直轨。A1 和 A2 是108毫米和54毫米的变体。E 是标准弯轨，八分之一圆，内边略超过182毫米，外边222毫米。八个这样的45度弯轨可围成一个直径约40厘米的圆。大多数零件可以翻转，因此弯轨的弯曲方向取决于你如何摆放它。 [](https://thecomputersciencebook.com/posts/how-my-2yo-taught-me-constraint-solving/brio.jpg)一个简单的Brio布局 还有坡道和桥梁，但为了简化，我们忽略它们，把系统视为二维的。这很适合我，因为桥梁摇摇晃晃，我儿子老是碰倒它们，所以我尽量把这些零件藏起来。 ## 首先，让轨道闭合 一天早上，我先把八个弯轨拼成一个圆。 “圆！”我儿子欢呼道。 好！把《托马斯和朋友学形状》读了上百遍，终于有回报了。 但这是最简单的闭合Brio回路。接下来怎么走？我觉得有趣的是，取一组轨道零件，看看是否每个零件都能被安排成一个闭合布局（即每个连接器都配对）。 本文的可视化由三个逐渐复杂的求解器提供支持。图一到图四使用回溯搜索，图五使用约束求解，图六使用SAT求解器。 回溯搜索就像是幼儿搭轨道：放下一块零件，看看开放的连接器，尝试另一块零件，当某个零件放不上时就退回。以下是我们如何制造一个回环： 1. 火车绕圈 8 个 E 弯轨 地面上的零件 搜索跟踪 0 个零件已放置 0.0 秒已过 0 个状态已探索 0 个开放连接器 当前选择 尚未放置任何轨道。 实际上，我儿子会在轨道拼不上时气冲冲地扔小火车，但求解器执行的是*递归回溯*，这是一种有自控能力的人探索搜索空间的常用方法。 开放连接器构成了一个任务列表。求解器一次只处理其中一个，尝试所有适合该位置的零件和朝向，并递归深入每个可能性。当某个分支陷入死胡同——没有零件能放上去，或者所有零件都用完了而连接器仍有未配对的——它就退回到最后一个仍有选项的连接器。只有当没有连接器开放*且*集合中的所有零件都已放置时，轨道才算闭合。过早闭合（仍有零件剩余）被视为另一个死胡同，需要回溯。用类似Python的伪代码表示，大致如下： `` def search(open_connectors, unused_pieces, layout): if not open_connectors: return layout if not unused_pieces else None connector = open_connectors[0] for piece in unused_pieces: for port in piece.ports: placement = mate(piece, port, connector) if collides(placement): continue found = search(update(open_connectors, placement), unused_pieces - piece, layout + placement) if found is not None: return found return None `` 对于八个E弯轨，只要每个弯轨都朝向同一方向，问题就很简单。但求解器并不知道这一点。如果逐步执行上面的图示并观察“已探索状态”计数，会发现它迅速增加。这是因为搜索首先尝试朝错误方向弯曲的弯轨，一直沿着这条死路走到所有零件用完而无法闭合，然后回溯并铺设实际上可行的弯轨。“状态”计数追踪了那整个浪费掉的子树。 “再来，爸爸！”他说。 ## 让轨道变大 于是我通过拆分圆并在两侧添加平行的直轨段来让轨道变大。 “椭圆！”我说，好像我发现了几何学似的。 “不，爸爸，是*长方形*，”他指着直轨段说。 我愣住了。他说得对。他在托儿所的工作人员曾说他似乎很聪明。也许高昂的学费是值得的。 试图快速挽回威严，我考虑其算法影响。增加两个直轨件大大增加了可能的状态数量。 2. 火车绕更大圈 8 个 E 弯轨 + 2 个 A 直轨 地面上的零件 搜索跟踪 0 个零件已放置 0.0 秒已过 0 个状态已探索 0 个开放连接器 当前选择 尚未放置任何轨道。 显而易见的方法是使用*贪心*算法：取第一个合适的零件，继续推进，永不回头。但一个零件可能在某处合适，却使得轨道永远无法闭合。特别是直轨只在少数位置可行。贪心运行可能会在错误位置用掉它们中的一个，然后卡住，再无办法。因此我们需要能够从死胡同回溯，撤销已做的放置并尝试新零件。 我温和地解释。“指数级，爸爸，”他点头。 确实如此。每个开放连接器可由任何适合它的零件继续，因此部分布局的数量随零件数量呈指数增长，大致为 O(b^n)，其中 b 是分支因子，n 是零件数量。这个图只比之前的圆多了两个零件，但它尝试了 1,930 个状态，而圆只用了 254 个。也就是说，多了两个零件，状态数大约增加了八倍。 那么，既然是指数运行时间的算法，它怎么在你的浏览器里运行得相当快呢？在这个规模下，它不需要很聪明：几千个状态对于笔记本电脑来说不算什么，因此简单的穷举回溯——按照固定顺序尝试每个零件和端口，没有捷径，没有花招——能在几毫秒内完成。但这不会永远成立。最坏情况仍然是指数的，我们很快就会撞墙。 无论如何，圆、长方形、椭圆或随便叫什么的东西都很无聊。做得更大并不难，但火车只是绕同样的圈。我们需要交叉和分支来让事情变得有趣。 ## 交叉引入分支点 我儿子拿起一个交叉件（H3）。它由两个重叠的圆组成，因此火车滚过时可以保持在原轨槽或切换到另一条轨道。 [](https://thecomputersciencebook.com/posts/how-my-2yo-taught-me-constraint-solving/h3.png)一个 H3 交叉件 现在我们有了分支点！我给儿子看。“看，这里有一个交叉件。” “两个环的图！”他眉开眼笑。 我自豪得融化了。我自己的小计算机科学家！未来 Hacker News 评论区里的恐怖分子！ 正如我们在《计算机科学书》的图论部分（https://thecomputersciencebook.com/book/algorithms-and-data-structures）中所见，图是点和连接线的数学术语（点称为顶点，线称为边），而环是通过图回到起点的任何路径。到目前为止，每个轨道零件有两个连接器，因此轨道就像一根线，从一端到另一端。如果形成闭合回路，那就是一个环。交叉件有四个连接器，因此放置它时会同时打开三个连接器，搜索本身也开始分支。数据模型必须从这样： 变为这样： `` piece = connectors + geometry + internal grooves `` 搜索算法没有改变，但现在它是在更复杂的空间上进行搜索。 记住，目标是检查集合中的每个零件——包括交叉件——是否能适配成一个闭合网络。而且确实可以。通过交叉件连接的两个完整圆，每个连接器都配对，火车一圈中穿过两个轨道槽。 3. 这个自己交叉自己 14 个 E 弯轨 + 1 个 H3 曲线交叉件 地面上的零件 搜索跟踪 0 个零件已放置 0.0 秒已过 0 个状态已探索 0 个开放连接器 当前选择 尚未放置任何轨道。 一个有趣的旁注是碰撞检测。起初，我加了这个约束，因为求解器老是想通过把零件叠在一起作弊。我为了正确性加了它，但额外的约束也有助于加速搜索。更多的约束减少了需要探索的搜索空间大小。 ### 获取免费的 45 页 CS 路线图 订阅后我会发给你一份免费的、45 页的计算机科学路线图——学什么，按什么顺序，跳过什么——以及偶尔的 CS 深度文章。 无垃圾邮件。随时可退订。 ## 分支将环变成网络 L 分支是一个直轨和一个弯轨共享一个连接器。小火车可以直行或沿弯轨拐弯。M 是其镜像。 [](https://thecomputersciencebook.com/posts/how-my-2yo-taught-me-constraint-solving/branches.jpg)L 和 M 分支 求解器现在可以找到更有趣的布局了。它在两个分支之间创建了一个内环，这样外部是一个长方形，内部是一个圆，并且每个分支的三个连接器都配对了。 4. 这个里面有个选择 10 个 E 弯轨 + L 和 M 分支 地面上的零件 搜索跟踪 0 个零件已放置 0.0 秒已过 0 个状态已探索 0 个开放连接器 当前选择 尚未放置任何轨道。 “爸爸！度数为三。没有欧拉回路。” 向 ChatGPT 咨询后，我明白了儿子的意思。 度数只是计算相遇于一点的轨道末端数量，因此交叉件（四个连接器）度数为四，分支（三个连接器）度数为三。正如我儿子解释的，图论学家将这种轨道形状称为 θ 图，因为它看起来像字母 θ。欧拉在 1736 年证明，奇数度的顶点意味着无法单圈恰好覆盖每一段轨道一次。（欧拉考虑的是桥，不是木制火车，但数学之美在于这个洞见可以迁移）。交叉件的度数为偶数，这意味着小火车可以单圈走完完整的“8”字形。而使用分支时，轨道完全闭合，但火车无法单圈覆盖整个路径。 ## 转化为约束问题 我的轨道布局已经无法打动我儿子了。绝望之下，我试图做出最令人印象深刻的轨道：大量交叉件、大量分支，全套零件。 我把整盒零件倒在地板上，试图做一个超级复杂的布局。结果惨败。我走得很远，然后发现零件之间距离太大无法连接。搜索空间随零件数量呈指数增长，而我还在不断增加零件。 我儿子用不可动摇的目光看着我，最后终于叹了口气，带着两岁儿童特有的沉重。 “爸爸，”他说，“这是一个约束满足问题，傻蛋！” “你什么意思？”我问道，不免有些沮丧，因为我隐约觉得他说得有道理。 “变量是开放连接器。论域是仍然适合的零件。约束条件说每个连接器都必须配对！” 当然！我怎么没想到呢？通俗地说，*约束满足问题*是指当你能够说出以下三件事时得到的问题： - 正在做哪些选择 - 每个选择允许是什么 - 哪些选择不能共存 例如，数独基本上就是一个约束满足游戏。任何行、列或宫都不能重复数字，因此你必须找出它们能放在哪里。这就是约束求解器所做的事。 转换到 Brio 语境中，选择是零件放置的位置。允许的值是它们可以取的位置、旋转和翻转。约束是我们收集的物理规则：连接器必须匹配，轨道不能穿过轨道，等等。 如果你停下来思考回溯是如何工作的，就会发现它在两个方面荒谬地浪费。它没有远见：它只在很久以后，当所有零件都耗尽时才意识到某个分支注定失败，而那正是导致失败的放置早已完成之后。而且它没有目标：当失败时，它只撤销最近一次放置并尝试下一个，即使真正的错误是十个零件之前犯下的，我们应该尝试一个全新的方向。 “你需要传播，”我儿子说，头也不抬地继续搭积木。“还有回溯跳转。” 事实上，我之前并不知道我需要传播和回溯跳转。 在约束求解器中，轨道仍然一次增长一个开放连接器，但每个开放连接器现在保留一份可能合法放置在那里的零件-端口组合的候选列表。这份候选列表就是它的*域*。 *前向检查*保持候选列表是最新的。每放置一个零件，求解器就会划掉任何现在会与布局发生碰撞或需要已用零件的选项。如果某个连接器的候选列表为空，则该分支永远无法闭合，因此求解器立即放弃它。*冲突导向的回溯跳转*决定应该回退多远。它不是一次撤销一个零件，而是找出哪个较早的放置导致了失败，并直接跳回那里。 我在图四中给了它同样的十二个零件，十个弯轨和两个分支，这样我可以直接与我们已经测量过的纯回溯问题进行比较。 出乎意料的是，我的第一个版本反而更糟。它尝试了 853,186 个状态，而图四是 434,791 个，几乎是两倍。我不相信，于是又在其他几十组零件上运行了一遍，前向检查每次都使搜索变慢。 这是为什么？难道我两岁的儿子其实并不太了解约束求解？ 原因在于前向检查能检测到什么和不能检测到什么。它只会在某个连接器的候选列表为空时放弃分支，而这需要放置一个使得那个连接器所有选项都被排除的零件。但 Brio 的死胡同几乎从不局部。几乎任何零件都适合几乎任何开放连接器，因此候选列表一直保持满，直到零件用完。真正让分支失败的是剩余零件无法提供足够的连接器来配对所有仍开放的连接器，或者是开放端之间距离太远，盒子里剩下的任何零件都无法跨越。因此前向检查只会在纯回溯检测到的同一时刻检测到问题，得不偿失。 “你在检查连接器，爸爸，”我儿子叹了口气。“检查所有零件。” 他指的是一个*全局约束*，它考察整个布局而不是单个连接器。每次放置后，求解器现在直接检查两个整体布局的事实：是否有足够的剩余连接器来配对所有仍开放的，以及剩余零件能否跨越间隙？如果任一答案为否，则布局永远无法闭合，所以分支直接……