蚂蚁下棋为老问题找到新解

把棋盘上的所有棋子都拿走，只留下一个骑士。然后试着让骑士穿过棋盘上的所有 64 个方格，每个方格都触碰一次。（提醒一下，骑士以 L 形移动，朝一个方向走两格，然后以 90 度角向左或向右、向上或向下走一格。）这种所谓的“骑士之旅”对于一个人来说很难实现，但数学家已经计算出有多种方法可以实现它。如果你最终回到了出发点，你就完成了所谓的“封闭之旅”。有超过 26 万亿种方法可以做到这一点。如果你只是触碰每个点，而不回到出发点，这就叫做开放之旅。实现这一目标的方法太多了，科学家们还没有计算出来。

为解决骑士之行这一数百年来一直吸引着数学家的问题，诺丁汉大学计算机科学家 Graham Kendall 和同事将目光转向了模拟蚂蚁。他们使用了蚁群优化算法，这是一种基于蚂蚁寻找其群体和食物源之间路径的行为的群体智能技术。正如 Kendall 在 The Conversation 上解释的那样，它的工作原理如下：

计算机程序用于模拟一群蚂蚁。这些蚂蚁被分配任务，寻找问题的解决方案。每只蚂蚁在执行任务时都会留下信息素踪迹——一种蚂蚁用来相互交流的有气味的物质。在模拟算法中，最成功的蚂蚁（解决问题能力更强的蚂蚁）比表现不佳的蚂蚁留下更多的信息素。

该计划重复了数十万次，在完成旅程的路径上放置了更多“信息素”。但必须在强化有效路径和强调寻找新路径之间取得平衡。

肯德尔和他的同事利用该程序找到了近 50 万个骑士之旅的新解决方案。谁知道（模拟）蚂蚁可以找到几个世纪以来一直困扰着人们的问题的新答案？

对话