资源描述：
《最新货郎担(旅行售货商)动态规划.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、__________________________________________________一，问题由来 货郎担问题也叫旅行商问题，即TSP问题（TravelingSalesmanProblem），是数学领域中著名问题之一。 二，问题描述 1）货郎担问题提法：有n个城市，用1，2，…，n表示，城i,j之间的距离为dij，有一个货郎从城1出发到其他城市一次且仅一次，最后回到城市1，怎样选择行走路线使总路程最短？ 2）旅行商问题的提法：假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径
2、，路经的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。三，问题求解 1）动态规划解 例题： 设v1，v2，……..，vn是已知的n个城镇，城镇vi到城镇vj的距离为dij，现求从v1出发，经各城镇一次且仅一次返回v1的最短路程。 分析：设S表示从v1到vi中间所可能经过的城市集合，S实际上是包含除v1和vi两个点之外的其余点的集合，但S中的点的个数要随阶段数改变。 建模：状态变量（i，S）表示：从v1点出发，经过S集合中所有点一
3、次最后到达vi。
最优指标函数fk（i，S）收集于网络，如有侵权请联系管理员删除__________________________________________________为从v1出发，经过S集合中所有点一次最后到达vi。
决策变量Pk（i，S）表示：从v1经k个中间城镇的S集合到vi城镇的最短路线上邻接vi的前一个城镇，则动态规划的顺序递推关系为： fk（i，S）= min{ fk-1（j，S、{j}+dji} j属于S
4、 f0（i，空集）=d1i （k=1，2，…,n-1,i=2,3,…n) 求解：K=0
f0(2,空集)=d12=6
f0(3,空集)=d13=7
f0(4,空集)=d14=9 当k=1时:
从城市V1出发,经过1个城镇到达Vi的最短距离为:
f1(2,{3})=f0 (3,空)+d 32 =7+8=15
f1(2,{4})=f0 (4,空)+d 42 =9+8=14
f1(3,{
5、2})=f0 (2,空)+d 23 =6+9=15
f1(3,{4})=f0 (4,空)+d 43 =9+5=14
f1(4,{2})=f0 (2,空)+d 24 =6+7=13
f1(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] =min[14+8,15+5]=20
P2(2,{3,4})=4f2(3,
6、{2,4})=min[14+9,13+5]=18
P2(3,{2,4})=4
f2(4,{2,3})=min[15+7,15+8]=22
P2(4,{2,3})=2 当k=3时:
从城市V1出发,中间经过3个城镇最终回到Vi的最短距离.
收集于网络，如有侵权请联系管理员删除__________________________________________________
f3(1,{2,3,4})=min[f2(2,{3,4})+d 21,f2(3,{2,4})+d31,f2(4,{2,3})+d41
7、]=min[20+8,18+5,22+6]=23
P3(1,{2,3,4})=3逆推回去,货郎的最短路线是1 2 4 3 1,最短距离为23.四，源码#include#includeusingnamespacestd;intn;intcost[20][20]={};booldone[20]={1};intstart=0;//从城市0开始intimin(intnum,intcur){if(num==1)//递归调用的出口returncost[cur][start];//所有节点
8、的最后一个节点，最后返回最后一个节点到起点的路径intmincost=10000;for(inti=0;i
