旅行商问题(动态规划方法,超级详细的) 哈尔滨去北京自驾最短路线多少公里啊怎么走的
旅行商问题动态规划方法,超级详细的
一、题目一个售货员必须访问n个城市,恰好访问每个城市一次,并最终回到出发城市。售货员从城市i到城市j的旅行费用是一个整数,旅行所需的全部费用是他旅行经过的的各边费用之和,而售货员希望使整个旅行费用最低。等价于求图的最短哈密尔顿回路问题令G=(V,E)是一个带权重的有向图,顶点集V=(v0,v1,...,vn-1)。从图中任一顶点vi出发,经图中所有其他顶点一次且只有一次,最后回到同一顶点vi的最短路径。二、测试用例其中1,2,3,4,5代表五个城市。此模型可抽象为图,可用邻接矩阵c表示,如下图所示:
假设从顶点s出发,令d(i,V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次,最后回到出发点s的最短路径长度。
推导:(分情况来讨论)
②如果V不为空,那么就是对子问题的最优求解。你必须在V这个城市集合中,尝试每一个,并求出最优解。
注:
综上所述,TSP问题的动态规划方程就出来了:
现在对问题定义中的例子来说明TSP的求解过程。(假设出发城市是 0城市)
这里只画出了d(1,{2,3,4}),由于篇幅有限这里就不画了。
由上述动态规划公式d(i,V)表示从顶点i出发经过V(是一个点的集合)中各个顶点一次且仅一次,最后回到出发点s的最短路径长度。根据上述给的测试用例有5个城市编号0,1,2,3,4。那么访问n个城市,恰好访问每个城市一次,并最终回到出发城市的嘴短距离可表示为d(0,{1,2,3,4}),那么问题来了我们用什么数据结构表示d(i,V),这里我们就可二维数据dp[N][M]来表示,N表示城市的个数,M表示集合的数量,即
那么你们可能就有疑问了,为什么这么表示?这里说明一下比如集合{1,2,3,4}为什么用15表示,我们可以把集合中元素看成二进制1的位置二进制从右开始看,1表示从右开始第一位为1,2表示从又开始第二位为1,所以集合{1,2,3,4}可表示二进制1111转化为十进制为15。再举个例子比如集合{1,3}表示为二进制为0101,十进制为5。所以我们求出dp[0][15]通用表示dp[0][
注意:对于第y个城市,他的二进制表达为,1 (i - 1) ) & 1) == 1或者x &(14--->2--->3--->0七、代码编写