鸡兔同笼终于可以靠「猜」了！佐治亚理工学者求解新方法获顶会最佳论文奖

「猜」也是解决问题的一种方法。

「今有雉兔同笼，上有三十五头，下有九十四足，问雉兔各几何？」

这是《孙子算经》中鸡兔同笼问题的经典描述。我们知道，二元一次方程组可以解决这个问题。求解线性系统有矩阵乘法等多种方法，但或许你不知道，靠「猜」也是可以的。

来自佐治亚理工学院的两位研究者给出了一种「猜」的方法，并斩获算法研究顶会 SODA 2021 的最佳论文奖。

论文地址： https://arxiv.org/pdf/2007.10254.pdf

正如该方法的研究者之一 Vempala 所说，「线性系统是现代计算的主力军」，在实际生活中的应用是非常广泛的。建造一座坚固的桥梁、一架隐蔽的飞机都需要解决包含数百万个方程的线性系统。此外，线性系统与许多计算机科学问题相关，这些问题涉及在约束系统内为一组变量寻找最佳值。如果可以更快地求解线性系统，那么我们也可以更快地解决这些计算机科学问题。

使用矩阵乘法求解线性系统的方法严重限制了计算速度。事实上，在这项研究提出的新方法中，矩阵乘法仍然发挥了一定作用，不过只起到补充作用。研究者将其与一种新方法结合起来： 本质上，那是一种经过训练的「猜测」方法。

动物同笼问题

回到经典的动物同笼问题，假设一个巨大的笼子中含有鸡、单角犀牛和山羊三种动物，已知有 12 个头，38 只脚和 10 只角。你能知道每只动物有多少只吗？

首先为每只动物分配一个变量（c 代表鸡，r 代表犀牛，g 代表山羊），并根据已知属性（包括头、脚、角）编写多个方程式。每个变量前面的数字（或系数）反映了每只动物拥有该属性的数量。

现在就有了三个方程式和三个未知数。

解决该问题的一种方法是操作一个方程式，并根据其他两个方程式定义一个变量。例如，0c + 1r + 2g = 10 变成 r = 10 – 2g。在其他两个方程式中用该值替换 r，然后像这样继续进行，直到仅用一个变量定义了所有变量，就可以精确求解。然后，你可以重复执行此过程，利用已求解的变量来求解下一个变量。

另一种更复杂的处理方式是创建一个方程组的系数矩阵，如下：

然后用另一个矩阵表示鸡、犀牛、山羊的未知数量：

然后再用一个矩阵表示头、脚、角的数量：

我们可以将上述 3 个矩阵组成一个线性系统，其中第一个矩阵乘第二个矩阵等于第三个矩阵。然后可以利用线性代数的知识求解第二个矩阵中的未知数。

无论是使用方程式还是采用矩阵的形式，计算复杂度都是 O(n^3)。例如有四种变量和四个方程，则需要 4^3，即 64 步操作。

降低计算复杂度

在现实应用的复杂问题中，变量数目很大，计算量也会非常大。几十年来，研究人员们一直致力于发现更有效的求解方法。

1969 年，Volker Strassen 设计了一种算法，将矩阵乘法的复杂度降到了 O(n^2.81)。从那时起，数学家和计算机科学家们就致力于进一步降低指数。来自麻省理工学院的 Virginia Vassilevska Williams 以及哈佛大学的博士后研究员 Josh Alman，将计算复杂度降低到了 O(n^2.37286)，比此前最好的结果指数下降了 0.00001。

这些研究表明任何线性系统的求解都可以归结为一个矩阵乘法的问题。到目前为止，理论上矩阵乘法的复杂度至少可以降至 O(n^2.37286)。

但是，多种方法表明，求解线性系统的速度应该比这更快，只需要 O(n^2)。使用矩阵乘法是因为它是目前可用的最佳工具，但这并不意味着不存在更好的工具。

Vempala 说：「求解线性系统的问题没有理由只依赖于矩阵乘法的改进。」在新方法中，彭泱和 Vempala 将算法复杂度降到了 。

靠「猜」的解决方案

为了了解新的改进工具，我们首先要了解另一种求解线性系统的方法。它是一种直观的方法，回想鸡兔同笼问题，你可以简单猜测鸡和兔子各有多少只，然后代入等式，看看离正确答案差了多远，然后再猜一次。

