通过基于变形虫的计算系统获得的旅行推销员问题的解决方案。 通过实验获得的在四个，五个，六个，七个和八个城市的推销员巡回示例，其中每个巡回在右图的相应频道上都涂成红色。 左面板显示了初始状态的透射光图像（东京庆应义University大学的一群日本研究人员
证明 ，变形虫可以为一个出人意料的复杂数学问题（称为
旅行商问题）产生近似解。
推销员的任务是最著名的组合优化任务之一，其中包括找到至少一次通过这些城市的利润最高的路线，然后返回原始城市。
但是，与大多数特殊情况一样，该问题的优化声明属于NP难题的类别。 “决策问题”的版本（即，提出的问题是是否存在不超过给定值k的路由）属于NP完全问题。
随着更多城市被添加到任务中，计算正确解决方案的难度成倍增加。 例如，对于四个城市，有三个解决方案，对于六个城市，有360个。未来，指数级增长将继续。
尽管计算复杂度很高，但仍有大量启发式和精确算法可以完全解决数以万计城市的某些情况，甚至数百万个城市的问题
也可以近似在0.05％内 。 所指示的链接包含尝试从国家地理学会的基础上解决地球上1,904,711个城市的实例。
1,904,711个城市的国家地理学会基地目前，地球城市的最小距离记录是7515772107公里，该记录是在2018年3月13日使用启发式
LKH算法设定的。
计算机科学中的经典推销员问题被用作优化算法的基准。
变形虫是单细胞生物，不了解组合优化的复杂性。 他们甚至都没有什么类似中枢神经系统的东西，这使得它们不太适合解决此类复杂问题。 但是，日本研究人员发现，某种变形虫可以用来计算八个城市的旅行商问题的最佳解。
根据
科学文章 ，一种名为
Physarum polycephalum的变形虫参与了该实验，
该虫以前曾在其他几个实验中用作生物计算机。 这种生物在生物计算中被认为特别有用，因为它可以扩展其身体的各个区域以寻找更有效的获取食物的方式，而且它讨厌光线。
为了将这种自然的营养机制转化为计算机，日本研究人员将变形虫放在具有64个通道的特殊板上，动物可以朝这个方向伸展身体。 变形虫不断地尝试扩大身体，使其覆盖营养板的最大可能区域。 然而，板上的每个通道都可以被照亮，这使变形虫从对光的反感中脱离了该通道。
为了模拟旅行商的问题，除了从1到8的数字外，在板上的64个通道中的每个通道还分配了一个城市代码A和H，该数字表示城市的顺序（城市的顺序与销售员访问它们的顺序相对应）。
为了对变形虫进行编程，研究人员使用了一个神经网络，该神经网络包含有关变形虫当前位置和城市之间距离的数据，以照亮特定的通道。 神经网络更有可能照亮城市（渠道）之间的距离。
当算法和变形虫相互作用时，变形虫采取一种形式，表示旅行商问题的近似解。 最有趣的是，尽管溶液选择的数量
呈指数增长，但变形虫获得这些几乎最佳溶液所需的时间
呈线性 增长 。 在不久的将来，研究人员将要制造具有数以万计的渠道的芯片，以便变形虫可以尝试解决数百个城市的旅行推销员问题。
该科学文章于2018年12月19日
发表在《
皇家学会开放科学》杂志上 （doi：10.1098 / rsos.180396）。