flylee 发布留言 2004-12-25 17:58
[求助]动态规划
从矩形的左下角走到右上角，每数字为经过该格所需的代价，怎样走使得代价最小。书上的动态规划的解法说是从右上角那点往前面倒推，但是这样到了倒数第二步后选择了1，（第2行第4列），则无法取得最小代价。请知道的解释一下
1 1 8 2
1 8 9 1
1 9 9 9
1 8 7 5
Knocker 发布留言 2004-12-27 22:17
有点复杂，没什么好的算法，若求最佳路径，只有遍历所有路径才能保证。从右上往左下也好，从左下往右上也好都是一样，象这种问题采用什么算法与数据分布的规律性相关，没有什么算法能满足所有的数据分布模式。
思考ing。。。。。
flylee 发布留言 2004-12-28 17:32
听说解这种题最好的方法就是动态规划，但是我觉得书上的程序有问题
乌鸦丘比特 发布留言 2004-12-28 18:22
这个题目可以用类似图论的最短路算法解决，
djstra，好象是这个（记不太清楚了）；
乌鸦丘比特 发布留言 2004-12-28 19:46
我把自己写的代码贴出来你参考一下吧，
思想是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);}
int change(int a,int b,int da)
{int t;
/*change函数用于更新标记len[a][j]>=0)continue;
if(len>min)
{mi1=i;mi2=j;
min=len;}}
/*每次只要更新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=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:05
以下是引用knocker在2004-12-27 22:17:11的发言：有点复杂，没什么好的算法，若求最佳路径，只有遍历所有路径才能保证。
对于一些最佳路径问题是不需要遍历所有路径的，遍历是万不得已的方法
xuanzilie 发布留言 2008-7-24 09:22
我觉得如果转化成最短路径的问题 应该求附件里蓝色的图的最短路径
xiaomengxia2008 发布留言 2008-7-24 09:24
忘了忘了
页: [1]
