[求助]动态规划 - C语言论坛

楼主

问题点数：0 回复次数：7

[求助]动态规划

从矩形的左下角走到右上角，每数字为经过该格所需的代价，怎样走使得代价最小。书上的动态规划的解法说是从右上角那点往前面倒推，但是这样到了倒数第二步后选择了1，（第2行第4列），则无法取得最小代价。请知道的解释一下

1 1 8 2

1 8 9 1

1 9 9 9

1 8 7 5

搜索更多相关主题的帖子: 动态规划　代价　数字　右上角　

第 2 楼

得分:0

有点复杂，没什么好的算法，若求最佳路径，只有遍历所有路径才能保证。从右上往左下也好，从左下往右上也好都是一样，象这种问题采用什么算法与数据分布的规律性相关，没有什么算法能满足所有的数据分布模式。

思考ing。。。。。

九洲方除百尺冰，映秀又遭蛮牛耕。汽笛嘶鸣国旗半，哀伤尽处是重生。 -老K
治国就是治吏。礼义廉耻，国之四维。四维不张，国之不国。 -毛泽东

第 3 楼

得分:0

听说解这种题最好的方法就是动态规划，但是我觉得书上的程序有问题

第 4 楼

得分:0

这个题目可以用类似图论的最短路算法解决，
djstra，好象是这个（记不太清楚了）；

我喜欢创造，一只扑腾着翅膀向天空飞翔的乌鸦

第 5 楼

得分:0

我把自己写的代码贴出来你参考一下吧，思想是djstra的思想，好象这个思想的本质也是动态规划

#include <stdio.h> FILE *fi; int data[50][50],len[50][50],dest[2],n; void in(int n) {int i,j; for(i=0;i<n;i++) for(j=0;j<n;j++) fscanf(fi,"%d",&data[i][j]);} int change(int a,int b,int da) {int t; /*change函数用于更新标记len[a][b] da为和它相邻的一个刚确定最短路径的结点的最短路径值，更新目标是更新目前已经知道的最短路径长*/ if(a<0||b<0||a>=n||b>=n)return 0; t=da-data[a][b]; if(len[a][b]==0) {len[a][b]=t; return 0;} if(len[a][b]<t)len[a][b]=t; return 0; } int find() {int i,j,min,mi1,mi2; min=-30000; /*这是算法的核心函数，它找出目前已经知道的所有最短路径长中最短的，它必然是起点到该点的最短路径长*/ for(i=0;i<n;i++) for(j=0;j<n;j++) {if(len[i][j]>=0)continue; if(len[i][j]>min) {mi1=i;mi2=j; min=len[i][j];}} /*每次只要更新4个目标，思考一下为什么*/ change(mi1+1,mi2,len[mi1][mi2]); change(mi1-1,mi2,len[mi1][mi2]); change(mi1,mi2+1,len[mi1][mi2]); change(mi1,mi2-1,len[mi1][mi2]); len[mi1][mi2]=-len[mi1][mi2]; if(mi1==dest[0]&&mi2==dest[1]) return 1; else return 0; /*如果得到右上角的最短路径，返回1*/} void djstra() {int i,j; for(i=0;i<n;i++) for(j=0;j<0;j++) len[i][j]=0; dest[0]=0; dest[1]=n-1; len[n-1][0]=data[n-1][0]; len[n-2][0]=-data[n-1][0]-data[n-2][0]; len[n-1][1]=-data[n-1][0]-data[n-1][1]; /*上面为一些必要的初始化,dest储存最终目标（右上角）， len里面储存：当元素>0时:起点到该点的最短路径长；当元素<0时：目前已经知道的最短路径长（但不一定时最短路径） =0；未被标记*/ while(!find());}

int main() {char fn[10]; scanf("%d",&n);/*在这里输入，N(N<=50)即正方形的边长*/ scanf("%s",fn);/*在这里输入输入文件名*/ fi=fopen(fn,"r"); in(n); djstra(); printf("%d\n",len[0][n-1]); getch(); fclose(fi); return 0;}

[此贴子已经被作者于2004-12-28 20:03:02编辑过]

我喜欢创造，一只扑腾着翅膀向天空飞翔的乌鸦