算法设计与分析报告

RentingBoats问题的实验研究一、研究报告（80分）1.题目描述（10分） 对题目理解后用自己的语言描述题目大意，给出问题的数学模型（形式化描述），涉及输入数据的精确范畴和解形式。【题目】长江游艇俱乐部在长江上设立了n个游艇出租站1，2，…，n。游客可在这些游艇出租站租用游艇，并在下游的任何一种游艇出租站偿还游艇。游艇出租站i到游艇出租站j之间的租金为r（i，j），1≤i<j≤n。试设计一种算法，计算出从游艇出租站1到游艇出租站n所需的最少租金。【题目描述】题目重要是讲：一种点到它背面的全部点所用的租金不同，例如从第一种站到第二个站所要租金为5；到第三个站的租金为15；而第二个站到第三个站为7；因此选的途径是第一站到第二站为5，第二站到第站为7；总的为12。不大于直接到第三站15。题目中尚有重要的一句话“游艇出租站i到游艇出租站j之间的租金为r（i，j），1≤i<j≤n。”第i行含有n-i个数据，代表租金r(i,j)；因此要特别注意输入的状况。重要思路是用Dijkstra()算法，求出第一站到第n站的最短途径。2.解题思路（20分） 分析题目的难点和核心点，具体叙述解题思路，并证明思路的对的性。【题解】对于给定的游艇出租站i对游艇出租站j之间的租金为r（i，j），1≤i<j≤n，计算从游艇出租站1到游艇出租站n所需的最少租金。数据输入：第1行中有1个正整数n（n<=200），表达有n个游艇出租站。接下来的n-1行是r(i,j),1<=i<j<=n。数据输出：从游艇出租站1到游艇出租站n所需的最少租金样例解释：5->r(1,2)

15->r(1,3)7->r(2,3)最少耗费：1->2->3题解一：dijkstra算法Dijkstra算法是典型最短路算法，用于计算一种节点到其它全部节点的最短途径。重要特点是以起始点为中心向外层层扩展，直到扩展到终点为止。Dijkstra算法能得出最短途径的最优解，但由于它遍历计算的节点诸多，因此效率低。算法思想：假设每个点都有一对标号(dj,pj)，其中dj是从来源点s到点j的最短途径的长度(从顶点到其本身的最短途径是零路(没有弧的路)，其长度等于零)；pj则是从s到j的最短途径中j点的前一点。求解从来源点s到点j的最短途径算法的基本过程以下：

1)初始化。来源点设立为：①ds=0,ps为空;②全部其它点:di=∞,pi=?;③标记来源点s，记k=s,其它全部点设为未标记的。

2)检查从全部已标记的点k到其直接连接的未标记的点j的距离，并设立：dj=min［dj,dk+lkj］式中，lkj是从点k到j的直接连接距离。

3)选用下一种点。从全部未标记的结点中，选用dj中最小的一种i：di=min［dj,全部未标记的点j］点i就被选为最短途径中的一点，并设为已标记的。

4)找到点i的前一点。从已标记的点中找到直接连接到点i的点j*，作为前一点,设立：i=j*5)标记点i。如果全部点已标记，则算法完全推出，否则，记k=i，转到2)再继续。#include<fstream>#include<fstream>#include<cstring>usingnamespacestd;constintMaxNum=1000000;//边权最大值intn;//节点数目intdist[501];//到节点1的最短途径值boolstate[501];//节点被搜索过状态批示intdata[501][501];//邻接矩阵//查找权值最小的节点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++;//找到的点的数目加1state[node]=true;//标记已经找到了从节点1到节点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;}题解二：弗洛伊德算法 弗洛伊德算法的算法思想：通过一种图的权值矩阵求出它的每两点间的最短途径矩阵。从图的带权邻接矩阵A=[a(i,j)]n×n开始，递归地进行n次更新，即由矩阵D(0)=A，按一种公式，构造出矩阵D(1)；又用同样地公式由D(1)构造出D(2)；……；最后又用同样的公式由D(n-1)构造出矩阵D(n)。矩阵D(n)的i行j列元素便是i号顶点到j号顶点的最短途径长度，称D(n)为图的距离矩阵，同时还可引入一种后继节点矩阵path来统计两点间的最短途径。采用的是松弛技术，对在i和j之间的全部其它点进行一次松弛。因此时间复杂度为O(n^3);其状态转移方程以下：map[i,j]:=min{map[i,k]+map[k,j],map[i,j]}map[i,j]表达i到j的最短距离K是穷举i,j的断点map[n,n]初值应当为0，或者按照题目意思来做。固然，如果这条路没有通的话，还必须特殊解决,例如没有map[i,k]这条路把图用邻接矩阵G表达出来，如果从Vi到Vj有路可达，则G[i,j]=d，d表达该路的长度；否则G[i,j]=空值。定义一种矩阵D用来统计所插入点的信息，D[i,j]表达从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的途径。根据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直接相连。算法实现：#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.算法实现（20分） 用程序设计语言实现该算法，给出使用的数据构造及具体代码，代码中给出具体注释。 程序代码放到文本框中，字号用小五号宋体，行间距为单倍行距。算法一：弗洛伊德算法此题用弗洛伊德算法，属于动态规划问题。需要注意的是根据题意所示，第一种点能到下游的n-1个点，而第二个点能到下游的n-2个点......根据动态规划的思想，问题的解由许多小的子问题的解构成。对于此问题，只有点1能够达成点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]表达点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;}/*此题的题目提示用于弗洛伊德算法，因此此题属于动态规划问题。需要注意的是根据题意所示，第一种点能到下游的n-1个点，而第二个点能到下游的n-2歌点......根据动态规划的思想，问题的解由许多小的子问题的解构成。对于此问题，只有点1能够达成点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]表达点1到点j的最小开销)*/算法二：dijkstra算法可根据Dijkstra算法的思想来拟定最少租金的最优子构造，定义数组cost（cost[i]寄存从游艇出租站1到游艇出租站i所需的最少租金）。对于cost数组，设cost[j]（j∈[1,i-1]）寄存从游艇出租站1到游艇出租站j的最少租金，则从游艇出租站1到游艇出租站i所需的最少租金cost[i]应是cost[j]+a[j][i]（j∈[1,i-1]）的最小值。故cost[n]即为所求的从游艇出租站1到游艇出租站n所需的最少租金。根据上述定义，可通过下列程序实现：/************/************求解从游艇出租站1到游艇出租站n所需的最少租金问题*******************a[i][j]表达从游艇出租站i到游艇出租站j所需的租金cost[i]表达从游艇出租站1到游艇出租站i所需的最小租金a,cost可最为全局函数，程序载人时已经定义好/***********************************************************/核心代码：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]=权值(这里就是vi->vj的费用)如果不存在初始化为INF(无穷大)dist[i]数组用来寄存源点1到点i的最少费用,s[i]用来标记源点1到点i的最少费用与否算出*/4.程序测试及分析（15分） 设计多组测试数据（重要是特殊测试数据）测试实现的代码。【测试】【测试时间代码】#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;}【测试成果】用例测试数据测试成果用时（秒）C121110C2312320C3413251620C45123325263530C56131435352563126730C6746325625632463456746760C785325634245625356346324562343406.总结（15分） 总结解题思路及有关内容，如算法使用的那种算法设计方略及实际应用范畴等。【题解总结】本题属于动态规划的求最短途径的一类题，可采用dijkstra算法和floyd算法以及回溯法（具体算法略）。Floyd算法又称为弗洛伊德算法，插点法，是一种用于寻找给定的加权图中顶点间最短途径的算法。时间复杂度为O(n^