动态规划求解网络最优路径.doc

《动态规划求解网络最优路径.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、动态规划算法求最短路径1.问题描述：在10×10的网格上任意指定起点和终点，运用动态规划算法从中找到最短路径。（要求：相邻格点权值在1到10之间）2.问题分析：运用动态规划的方法就是从后向前逆向思考，对于本题就是从终点出发，依次遍历网格格点，找到各点到终点的最短路径，最终找到起点到终点的最短路径。因为找任意两点最短距离比较复杂，我只做了从一个对角到另一对角最短路径计算。3.程序调试截图如下：代码如下：#include#include#defineN10constin

2、then[N][N-1]={{4,2,5,2,5,9,5,8,3},{1,8,1,5,1,7,1,4,4},{6,4,3,1,2,4,10,3,9},{8,6,10,8,3,6,10,5,1},{10,2,2,9,2,5,5,1,1},{2,7,9,9,2,1,5,2,2},{1,7,6,1,9,3,4,10,7},{5,7,10,4,6,2,10,10,8},{1,7,1,3,6,2,4,6,7},{4,8,5,9,8,3,2,1,5}};constintshu[N-1][N]={{6,4,7,6,3

3、,10,3,1,6,9},{3,10,8,7,2,5,2,10,3,10},{8,8,7,6,3,8,3,8,5,8},{2,5,4,3,5,3,4,5,7,1},{7,5,9,5,4,5,5,6,7,3},{2,5,6,5,10,6,6,3,4,4},{4,4,4,3,5,3,1,5,4,7},{7,6,10,4,2,7,3,10,10,2},{8,6,9,2,10,8,9,6,7,8}};intmain(){inti,j,k1,k2;intx=0;inty=0;intd[N][N];intu_x[N

4、][N];intu_y[N][N];d[N-1][N-1]=0;u_x[N-1][N-1]=u_y[N-1][N-1]=N-1;for(i=0;i<=N-2;i++)for(j=0;j<=i+1;j++){if(j==0){d[N-2-i+j][N-1-j]=d[N-1-i+j][N-1-j]+shu[N-2-i][N-1];u_x[N-2-i+j][N-1-j]=N-1-i+j;u_y[N-2-i+j][N-1-j]=N-1-j;}elseif(j==i+1){d[N-2-i+j][N-1-j]=d[

5、N-2-i+j][N-j]+hen[N-1][N-2-i];u_x[N-2-i+j][N-1-j]=N-2-i+j;u_y[N-2-i+j][N-1-j]=N-j;}else{k1=d[N-2-i+j][N-j]+hen[N-2-i+j][N-1-j];k2=d[N-1-i+j][N-1-j]+shu[N-2-i+j][N-1-j];if(k1<=k2){d[N-2-i+j][N-1-j]=k1;u_x[N-2-i+j][N-1-j]=N-2-i+j;u_y[N-2-i+j][N-1-j]=N-j;}e

6、lse{d[N-2-i+j][N-1-j]=k2;u_x[N-2-i+j][N-1-j]=N-1-i+j;u_y[N-2-i+j][N-1-j]=N-1-j;}}}for(i=N-2;i>=0;i--)for(j=0;j<=i;j++){k1=d[i-j][j+1]+hen[i-j][j];k2=d[i-j+1][j]+shu[i-j][j];if(k1<=k2){d[i-j][j]=k1;u_x[i-j][j]=i-j;u_y[i-j][j]=j+1;}else{d[i-j][j]=k2;u_x[i-

7、j][j]=i-j+1;u_y[i-j][j]=j;}}printf("最短路径为:");for(i=1;i<=2*N-5;i++){printf("(%d,%d)",x,y);x=u_x[x][y];y=u_y[x][y];}printf("最短路径长度为：%d",d[0][0]);return0;}