首页 >> 快讯 >

世界热点评!旅行商问题(TSP)

2023-03-13 23:56:02 来源:哔哩哔哩


(资料图片)

旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。

旅行商问题分析

分析

旅行商问题要从图G的所有周游路线中求取最小成本的周游路线,而从初始点出发的周游路线一共有(n-1)!条,即等于除初始结点外的n-1个结点的排列数,因此旅行商问题是一个排列问题。排列问题比子集合的选择问题通常要难于求解得多,这是因为n个物体有n!种排列,只有 个子集合(n!>O( ))。通过枚举(n-1)!条周游路线,从中找出一条具有最小成本的周游路线的算法,其计算时间显然为O(n!)。

所以该怎么求解呢,很容易想到一种类似于穷举的思路:现在假设我们要拜访11个城市,从城市1出发,最后回到城市1。显然,从城市1出来后,我们随即可以选择剩余的10个城市之一进行拜访(这里所有城市都是连通的,总是可达的),那么很显然这里就有10种选择,以此类推,下一次就有9种选择……总的可选路线数就是:10!。也就是说需要用for循环迭代10!次,才能找出所有的路线,进而筛选出最短的那条路线。如果只拜访10个城市的话(需要迭代3628800次)或许还好,那要拜访100个城市(需要迭代9.3326215443944 * 10^157)开销可想而知

更一般地,如果要拜访n+1个城市,总的可选路线数就是n!,进而时间复杂度就是O(n!)

标签:
x 广告
x 广告

Copyright ©  2015-2022 亚洲创投网版权所有  备案号:豫ICP备20022870号-9   联系邮箱:553 138 779@qq.com

返回顶部