算法設(shè)計與分析報告

RentingBoats問題的實驗研究一、研究報告（80分）1.題目描述（10分） 對題目理解后用自己的語言描述題目大意，給出問題的數(shù)學(xué)模型（形式化描述），涉及輸入數(shù)據(jù)的精確范疇和解形式?！绢}目】長江游艇俱樂部在長江上設(shè)立了n個游艇出租站1，2，…，n。游客可在這些游艇出租站租用游艇，并在下游的任何一種游艇出租站償還游艇。游艇出租站i到游艇出租站j之間的租金為r（i，j），1≤i<j≤n。試設(shè)計一種算法，計算出從游艇出租站1到游艇出租站n所需的最少租金?！绢}目描述】題目重要是講：一種點到它背面的全部點所用的租金不同，例如從第一種站到第二個站所要租金為5；到第三個站的租金為15；而第二個站到第三個站為7；因此選的途徑是第一站到第二站為5，第二站到第站為7；總的為12。不大于直接到第三站15。題目中尚有重要的一句話“游艇出租站i到游艇出租站j之間的租金為r（i，j），1≤i<j≤n?！钡趇行含有n-i個數(shù)據(jù)，代表租金r(i,j)；因此要特別注意輸入的狀況。重要思路是用Dijkstra()算法，求出第一站到第n站的最短途徑。2.解題思路（20分） 分析題目的難點和核心點，具體敘述解題思路，并證明思路的對的性?！绢}解】對于給定的游艇出租站i對游艇出租站j之間的租金為r（i，j），1≤i<j≤n，計算從游艇出租站1到游艇出租站n所需的最少租金。數(shù)據(jù)輸入：第1行中有1個正整數(shù)n（n<=200），表達(dá)有n個游艇出租站。接下來的n-1行是r(i,j),1<=i<j<=n。數(shù)據(jù)輸出：從游艇出租站1到游艇出租站n所需的最少租金樣例解釋：5->r(1,2)

15->r(1,3)7->r(2,3)最少耗費：1->2->3題解一：dijkstra算法Dijkstra算法是典型最短路算法，用于計算一種節(jié)點到其它全部節(jié)點的最短途徑。重要特點是以起始點為中心向外層層擴展，直到擴展到終點為止。Dijkstra算法能得出最短途徑的最優(yōu)解，但由于它遍歷計算的節(jié)點諸多，因此效率低。算法思想：假設(shè)每個點都有一對標(biāo)號(dj,pj)，其中dj是從來源點s到點j的最短途徑的長度(從頂點到其本身的最短途徑是零路(沒有弧的路)，其長度等于零)；pj則是從s到j(luò)的最短途徑中j點的前一點。求解從來源點s到點j的最短途徑算法的基本過程以下：

1)初始化。來源點設(shè)立為：①ds=0,ps為空;②全部其它點:di=∞,pi=?;③標(biāo)記來源點s，記k=s,其它全部點設(shè)為未標(biāo)記的。

2)檢查從全部已標(biāo)記的點k到其直接連接的未標(biāo)記的點j的距離，并設(shè)立：dj=min［dj,dk+lkj］式中，lkj是從點k到j(luò)的直接連接距離。

3)選用下一種點。從全部未標(biāo)記的結(jié)點中，選用dj中最小的一種i：di=min［dj,全部未標(biāo)記的點j］點i就被選為最短途徑中的一點，并設(shè)為已標(biāo)記的。

