首页 > 试题广场 >

旅行商问题是NP问题吗?

[单选题]
旅行商问题是NP问题吗?
  • 至今尚无定论
http://blog.csdn.net/zhengzhoudaxue2/article/details/6725855
发表于 2015-09-05 12:49:57 回复(0)

旅行商问题

旅行商问题(Traveling Saleman Problem,TSP)

什么是旅行商问题

旅行商问题(Traveling Saleman Problem,TSP)是VRP的特例,由于Gaery [1]已证明TSP问题是NP难题,因此,VRP也属于NP难题。

旅行商问题(TSP)又译为旅行推销员问题、货郎担问题,简称为TSP问题,是最基本的路线问题,该问题是在寻求单一旅行者由起点出发,通过所有给定的需求点之后,最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig(1959)等人提出 [2]

TSP问题在物流中的描述是对应一个物流配送公司,欲将n个客户的订货沿最短路线全部送到。如何确定最短路线。

TSP问题最简单的求解方法是枚举法。它的解是***的、多局部极值的、趋于无穷大的复杂解的空间,搜索空间是n个点的所有排列的集合,大小为(n-1)。可以形象地把解空间看成是一个无穷大的丘陵地带,各山峰或山谷的高度即是问题的极值。求解TSP,则是在此不能穷尽的丘陵地带中攀登以达到山顶或谷底的过程。


旅行商问题的历史


旅行商问题字面上的理解是:有一个推销员,要到n个城市推销商品,他要找出一个包含所有n个城市的具有最短路程的环路。

TSP的历史很久,最早的描述是1759年欧拉研究的骑士周游问题,即对于国际象棋棋盘中的64个方格,走访64个方格一次且仅一次,并且最终返回到起始点。

TSP由美国RAND公司于1948年引入,该公司的声誉以及线性规划这一新方法的出现使得TSP成为一个知名且流行的问题。


旅行商问题的解法

旅行推销员的问题,我们称之为巡行(Tour),此种问题属于NP-Complete的问题,所以旅行商问题大多集中在启发式解法。Bodin(1983)等人将旅行推销员问题的启发式解法分成三种:


从距离矩阵中产生一个近似最佳解的途径,有以下几种解法:

1)最近邻点法(Nearest Neighbor Procedure):一开始以寻找离场站最近的需求点为起始路线的第一个顾客,此后寻找离最后加入路线的顾客最近的需求点,直到最后。

2)节省法(Clark and Wright Saving):以服务每一个节点为起始解,根据三角不等式两边之和大于第三边之性质,其起始状况为每服务一个顾客后便回场站,而后计算路线间合并节省量,将节省量以降序排序而依次合并路线,直到最后。

3)插入法(Insertion procedures):如最近插入法、最省插入法、随意插入法、最远插入法、最大角度插入法等。


先给定一个可行途程,然后进行改善,一直到不能改善为止。有以下几种解法:

1)K-Opt(2/3 Opt):把尚未加入路径的K条节线暂时取代目前路径中K条节线,并计算其成本(或距离),如果成本降低(距离减少),则取代之,直到无法改善为止,K通常为2或3。

2)Or-Opt:在相同路径上相邻的需求点,将之和本身或其它路径交换且仍保持路径方向性,并计算其成本(或距离),如果成本降低(距离减少),则取代之,直到无法改善为止。


先由途程建构法产生起始途程,然后再使用途程改善法去寻求最佳解,又称为两段解法(two phase method)。有以下几种解法:

1)起始解求解+2-Opt:以途程建构法建立一个起始的解,再用2-Opt的方式改善途程,直到不能改善为止。

2)起始解求解+3-Opt:以途程建构法建立一个起始的解,再用3-Opt的方式改善途程,直到不能改善为止。

编辑于 2016-08-03 09:41:37 回复(1)
首先搞清楚两个概念:
大概就是说:找到到达许多点(一次)的最小路径。但是,最好的解决方法,至今没有人给出来。但是,蜜蜂却办到了。

NP问题? Non deterministic problem(非确定性问题)。http://baike.baidu.com/link?url=I_DOhhZwNvo0goT9XxguZhwPsvvAJt-DpMgXPc125KfZS5IIeSSg7KQyBXEk7iWbWt6H2jy5OzfFxOps0C1gaK
大概就是说:问题可以在多项式时间内求解,但是这个问题的多项式解还不知道。
所以,旅行商问题,就是NP问题。知道该怎么求解,但是,最优的方法却不知道
发表于 2016-05-28 10:23:16 回复(1)
旅行商问题(TravelingSalesmanProblem,TSP)是一个经典的组合优化问题。经典的TSP可以描述为:一个商品推销员要去若干个城市推销商品,该推销员从一个城市出发,需要经过所有城市后,回到出发地。应如何选择行进路线,以使总的行程最短。从图论 的角度来看,该问题实质是在一个带权完全无向图 中,找一个权值最小的Hamilton 回路。由于该问题的可行解是所有顶点的全排列 ,随着顶点数的增加,会产生组合爆炸,它是一个NP完全问题 。由于其在交通运输、电路板线路设计以及物流配送等领域内有着广泛的应用,国内外学者对其进行了大量的研究。早期的研究者使用精确算法求解该问题,常用的方法包括:分枝定界 法、线性规划 法、动态规划 法等。但是,随着问题规模的增大,精确算法将变得无能为力,因此,在后来的研究中,国内外学者重点使用近似算法或启发式算法 ,主要有遗传算法 模拟退火法 蚁群算法 禁忌搜索 算法、贪婪算法 神经网络
发表于 2017-04-21 10:33:14 回复(0)
首先搞清楚什么是NP问题,
最简单的解释:
P:算起来很快的问题
NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对
NP-hard:比所有的NP问题都难的问题
NP-complete:满足两点:
1. 是NP hard的问题
2. 是NP问题
结合旅行商问题,可得出结论
发表于 2019-04-24 20:33:54 回复(2)
没有搞清楚NP是什么
发表于 2023-03-20 17:35:56 回复(0)
&amp;<p>首先搞清楚什么是NP问题, 最简单的解释:</p><p> P:算起来很快的问题</p><p> NP:算起来不一定快,但对于任何答案我们都可以快速的验证这个答案对不对</p><p> NP-hard:比所有的NP问题都难的问题</p><p> NP-complete:满足两点:</p><p> 1. 是NP hard的问题</p><p> 2. 是NP问题 结合旅行商问题,可得出结论</p>
发表于 2020-05-12 23:25:08 回复(0)
答案是B,是
发表于 2015-09-12 14:51:33 回复(0)
P问题和NP问题=><都可以,但是NPC问题一定是NP问题的子集。
这两句话对不对,求解答
发表于 2015-09-09 12:12:20 回复(0)