货郎担动态规划

1、一，问题由来货郎担问题也叫旅行商问题，即TSP问题（Traveling Salesman Problem ）, 是数学领域中著名问题之一。二，问题描述1）货郎担问题提法：有n个城市，用1，2,，n表示，城i,j之间的 距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市 1， 怎样选择行走路线使总路程最短？2） 旅行商问题的提法：假设有一个旅行商人要拜访 n个城市，他必须选 择所要走的路径，路经的限制是每个城市只能拜访一次， 而且最后要回到原来出 发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。三，问题求解1）动态规划解例题：设v1，v2，vn是已知的n个城

2、镇，城镇vi到城镇vj的距离为dij，现求从v1出发，经各城镇一次且仅一次返回 v1的最短路程。例12已知4个城市间距离如下表.求从VI岀发.经其余城市一次R仅一次最后返回¥1的最短路径和距离-Vj距离Vi123410679280r .973580846550分析：设S表示从v1到vi中间所可能经过的城市集合，S实际上是包 含除v1和vi两个点之外的其余点的集合，但 S中的点的个数要随阶段数改变。建模：状态变量（i，S）表示：从v1点出发，经过S集合中所有点一 次最后到达vi。最优指标函数fk （i，S）为从v1出发，经过S集合中所有点一次最后到达vi决策变量Pk (i, S)表示：

3、从v1经k个中间城镇的S集合 到vi城镇的最短路线上邻接vi的前一个城镇，则动态规划的顺序递推关系为：fk( i，S)= min fk-1 (j，S、 j +djij 属于 SfO (i，空集)=d1i (k=1 , 2,n-1,i=2,3,n)求解：K=0f0(2,空集)=d12=6f0(3,空集)=d13=7f0(4,空集)=d14=9当k=1时：从城市V1出发，经过1个城镇到达Vi的最短距离为：f1(2, 3 ) = f0 (3,空)+d 32 =7+8=15f1(2, 4 ) = f0 (4,空)+d 42 =9+8=14f1(3, 2 ) = f0 (2,空)+d 23 =6+9=1

4、5f1(3, 4 ) = f0 (4,空)+d 43 =9+5=14f1(4, 2 ) = f0 (2,空)+d 24 =6+7=13f1(4, 3 ) = f0 (3,空)+d 34 =7+8=15当k=2时，从城市V1出发,中间经过2个城镇到达Vi的最短距离.f2(2, 3,4 ) = min f1(3,4)+d32, f1(4,3)+ d42 =mi n 14+8,15+5=20P2(2,3,4)=4f2(3, 2,4 )= min 14+9,13+5=18P2(3,2,4)=4f2(4, 2,3)= min 15+7,15+8=22P2(4,2,3)=2当k=3时：从城市V1出发,中间

5、经过3个城镇最终回到Vi的最短距离.f3(1, 2,3,4 )= minf2(2, 3,4 ) + d 21,f2(3, 2,4)+ d31,f2(4, 2,3 ) +d41 =mi n20+8,18+5,22+6=23P3(1,2,3,4)=3逆推回去，货郎的最短路线是1 2 4 3 1,最短距离为23.四，源码#in clude<iostream>#in clude<ioma nip>using n amespace std;int n;in t cost2020=;bool don e20=1;int start = 0; /从城市0开始int imin (i n

6、t num, int cur)if(num=1)/递归调用的出口return costcurstart;/所有节点的最后一个节点，最后返回最后一个节点到起点的路径int min cost = 10000;for(i nt i=0; i<n; i+)cout<<i<<" i:"<<do nei<<e ndl;if(!donei && i!=start) / 该结点没加入 且 非起始点if(min cost <= costcuri+costistart)continue; /其作用为结束本次循环。即跳出

7、循环体中下面尚未执行的语句。区别于breakdonei = 1; /递归调用时，防止重复调用int value = costcuri + imin(nu m-1, i);if(min cost > value)donei = 0;/本次递归调用完毕，让下次递归调用return min cost;int mai n()/ cin >> n;n=4;in t cc44=0 ,4, 1,3,4 ,0 ,2, 1,1 ,2 ,0, 5,3 ,1,5, 0;for(i nt i=0; i<n; i+)for(i nt j=0; j< n; j+)/cin >> costij; costij=ccij;cout << imin(n, start) << en dl;return 0;源码解析：核心是动态规划，自底向上的思想。写法是递归写法，自顶向下递归调用。第一次调用：起点0，第一