多段图算法实验报告

算法分析与设计实验报告课题:多段图姓名：杜茂鹏班级：计算机1101学号：0909101605目录一、实验目的二、实验内容三、实验要求四、概要设计五、详细设计六、实验心得一、实验目的加深理解动态规划策略，求出多段图中源点到各点的最短路径。二、实验内容设G=(V,E)是一个赋权有向图，其顶点集V被划分成k2个不相交的子集Vi:1ik，其中，V1和Vk分别只有一个顶点s(称为源)和一个顶点t(称为汇)，图中所有的边(u,v)的始点和终点都在相邻的两个子集Vi和Vi＋1中：uVi，vVi＋1。找一条从s到t的最短路线。三、实验要求在上机前写出全部源程序；能在机器上正确运行程序；四、概要设计图采用邻接矩阵表示设P(i，j)是一条从Vi中的结点j到汇点t的最小成本路径，COST(i，j)是这条路的成本。则从Vi中节点j到t的最小代价为：cost((i,j)=min{cost(i+1,l)+c(j,l)},l∈Vi+1，j∈Vicost(i+1，l)是从Vi+1中节点l到t的最小代价。算法概要设计如下：多段图的向前处理算法procedureFGRAPH(G，k，n，P){//G有n个结点的k段图。E是边集，c[i，j]是边i,j的成本。P[1：k]是最小成本路径。//COST[n]，D[n一1]，P[k]，r，j，k，nCOST[n]←0forj←n-1to1by-1do//计算COST[j]//{设r是一个这样的结点，(j，r)E且使c[j，r]+COST[r]取最小值COST[j]←c[j，r]+COST[r]D[j]←r}//向前对j-1进行决策//P[1]←1P[k]←nforj←2tok-1do//找路径上的第j个节点//P[j]←D[P[j-1]]五、详细设计：#includestdio.h#includestdlib.h#defineN12#defineK5#defineMAX23767intcost[N][N];intpath[K];typedefstructnode{intv;intw;structnode*next;}node;nodeL[N];voidinit(node*L[]){inti,j;node*p,*q;for(i=0;iN;i++)for(j=0;jN;j++)cost[i][j]=MAX;cost[0][1]=9;cost[0][2]=7;cost[0][3]=3;cost[0][4]=2;cost[1][5]=4;cost[1][6]=2;cost[1][7]=1;cost[2][5]=2;cost[2][6]=7;cost[3][7]=11;cost[4][6]=11;cost[4][7]=8;cost[5][8]=6;cost[5][9]=5;cost[6][8]=4;cost[6][9]=3;cost[7][9]=5;cost[7][10]=6;cost[8][11]=4;cost[9][11]=2;cost[10][11]=5;/*生成邻接表*/for(i=0;iN;i++)L[i]=(node*)malloc(sizeof(node));for(i=0;iN;i++){q=L[i];for(j=0;jN;j++)if(cost[i][j]0&&cost[i][j]MAX){p=(node*)malloc(sizeof(node));p-v=j;p-w=cost[i][j];q-next=p;q=p;}q-next=NULL;}}voidMethod1()/*使用邻接矩阵存储*/{inti,j,maxlen,temp,v[N],d[N];for(i=0;iN;i++)v[i]=0;for(i=N-2;i=0;i--){for(maxlen=MAX,j=i+1;j=N-1;j++)if(cost[i][j]0&&cost[i][j]+v[j]maxlen){maxlen=cost[i][j]+v[j];temp=j;}v[i]=maxlen;d[i]=temp;}path[0]=0;path[K-1]=N-1;for(i=1;i=K-2;i++)path[i]=d[path[i-1]];}voidMethod2(node*L[])/*使用邻接表存储*/{inti,j,maxlen,temp,v[N],d[N];node*p;for(i=0;iN;i++)v[i]=0;for(i=N-2;i=0;i--){p=L[i]-next;maxlen=MAX;while(p){if(p-w+v[p-v]maxlen){maxlen=p-w+v[p-v];temp=p-v;}p=p-next;}v[i]=maxlen;d[i]=temp;}path[0]=0;path[K-1]=N-1;for(i=1;i=K-2;i++)path[i]=d[path[i-1]];}voidprint(){inti;for(i=0;iK;i++)printf(%d,path[i]+1);printf(\n);}intmain(){init(&L);printf(最短路径:\n);Method1();print();printf(最短路径:\n);Method2(&L);print();system(pause);return0;}六．实验心得通过本次试验，掌握了动态规划的思想，即如果一个问题的最优解可以分解为找子问题的最优解，那么即可使用动态规划。并且区别了分治法和动态规划思想的异同，最大的不同点就是动态规划问题中的子问题不是相互独立的，而分治法的子问题是相互独立的。就多段图问题而言，学会了从“向前”和“向后两方面”理解问题，采用递推的方式依次求得问题的最优解。将选择最短路径的实际问题同算法内容相结合，使得知识应用于实践。在算法的过程中巩固了矩阵和邻接表的存储方式，收获颇丰。