Untitled Course旅行商问题

让我们再次考虑网络和地图。想象一下送货服务必须拜访${tsn}个不同的城市分发包裹。我们可以将这些城市视为图中的顶点。如果所有城市都通过公路连接，则这是完全图循环二分图 ，所以有总共有 ${tsn}×${tsn}−12=${tsn*(tsn-1)/2} 条边。

送货卡车必须以任意顺序访问所有城市。在柯尼斯堡（Königsberg）桥梁问题中，我们希望找到游历_每一条边_的确切路径。现在，我们想找到只访问 每个顶点 一次的路径。这些路径称为 哈密顿循环 。

到目前为止，我们忽略了以下事实：有些城市可能比另一些城市更远。但是，在现实生活中，这是一个非常重要的考虑因素：我们不仅要找到_任何_一条路径，而且还要找到最短的路径。这称为 旅行商问题 。它不仅需要在运输和物流中解决，而且还必须在将晶体管放置在微芯片上，制造更快的计算机或分析DNA结构时解决。

一种简单的方法是尝试所有可能的路径，找到每个路径的长度，然后选择最短的路径。但是我们已经展示了：即使仅有${tsn2}座城市，也会有多达${tsn2}! = ${factorial(tsn2)}条可能的路径。一旦拥有成百上千个顶点，即使利用功能强大的计算机，也无法尝试所有可能的路径。

蚁群系统（ACS）算法尝试使用许多“虚拟”蚂蚁在计算机上复制此行为。他们可以迅速找到很好的解决旅行商问题的解决方案。

ACS算法的一个特别有用的特性是，它们可以连续运行并实时适应图的变化。这些变化可能是由街道网络上的交通事故和道路封闭造成的，也可能是计算机网络上网页服务器的流量激增所致。