运筹答辩货郎担问题.pptx

《运筹答辩货郎担问题.pptx》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、旅游路线设计小组成员选题-------远离繁荣都市的喧嚣，品味自然的乐趣和历史的沉淀模型描述——货郎担问题按上述所给城市的顺序进行编号1,2,3……11，用两城市间欧几里德距离的1.3倍代表城市的距离，我们以任意两点之间的最短距离矩阵为权重矩阵，以北京（编号1）为出发点，构造如下模型：游客到10个城市旅游，再回到出发点处，每城市到且仅到一次。为其设计一种路线，使得所用旅行路线最短。建立数学模型时，把城市设为结点，城市与城市之间的路线设为结点之间的带权的边，则该问题转化为在图上寻求最优Hamilton圈问题。即在加权图上求一个Hamilton圈Ch使得w(c)=mi

2、n{各个Hamilton圈的权)算法①求解与实现①化货郎担问题为指派问题的算法。通过恰当地添加大正数构造效率矩阵。求解结果与分析原问题最短行走路线为1→2→4→5→6→3→11→9→10→8→7→1，总路径长度为：13986公里算法②分支定界法总结起来基本思想是：Step1将边权由小至大排序，初始界d0→∞。Step2在边权序列中依次选取n条边，判断是否构成H圈，若是，d0←d(S)，结束。Step3依次删除当前中的最长边，加入后面第一条待选边，进行深探，如果它是H回路且d(Si)

3、最优值为d0。不然如果新分支的d(Si)≥d0，继续退栈；若d(Si)#include#include#include#defineMax12intcn,tt,start;//定义要经过的城市个数,起点doublearry1[Max][Max];//邻接矩阵，用来存放两两城市间的距离doublefn=0,gn=0,hn=0;//启发函数doublef1=0,g1=0,h1=0;intarry3[Max];//存放已历经的城市名intarry4

4、[Max];//标志位数组，cn个城市中已历经的置0，未历经的置1//主函数intmain(){voidRandNum(int);voidCityCoordinate();doubleCityCost(int,int);voidTSP();doubleMaxLengh();inti,j;//随机生成并显示表示两城市间距离的邻接矩阵for(i=1;i

5、：%d→",start,start);for(i=2;i<=cn;i++)printf("%d→¨²",arry3[i]);printf("%d",arry3[cn+1]);printf("总路径长度为:%f",fn);}//用启发式的MST查找最短路径/////////////////////////////////////////////////////////voidTSP(){intMnode;//起点，当前搜索层的父节点inth,i,k,l,m,n,nn;intx,y=0;intarry2[Max]={0};//标志位数组，已历经的置0，未历经的

6、置1doubletemp1=100,temp2=100;doublelayer1[Max];//初始化当前搜索层节点doublelayer2[Max];//初初始化后继搜索层节点printf("请输入要经过的城市个数：");scanf("%d",&cn);printf("");//输入历经节点printf("请输入要历经的城市：");for(h=1;h<=cn;h++){scanf("%d",&x);if(0==arry2[x])arry2[x]=1;//避免重复elseif(1==arry2[x])h=h-1;}//输入出发点printf("请输入出

7、发城市：");scanf("%d",&start);printf("");arry2[start]=0;//初始化arry3[1]=start;arry3[cn+1]=start;Mnode=arry3[1];for(n=2;n<=cn;n++)//找出城市2～cn{for(nn=1;nn

8、1[k][