这种「迭代方法」是工程师和科学家经常采用的方法。它可以很好地解决许多实际问题，因为专家通常不会盲目猜测，从而减少了在找到解决方案之前需要反复进行猜测的次数。

彭泱说：「对于现实世界中的科学计算问题，人类对答案应该具备良好的直觉。」

迭代方法在特定示例下是非常有效的，当求解的线性系统中包含大量系数为 0 的变量时，迭代方法也是很有效的。

在更复杂的线性系统中，这种关系（其中并非所有属性都与所有变量相关）可以普遍存在。有些线性系统可能有数百万个变量和数百万个方程式，但是每个方程式中可能只含有部分变量，这类线性系统称为「稀疏」，意味着大多数方程中大多数变量取零值，线性系统中经常会出现这种情况。

Williams 说：「只有当矩阵足够稀疏时，这种方法才会有效。」但是在这项研究之前，没有人能够证明对于所有稀疏线性系统，迭代方法总是快于矩阵乘法。

协调随机性

彭泱和 Vempala 的新方法采用了迭代猜测策略的增强版本：他们的算法不仅可以进行单个猜测，而且还可以并行进行多个猜测。这种方法可以加快搜索速度。滑铁卢大学教授 Giesbrecht 说：「并行才是魔法所在。」

一次进行多个猜测似乎是有用的，但是想让该策略起作用并不是那么简单。新算法的有效性在很大程度上取决于如何聪明地做出引发迭代过程的初始猜测，以及找到将并行猜测的结果组合成单个最终答案的巧妙方法。

回到动物同笼的问题，该算法可能会首先进行三个初始猜测，其中每个猜测都是一个 3×1 矩阵，该矩阵指定了鸡、犀牛和山羊的数量。该算法将观察每个猜测距离正确答案有多远，然后进行更多猜测，持续进行并行猜测线程。

该算法最终成功的关键在于，它会随机进行三个初始猜测。随机性似乎并不适合猜测，但它作为一种通用方法具备其独特的优势，尤其是在处理大量问题时，优势更加明显。也就是说，随机性能够保证最终搜索不会偏向问题的某一部分，否则可能会忽略实际上解所在的空间。

彭泱说：「我需要确保所有的猜测都是足够随机的，以便它们涵盖所有可能的组合。这是一种非常糟糕的猜测方法，但随着问题变得越来越大，这最终成为首选方法。」

在该研究中，许多技术问题都涉及证明随机猜测的不同部分也可以协同工作，包括实际上是最终解的任何特定猜测。Vempala 表示：「存在协调随机性」。

这意味着随机猜测不仅可以包含猜测本身的确切值，还可以涵盖介于两者之间的所有潜在猜测。这类似于两个人在森林中搜寻并不只是搜寻他们所走的地面，还会搜寻他们的整个视野区域。Vempala 说：[两个猜测之间的所有内容也包括在内。]

此搜索功能可确保算法将在某处找到答案。但是它本身并不能识别答案。因此彭泱和 Vempala 还需要进行进一步的证明工作。

该算法将随机猜测作为矩阵中的条目进行追踪。在矩阵的各个条目中寻找解使得问题变成了矩阵乘法问题，这当然是他们要规避的障碍。但是在此，他们再次利用了随机性。因为矩阵中的条目是随机的，并且经过了协调，矩阵最终会具有一些对称性。这些对称性使得计算过程中可以利用一些快捷计算方法。

矩阵的对称性还有另一个好处，即能够保证猜测永远不会太大，避免在算法效率的层面上难以理解。彭泱和 Vempala 的算法可以比没有对称性的矩阵更快地在矩阵中找到解。

作者介绍

个人主页：https://www.cc.gatech.edu/~rpeng/

该论文的一作是是佐治亚理工学院计算机科学学院的助理教授彭泱。

彭泱是江苏南京人，本科毕业于滑铁卢大学数学专业，后在卡内基梅隆大学取得计算机科学博士学位，以及在 MIT 担任博士后。他的研究兴趣是高效算法的设计，分析和实现，曾获 NSF 职业奖，微软研究博士奖学金和 CMU SCS 杰出论文奖。2015 年起担任佐治亚理工计算机科学学院助理教授。