新算法通过模仿神经系统来改进二分匹配

当你要求拼车应用帮你找车时，公司的计算机就开始工作了。它们知道你想快速到达目的地。它们知道你不是唯一需要搭车的用户。它们还知道司机想在附近搭载乘客，以尽量减少空闲时间。冷泉港实验室副教授萨凯特·纳夫拉卡 (Saket Navlakha) 说，计算机的工作是将司机与乘客配对，以最大限度地提高每个人的幸福感。

纳夫拉卡等计算机科学家将此称为二分匹配。这与器官捐献者与移植候选人、医学生配对的系统所处理的任务相同。因此，这是深入研究的主题。

“这可能是计算机科学领域最著名的 10 个问题之一。”Navlakha 说。

现在，他从生物学中找到了更好的方法。纳夫拉卡发现了神经系统连接中的二分匹配问题。在成年动物中，身体的每一根肌肉纤维都与一个控制其运动的神经元配对。然而，在生命早期，每根纤维都是许多神经元的目标。为了让动物有效地运动，必须修剪多余的连接。那么，哪些匹配可以持久呢?

神经系统有一个有效的解决方案。纳夫拉卡解释说，最初连接到同一肌肉纤维的神经元相互竞争以维持匹配，使用神经递质作为“竞标”资源。输掉这场生物拍卖的神经元可以拿走它们的神经递质并竞标其他纤维。这样，每个神经元和纤维最终都会找到一个伙伴。

Navlakha 设计了一种在神经系统之外实现这种匹配策略的方法。“这是一个简单的算法，”他说。“只有两个方程。一是连接到同一纤维的神经元之间的竞争，二是资源的重新分配。”这项工作已发表在《美国国家科学院院刊》上。

与目前最好的二分匹配程序相比，这种受神经科学启发的算法表现非常出色。它能创建近乎最优的配对，并且不会出现未匹配的情况。在日常应用中，这可能意味着拼车乘客的等待时间更短，没有住院医生的医院更少。

　　免责声明：本文由用户上传，与本网站立场无关。财经信息仅供读者参考，并不构成投资建议。投资者据此操作，风险自担。 如有侵权请联系删除！