您的位置：：和羣娱乐网 >> 李璇

单个单元提示解决计算机科学中最大的问题索朗扎西

时间：2022年08月24日

单个单元提示解决计算机科学中最大的问题

计算机科学中最古老的问题之一就是单个细胞解决了。

来自东京庆应义塾大学的一组研究人员开始使用变形虫来解决旅行推销员问题，这是计算机科学中的一个着名问题。问题是这样的：想象一下，你是一个旅行推销员，从一个城市飞到另一个城市，出售你的商品你最关心的是最大化你的效率以赚取尽可能多的钱，所以你想要找到最短的路径，让你击中路线上的每个城市。

没有简单的数学公式可以为我们的销售人员找到最有效的路线。相反，解决问题的唯一方法是计算每条路线的长度，看看哪条路线最短。

多头泡菌是一种非常简单的有机体，可以做两件事：它向食物移动并远离光线。

更糟糕的是，执行此计算会使得路线中添加的城市越来越多。有四个城市，只有三条不同的路线需要考虑。但是有六个城市，需要计算360条不同的路线。如果你有一个有十个或更多城市的路线，那么可能的路线数量就是数百万。

这使得旅行商问题成为计算机科学家称之为“NP难”的广泛问题之一。这些问题很快就会出现指数级难度，其中还包括与黑客加密系统和加密货币挖掘相关的问题。由于非常明显的原因，很多人都有兴趣找到尽快解决这些问题的方法。

庆应义塾大学的解决方案与其他研究人员生产的典型算法解决方案不同，因为科学家们使用变形虫。具体而言，Physarum polycephalum 粘液霉菌。多头泡菌是一种非常简单的有机体，可以做两件事：它向食物移动并远离光线。数百万年的进化使得Physarum在这两方面都异常高效。

庆应义塾大学的研究人员利用这种效率建立了解决旅行商问题的设备。他们将变形虫放在一个充满通道的特殊室中，在每个通道的末端，研究人员放置了一些食物。本能地，变形虫会将卷须延伸到通道中以尝试获取食物。但是，当它这样做时，它会触发灯光在其他通道中消失。

在这种特殊情况下，每个渠道代表我们假设的推销员路线上的城市，以及应该访问城市的订单。当变形虫延伸到代表城市的通道时，它会影响光线在代表路线上下一个城市的通道中消失的可能性。距离这个城市越远，光线就越频繁地消失。

这似乎是计算旅行商问题解决方案的迂回方式，但优点是变形虫不必像大多数计算机算法那样计算每个单独的路径。相反，变形虫只是被动地对条件做出反应，并自己找出最好的安排。这意味着对于变形虫来说，增加更多的城市不会增加解决问题所需的时间。

因此，变形虫可以比我们的任何计算机算法更快地解决NP难问题。这是怎么发生的？Keio的科学家们并不确定。

首席研究作者Masashi Aono 在新闻发布会上表示，“变形虫维持近似解决方案质量的机制，即短路线长度仍然是一个谜。”

但是，如果研究人员能够弄清楚变形虫是如何起作用的，他们可以使用这个技巧，而不仅仅是帮助旅行推销员。它可以加快我们解决各种困难计算问题的能力，并改变我们处理安全性的方式。

这个小变形虫 - 以及它解决困难问题的方式 - 可能会永远改变计算的面貌。