词汇表

选择左侧的一个关键字...

旅行商问题

阅读时间: ~5 min
此页面已自动翻译,可能包含错误。如果您想帮助我们审核翻译,请与我们取得联系!

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

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

完全图中的哈密顿循环有无数种不同的可能性。实际上,我们可以选择任意一个顶点作为起始顶点,然后以任意顺序选择剩余的任意城市:

Diagram coming soon…

Diagram Coming Soon…

在图中${tsn1}座城市,每个汉密尔顿周期也必须包含${tsn1}座城市。现在,

    这意味着总共有${tsnPaths(tsn1)}种可能的路径。该结果的简称是${tsn1}! 或 ${tsn1}阶乘

    您可以想象,如果不经过另一座城市,可能无法直接在两个城市之间旅行。在那种情况下,我们将不再有完全图,找到汉密尔顿循环的数量-如果确实存在,将变得更加困难。

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

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

    不幸的是,没有更有效的算法来解决旅行商问题。取而代之的是,数学家和计算机科学家开发了各种算法,它们找到了良好的解决方案,即使它们可能不是最好的。这些仅给出近似解的算法称为 __启发式算法

    尝试在地图上重新排列城市,并观察它们之间最短路径的变化。您可以通过点按来删除城市,也可以通过在地图上的任意位置(最多8个)单击来添加城市:

    贪婪算法 (或最近邻居算法)非常简单:您从一个随机城市开始,然后连续移至您之前从未访问过的最近城市。一旦您访问了所有城市,便会停下来。

    动画即将推出…

    您可以证明,使用贪婪算法找到的路径平均比最短路径长25%。

    2-Opt算法 从可能的随机路径开始。然后,您反复选择两个边缘并交换它们,如果这样会减少路径的长度。当您无法通过交换任何对边来进一步减小长度时,您会停下来。

    动画即将推出…

    事实证明,在计算机甚至还没有出现的很早以前,自然界就已经找到了一种巧妙的方法来找到不同位置之间的最佳路径:在蚁群中。

    蚂蚁希望找到它们的巢和食物来源之间的最短路径。它们可以通过沿着行进路线留下的化学物质相互交流,并可以跟随其他蚂蚁。

    • 蚁群会发出许多侦察兵,这些侦察兵最初会朝随机方向行进。一旦找到食物,他们就会返回,留下一小撮信息素。
    • 其他蚂蚁在找到一条线索时,往往会跟着一条线索,这条线索会引导它们找到食物。
    • 随着时间的流逝,信息素蒸发。路径越长,蚂蚁沿着它行进所花费的时间就越多,因此信息素有更多的时间蒸发。另一方面,短路径可以更快地得到增强,因此它们的强度会更快地增加。

    图解即将推出…

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

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

    旅行商问题是NP难题 ,这意味着很难用计算机来解决(至少对于大量城市而言)。

    找到一种快速而精确的算法将对计算机科学领域产生重大影响:这意味着对于所有 NP难题,都有快速的算法。这也将使大多数国际互联网安全策略失效,因为已有的安全防御取决于以下事实:即某些问题被认为对计算机来说非常难解。

    寻找一种解决旅行商问题的快速算法,也将解决数学和计算机科学中最著名的开放问题之一,即P vs NP问题。它是七个千年奖”问题之一 ,每个都有100万美元的奖金。