TSP-旅行商问题,是一个经典问题,如下图所示,描述为“有n个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次,最后回到原出发城市,问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP,回答下列问题。关于TSP的贪心算法的求解思想,下列说法不正确的是()。


TSP-旅行商问题,是一个经典问题,如下图所示,描述为“有n个城市,任何两个城市之间的距离都是确定的,现要求一旅行商从某城市出发必须经过每一个城市且只能在每个城市逗留一次,最后回到原出发城市,问如何事先确定好一条最短的路线使其旅行的费用最少”。围绕TSP,回答下列问题。关于TSP的贪心算法的求解思想,下列说法不正确的是()。

A.贪心算法确定的路径,是由局部最优组合起来的路径,该路径从全局角度来看一定是最优的

B.无需对所有可能进行比较,而仅需依照某种办法确定一系列局部最优,将这样系列局部最优解组合就是一个较优解或次优解

C.不追求最优解,只希望最快得到较为满意解的方法,即每个阶段总是做出在当前看来是最好的选择

D.对一个具体的TSP问题,每次执行贪心算法,所求得的最终解可能是不同的

正确答案:贪心算法确定的路径,是由局部最优组合起来的路径,该路径从全局角度来看一定是最优的


Tag:大学计算机 大学计算机中国大学MOOC 路径 时间:2021-12-09 21:07:53

热门答案