4)找到點i的前一點。從已標(biāo)記的點中找到直接連接到點i的點j*，作為前一點,設(shè)立：i=j*5)標(biāo)記點i。如果全部點已標(biāo)記，則算法完全推出，否則，記k=i，轉(zhuǎn)到2)再繼續(xù)。#include<fstream>#include<fstream>#include<cstring>usingnamespacestd;constintMaxNum=1000000;//邊權(quán)最大值intn;//節(jié)點數(shù)目intdist[501];//到節(jié)點1的最短途徑值boolstate[501];//節(jié)點被搜索過狀態(tài)批示intdata[501][501];//鄰接矩陣//查找權(quán)值最小的節(jié)點intfindmin(){intminnode=0,min=MaxNum;for(inti=1;i<=n;i++)if((dist[i]<min)&&(!state[i])){min=dist[i];minnode=i;}returnminnode;}intmain(){ifstreamin("dijkstra.in");ofstreamout("dijkstra.out");memset(state,0,sizeof(state));in>>n;for(intp=1;p<=n;p++)for(intq=1;q<=n;q++){in>>data[p][q];if(data[p][q]==0)data[p][q]=MaxNum;}//初始化for(inti=1;i<=n;i++)dist[i]=data[1][i];state[1]=true;intdone=1;intdone=1;while(done<n){intnode=findmin();if(node!=0){done++;//找到的點的數(shù)目加1state[node]=true;//標(biāo)記已經(jīng)找到了從節(jié)點1到節(jié)點node的最短途徑for(inti=1;i<=n;i++)//更新還沒有找到的點的途徑值if((dist[i]>dist[node]+data[node][i])&&(!state[i]))dist[i]=dist[node]+data[node][i];}elsebreak;}for(intp=1;p<=n;p++){if(dist[p]==MaxNum)out<<-1;elseout<<dist[p];if(p==n)out<<endl;elseout<<"";}in.close();out.close();return0;}題解二：弗洛伊德算法 弗洛伊德算法的算法思想：通過一種圖的權(quán)值矩陣求出它的每兩點間的最短途徑矩陣。從圖的帶權(quán)鄰接矩陣A=[a(i,j)]n×n開始，遞歸地進(jìn)行n次更新，即由矩陣D(0)=A，按一種公式，構(gòu)造出矩陣D(1)；又用同樣地公式由D(1)構(gòu)造出D(2)；……；最后又用同樣的公式由D(n-1)構(gòu)造出矩陣D(n)。矩陣D(n)的i行j列元素便是i號頂點到j(luò)號頂點的最短途徑長度，稱D(n)為圖的距離矩陣，同時還可引入一種后繼節(jié)點矩陣path來統(tǒng)計兩點間的最短途徑。采用的是松弛技術(shù)，對在i和j之間的全部其它點進(jìn)行一次松弛。因此時間復(fù)雜度為O(n^3);其狀態(tài)轉(zhuǎn)移方程以下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表達(dá)i到j(luò)的最短距離K是窮舉i,j的斷點map[n,n]初值應(yīng)當(dāng)為0，或者按照題目意思來做。固然，如果這條路沒有通的話，還必須特殊解決,例如沒有map[i,k]這條路把圖用鄰接矩陣G表達(dá)出來，如果從Vi到Vj有路可達(dá)，則G[i,j]=d，d表達(dá)該路的長度；否則G[i,j]=空值。定義一種矩陣D用來統(tǒng)計所插入點的信息，D[i,j]表達(dá)從Vi到Vj需要通過的點，初始化D[i,j]=j。把各個頂點插入圖中，比較插點后的距離與原來的距離，G[i,j]=min(G[i,j],G[i,k]+G[k,j])，如果G[i,j]的值變小，則D[i,j]=k。在G中包含有兩點之間最短道路的信息，而在D中則包含了最短通途徑的信息。例如，要尋找從V5到V1的途徑。根據(jù)D，如果D(5,1)=3，D(3,1)=2，D(2,1)=1則闡明從V5到V1通過V3，從V3到V1通過V2，V2到V1直接相連，途徑為{V5,V3,V2,V1}，如果D(5,3)=3，闡明V5與V3直接相連，如果D(3,1)=1，闡明V3與V1直接相連。算法實現(xiàn)：#include<fstream>#include<fstream>#defineMaxm501usingnamespacestd;ifstreamfin;ofstreamfout("APSP.out");intp,q,k,m;intVertex,Line[Maxm];intPath[Maxm][Maxm],Dist[Maxm][Maxm];voidRoot(intp,intq){if(Path[p][q]>0){Root(p,Path[p][q]);Root(Path[p][q],q);}else{Line[k]=q;k++;}}intmain(){memset(Path,0,sizeof(Path));memset(Dist,0,sizeof(Dist));fin>>Vertex;for(p=1;p<=Vertex;p++)for(q=1;q<=Vertex;q++)fin>>Dist[p][q];for(k=1;k<=Vertex;k++)for(p=1;p<=Vertex;p++)if(Dist[p][k]>0)for(q=1;q<=Vertex;q++)if(Dist[k][q]>0){if(((Dist[p][q]>Dist[p][k]+Dist[k][q])||(Dist[p][q]==0))&&(p!=q)){{Dist[p][q]=Dist[p][k]+Dist[k][q];Path[p][q]=k;}}for(p=1;p<=Vertex;p++){for(q=p+1;q<=Vertex;q++){fout<<"\n==========================\n";fout<<"Source:"<<p<<'\n'<<"Target"<<q<<'\n';fout<<"Distance:"<<Dist[p][q]<<'\n';fout<<"Path:"<<p;k=2;Root(p,q);for(m=2;m<=k-1;m++)fout<<"-->"<<Line[m];fout<<'\n';fout<<"==========================\n";}}fin.close();fout.close();return0;}注解:無法連通的兩個點之間距離為0;3.算法實現(xiàn)（20分） 用程序設(shè)計語言實現(xiàn)該算法，給出使用的數(shù)據(jù)構(gòu)造及具體代碼，代碼中給出具體注釋。 程序代碼放到文本框中，字號用小五號宋體，行間距為單倍行距。算法一：弗洛伊德算法此題用弗洛伊德算法，屬于動態(tài)規(guī)劃問題。需要注意的是根據(jù)題意所示，第一種點能到下游的n-1個點，而第二個點能到下游的n-2個點......根據(jù)動態(tài)規(guī)劃的思想，問題的解由許多小的子問題的解構(gòu)成。對于此問題，只有點1能夠達(dá)成點2，因此W[1,2]是點1到點2的最短距離。而到點3的點是點1和2，因此W[1,3]=m(W[1,3]，W[1,2]+W[2,3])....可得遞推公式：W[1,j]=m(W[1,j],W[1,j-1]+W[j-1,j])(W[1,j]表達(dá)點1到點j的最小開銷)。#include<iostream>#include<iostream>usingnamespacestd;intmain(){ints[201][201];inti,j,n; intp,q; intm,t;cin>>n;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++) { cin>>s[i][j]; } for(p=2;p<=n;p++)for(q=p+1;q<=n;q++) { m=s[1][q]; t=s[1][p]+s[p][q];if(m>t)s[1][q]=t;else s[1][q]=m;} cout<<s[1][n]<<endl; return0;}/*此題的題目提示用于弗洛伊德算法，因此此題屬于動態(tài)規(guī)劃問題。需要注意的是根據(jù)題意所示，第一種點能到下游的n-1個點，而第二個點能到下游的n-2歌點......根據(jù)動態(tài)規(guī)劃的思想，問題的解由許多小的子問題的解構(gòu)成。對于此問題，只有點1能夠達(dá)成點2，因此W[1,2]是點1到點2的最短距離。而到點3的點是點1和2，因此s[1,3]=m(s[1,3]，s[1,2]+s[2,3])....可得遞推公式：s[1,j]=m(s[1,j],s[1,j-1]+s[j-1,j])(s[1,j]表達(dá)點1到點j的最小開銷)*/算法二：dijkstra算法可根據(jù)Dijkstra算法的思想來擬定最少租金的最優(yōu)子構(gòu)造，定義數(shù)組cost（cost[i]寄存從游艇出租站1到游艇出租站i所需的最少租金）。對于cost數(shù)組，設(shè)cost[j]（j∈[1,i-1]）寄存從游艇出租站1到游艇出租站j的最少租金，則從游艇出租站1到游艇出租站i所需的最少租金cost[i]應(yīng)是cost[j]+a[j][i]（j∈[1,i-1]）的最小值。故cost[n]即為所求的從游艇出租站1到游艇出租站n所需的最少租金。根據(jù)上述定義，可通過下列程序?qū)崿F(xiàn)：/************/************求解從游艇出租站1到游艇出租站n所需的最少租金問題*******************a[i][j]表達(dá)從游艇出租站i到游艇出租站j所需的租金cost[i]表達(dá)從游艇出租站1到游艇出租站i所需的最小租金a,cost可最為全局函數(shù)，程序載人時已經(jīng)定義好/***********************************************************/核心代碼：doublemincost(intn){ inti,j; cost[1]=0;cost[2]=a[1][2]; //初始化 for(i=3;i<=n;i++){ cost[i]=a[1][i]; for(j=2;j<=i-1;j++) if(cost[j]+a[j][i]<cost[i]) cost[i]=cost[j]+a[j][i]; } returncost[n];}#include<stdio.h>#include<stdio.h>#defineINF99999999#defineMAX201intmap[MAX][MAX];ints[MAX],dist[MAX];intmindist;voiddijkstra(intn){inti,j,k,v0=1;for(i=1;i<=n;i++)//初始化{dist[i]=map[v0][i];s[i]=0;}s[v0]=1;for(i=1;i<=n;i++){mindist=INF;k=v0;for(j=1;j<=n;j++){if(s[j]==0&&dist[j]<mindist){k=j;mindist=dist[j];}}s[k]=1;for(j=1;j<=n;j++){if(s[j]==0)if(map[k][j]<INF&&dist[k]+map[k][j]<dist[j])dist[j]=dist[k]+map[k][j];}}}intmain(){inti,j,n;while(scanf("%d",&n)!=EOF){for(i=0;i<n;i++)for(j=0;j<n;j++)map[i][j]=INF;for(i=1;i<=n-1;i++)for(j=i+1;j<=n;j++)scanf("%d",&map[i][j]);dijkstra(n);printf("%d\n",dist[n]);}return0;}/*如果存在<Vi,Vj>則map[Vi][Vj]=權(quán)值(這里就是vi->vj的費用)如果不存在初始化為INF(無窮大)dist[i]數(shù)組用來寄存源點1到點i的最少費用,s[i]用來標(biāo)記源點1到點i的最少費用與否算出*/4.程序測試及分析（15分） 設(shè)計多組測試數(shù)據(jù)（重要是特殊測試數(shù)據(jù)）測試實現(xiàn)的代碼。【測試】【測試時間代碼】#include<iostream>#include<iostream>#include<time.h>usingnamespacestd;intmain(){ clock_tstart,finish; doubletotaltime;ints[201][201];inti,j,n; intp,q; intm,t;cin>>n;for(i=1;i<=n;i++)for(j=i+1;j<=n;j++) { cin>>s[i][j]; } start=clock(); for(p=2;p<=n;p++) for(q=p+1;q<=n;q++) { m=s[1][q]; t=s[1][p]+s[p][q]; if(m>t) s[1][q]=t; else s[1][q]=m;} cout<<s[1][n]<<endl; finish=clock(); totaltime=(double)(finish-start)/CLOCKS_PER_SEC;cout<<"\n此程序的運行時間為"<<totaltime<<"秒！"<<endl; return0;}【測試成果】用例測試數(shù)據(jù)測試成果用時（秒）C121110C2312320C3413251620C45123325263530C56131435352563126730C6746325625632463456746760C785325634245625356346324562343406.總結(jié)（15分） 總結(jié)解題思路及有關(guān)內(nèi)容，如算法使用的那種算法設(shè)計方略及實際應(yīng)用范疇等。【題解總結(jié)】本題屬于動態(tài)規(guī)劃的求最短途徑的一類題，可采用dijkstra算法和floyd算法以及回溯法（具體算法略）。Floyd算法又稱為弗洛伊德算法，插點法，是一種用于尋找給定的加權(quán)圖中頂點間最短途徑的算法。時間復(fù)雜度為O(n^