变形虫——一种主要由胶质原生质构成的单细胞生物——被证实具有一种独特的计算能力，能用来解决“旅行推销员问题”。有朝一日，这或许会成为成取代传统计算机所使用的方法。在日本庆应义塾大学，青野真士（Masashi Aono）教授领导的一个研究团队，将变形虫用来解决组合优化中的一个问题——旅行推销员问题（TSP）。
这个问题所说的是，给定一系列城市和每个城市之间的距离，求解这几个城市之间最短的路线，使得每个城市恰好被访问一次，且起点和终点是相同的。这是一个属于NP-困难的问题，这意味着随着城市数量的增加，计算机解决它所需要的时间呈指数级增长。它之所以复杂是因为存在大量可能的解决方案。例如，当考虑的城市数量是4个时，那么可能的路线只有三条；但如果考虑的城市数量为8，那么可能的路线数量就会增加到2520条。
在这项新的研究中，研究人员发现，一种变形虫可以找到合理的（几乎是最优的）解决旅行推销员问题的方案，并且随着“城市”数量从4到8的增加，所用的时间呈线性增长。虽然传统的计算机也可以在线性时间内找到近似解，但其算法与变形虫完全不同。科学家解释说，变形虫通过以恒定的速率不断地将凝胶重新分布在它那没有固定形状的身体中，以及并行而不是串行地处理光学反馈来探索溶液空间。
虽然传统的计算机仍然能够比变形虫更快速地解决旅行推销员问题（特别是对于那些“城市”数量较小的问题），但这一新的结果是非常有趣的，它或许能发展出新型的模拟计算机，这种模拟计算机可以在线性时间内得到大得多的计算复杂的问题的近似解。
变形虫如何工作？科学家使用的变形虫是一种疟原虫（或“真正的黏液霉菌”），它重约12毫克，以燕麦片为食。
它无定形的身体会不断地变换形状，以约1毫米/秒的速率反复供应和收回凝胶，制造出像伪足一样的附肢。实验中，研究人员把变形虫放在星形薄片的中心，这是一种圆形的薄片，有64个狭窄的通道向外突出。将这种薄片放在琼脂上面，变形虫会被限制在薄片内，但仍然可以移动到64个通道中。为了最大限度地吸收营养，变形虫会试图在薄片内扩张，以尽可能多地接触到琼脂。
然而，变形虫不喜欢光，而研究人员可以选择性地照亮每个通道，所以就有可能迫使变形虫从被照亮的通道中退散。
为了对旅行推销员问题进行建模，星形薄片中的每个通道代表推销员路线上的一个有序的城市。例如，对于有四个城市标记为A-D的情况，如果变形虫占据A4、B2、C1和D3通道，则旅行推销员问题对应的解决方案是C、B、D、A、C。将变形虫引向最优或接近最优解决方案的关键在于控制光线。
为了做到这一点，研究人员使用了一种神经网络模型，在这种模型中，系统每隔六秒钟就会更新被照亮的通道。这种模型将两个城市之间距离的信息与变形虫在通道中当前位置的反馈结合了起来。
总的来说，用变形虫来模拟旅行推销员问题是利用了变形虫寻求稳定平衡的自然倾向。由于代表较短路线的通道不太可能被照亮，变形虫可能会在这些通道中扩散，并继续探索其他未被照亮的通道，使得它在琼脂上的表面积最大化。研究人员还开发了一种名为AmoebaTSP（变形虫旅行推销员问题）的计算机模拟，来模拟变形虫如何解决这一问题的一些主要特征，包括凝胶从各种通道以恒定速率供应和撤出时的持续移动。
未来，研究人员计划进一步提高变形虫的计算能力。来自庆应义塾大学的另一位合著者Kim Song-Ju说：“我们将进一步研究这些复杂的时空振荡动力学能如何提高计算性能，从而在更短的时间内找到更高质量的解决方案。如果能够清楚这一点，这些知识将有助于创造出新的能充分利用电路中电流的时空动力学的模拟计算机。
”研究人员还预计，通过制造更大的薄片，变形虫将能够解决数百个城市间的旅行推销员问题，尽管那时这将需要数万个通道。