资源描述：
《动态规划算法的一个应用.doc》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、动态规划算法的一个应用邸楠dinan@net.cs.pku.edu.cn摘要本文用动态规划算法对一族问题作了分析和解决，并分析了所给算法的复杂度。关键词动态规划1问题的提出1.1简单的开始考虑一个国际象棋盘，每个格子里放若干粒谷子，一枚棋子从左上角的格子按照规则（legal）走法（每次只能向下或向右走一格）走到右下角的格子，每走到一格就把此格中的谷子拿走。那么怎样走才能使拿到的谷子数目最大？1.2稍微复杂的情况如果这枚棋子还要按照规则走法（每次只能向上或向左走一格）从右下角走回到左上角（注意回来时以前走过的格子里的谷子就没有啦），那
2、么怎样走才能使拿到的谷子数目最多？1.3更一般的情况更一般的这枚棋子在左上角的格子和右下角的格子间走k（）次（当的时候，可以经棋盘上的所有谷子都拿走），那么怎么走才能使拿到的谷子数目最多？1.4其他问题如果把问题推广到3维或更多维呢？考虑你的解法的算法复杂度。考虑这个问题的算法复杂度。1一些记号1.1一些记号为了考虑问题的方便，下面考虑问题一般情况：设M为n*n矩阵，，其中；i=1ton,j=1ton对上面的矩阵中的某一个格子(i,j)定义其sum值为sum(i,j)=i+j那么对于一条从(1,1)到(n,n)的规则路径（legal
3、path）可以按照路径上各自的sum值从小到大排列，相邻两个格子的sum值差1。例如：(1,1),(1,2),(1,3),(2,3),(3,3)就是一条从(1,1)到(3,3)的规则路径。1.2一个运算及其性质对上面的矩阵定义如下的运算SPADD，满足：的非重复求和。例如：SPADD((1,1),(1,2),(1,1),(2,1),)=M(1,1)+M(1,2)+M(2,1)特别的定义SPADD((x,y))=M(x,y)容易得到SPADD有下面的性质：IFF与的交集为空。上面性质的一个推论是：对于从(1,1)到(i,j)和(p,q
4、)的两条合法路径（下面的表示是按照sum的值排序）,：和如果i+j=p+q那么：1问题的解决1.1初步设想这类问题是一个典型的动态规划问题，其问题带有最优子结构的性质，下面寻找递推关系，利用动态规划来解决这类问题。1.2第一个问题的解答原问题是从(1,1)到(n,n)引一条规则路径，使在这条路径上的谷子总数最大。更一般的考虑从(1,1)到(i,j)引一条规则路径，使在这条路径上的谷子总数最大。设是这个最大值，那么即为所求。令==0;i=1ton,j=1ton容易有：=M(1,1)=SPADD((1,1))i=1ton,j=1ton对
5、(1)的说明是：考虑最优子结构有从(1,1)到(i,j)的最优路线必然包括从(1,1)到(i-1,j)的最优路线或从(1,1)到(i,j-1)的最优路线从上面的递推式可以作出下面的代码：intfunction1(M,n,n)result[1][1]=M(1,1)fori=1tonresult[i][0]=0forj=1tonresult[0][j]=0forsum=2ton+nfori=max(1,sum-n)tomin(n,sum-1)j=sum–iresult[i][j]=max(result[i-1][j],result[i]
6、[j-1])+SPADD((i,j))index[i][j]=...//记录最优路径returnresult[n][n]如果想找到这条最优路径，只要从index这个表中查寻即可，这里就不再讨论了。1.1第二个问题的解答原来的问题是从(1,1)到(n,n)引两条规则路径，使在这两条路径上的谷子数目之和最大。下面讨论更一般的问题，设i+j=p+q,考虑从(1,1)到(i,j)和(p,q)分别引一条规则路径，使在这两条路径上的谷子数目之和最大。设是这个最大值那么即为所求。类似3.2对result作初始化容易有：=M(1,1)=SPADD(
7、(1,1))根据的定义有，对任意的从(1,1)到(i,j)和(p,q)的两条规则路径，按照sum做升序排列:===即=(n,n)(i,j)(i-1,j)(i,j-1)(p,q)(p-1,q)(p,q-1)(1,1)根据上面的递推式，有下面的代码：intfunction2(M,n,n)result[1][1][1][1]=M(1,1)fori=1tonforj=1tonforp=1tonforq=1tonresult[0][j][p][q]=0result[i][0][p][q]=0result[i][j][0][q]=0result
8、[i][j][p][0]=0forsum=2ton+nfori=max(1,sum-n)tomin(n,sum-1)forp=max(1,sum-n)tomin(n,sum-1)j=sum–iq=sum-presult[i][j][p
