運籌答辯貨郎擔問題.pptx

《運籌答辯貨郎擔問題.pptx》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、旅游路線設計小組成員選題-------遠離繁榮都市的喧囂，品味自然的樂趣和歷史的沉淀模型描述——貨郎擔問題按上述所給城市的順序進行編號1,2,3……11，用兩城市間歐幾里德距離的1.3倍代表城市的距離，我們以任意兩點之間的最短距離矩陣為權(quán)重矩陣，以北京（編號1）為出發(fā)點，構(gòu)造如下模型：游客到10個城市旅游，再回到出發(fā)點處，每城市到且僅到一次。為其設計一種路線，使得所用旅行路線最短。建立數(shù)學模型時，把城市設為結(jié)點，城市與城市之間的路線設為結(jié)點之間的帶權(quán)的邊，則該問題轉(zhuǎn)化為在圖上尋求最優(yōu)Hamilton圈問題。即在加權(quán)圖上求一個Hamilton圈Ch使得w(c)=mi

2、n{各個Hamilton圈的權(quán))算法①求解與實現(xiàn)①化貨郎擔問題為指派問題的算法。通過恰當?shù)靥砑哟笳龜?shù)構(gòu)造效率矩陣。求解結(jié)果與分析原問題最短行走路線為1→2→4→5→6→3→11→9→10→8→7→1，總路徑長度為：13986公里算法②分支定界法總結(jié)起來基本思想是：Step1將邊權(quán)由小至大排序，初始界d0→∞。Step2在邊權(quán)序列中依次選取n條邊，判斷是否構(gòu)成H圈，若是，d0←d(S)，結(jié)束。Step3依次刪除當前中的最長邊，加入后面第一條待選邊，進行深探，如果它是H回路且d(Si)

3、最優(yōu)值為d0。不然如果新分支的d(Si)≥d0，繼續(xù)退棧；若d(Si)#include#include#include#defineMax12intcn,tt,start;//定義要經(jīng)過的城市個數(shù),起點doublearry1[Max][Max];//鄰接矩陣，用來存放兩兩城市間的距離doublefn=0,gn=0,hn=0;//啟發(fā)函數(shù)doublef1=0,g1=0,h1=0;intarry3[Max];//存放已歷經(jīng)的城市名intarry4

4、[Max];//標志位數(shù)組，cn個城市中已歷經(jīng)的置0，未歷經(jīng)的置1//主函數(shù)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→¨2",arry3[i]);printf("%d",arry3[cn+1]);printf("總路徑長度為:%f",fn);}//用啟發(fā)式的MST查找最短路徑/////////////////////////////////////////////////////////voidTSP(){intMnode;//起點，當前搜索層的父節(jié)點inth,i,k,l,m,n,nn;intx,y=0;intarry2[Max]={0};//標志位數(shù)組，已歷經(jīng)的置0，未歷經(jīng)的

6、置1doubletemp1=100,temp2=100;doublelayer1[Max];//初始化當前搜索層節(jié)點doublelayer2[Max];//初初始化后繼搜索層節(jié)點printf("請輸入要經(jīng)過的城市個數(shù)：");scanf("%d",&cn);printf("");//輸入歷經(jīng)節(jié)點printf("請輸入要歷經(jīng)的城市：");for(h=1;h<=cn;h++){scanf("%d",&x);if(0==arry2[x])arry2[x]=1;//避免重復elseif(1==arry2[x])h=h-1;}//輸入出發(fā)點printf("請輸入出

7、發(fā)城市：");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][