国家集训队论文集俞玮.doc

国家集训队论文集俞玮.doc

ID:52712217

大小:84.50 KB

页数:5页

时间:2020-03-29

国家集训队论文集俞玮.doc_第1页
国家集训队论文集俞玮.doc_第2页
国家集训队论文集俞玮.doc_第3页
国家集训队论文集俞玮.doc_第4页
国家集训队论文集俞玮.doc_第5页
资源描述:

《国家集训队论文集俞玮.doc》由会员上传分享,免费在线阅读,更多相关内容在教育资源-天天文库

1、基本动态规划问题的扩展应用动态规划可以有效的解决许多问题,其中有许多问题的数学模型,尤其对一些自从57年就开始研究的基本问题所应用的数学模型,都十分精巧。有关这些问题的解法,我们甚至可以视为标准——也就是最优的解法。不过随着问题规模的扩大化,有些模型显出了自身的不足和缺陷。这样,我们就需要进一步优化和改造这些模型。一.程序上的优化:程序上的优化主要依赖问题的特殊性。我们以f(XT>=opt{f(uT>}+A(XT>,uTÎPred_Set(XT>这样的递推方程式为例<其中A(XT>为一个关于XT的确定函

2、数,Pred_Set(XT>表示XT的前趋集)。我们设状态变量XT的维数为t,每个XT与前趋中有e维改变,则我们可以通过方程简单的得到一个时间复杂度为O(nt+e>的算法。b5E2RGbCAP当然,这样的算法并不是最好的算法。为了简化问题,得到一个更好的算法。我们设每个XT所对应的g(XT>=opt{f(uT>},则f(XT>=g(XT>+A(XT>,问题就变为求g(XT>的值。下面分两个方面讨论这个问题:p1EanqFDPw1.Pred_Set(XT>为连续集:在这样的情况下,我们可以用g(XT>=o

3、pt{g(Pred(XT>>,f(Pred(XT>>}这样一个方程式来求出g(XT>的值,并再用g(XT>的值求出f(XT>的值。这样,虽然我们相当于对g(XT>和f(XT>分别作了一次动态规划,但由于两个规划是同时进行的,时间复杂度却降为了O(nt>。由于我们在实际使用中的前趋即通常都是连续的,故这个方法有很多应用。例如IOI’99的《小花店》一题就可以用该方法把表面上的时间复杂度O(FV2>降为O(FV>。DXDiTa9E3d2.Pred_Set(XT>为与XT有关的集合:这样的问题比较复杂,我们以

4、最长不下降子序列问题为例。规划方程为:f(i>=max{f(j>}+1,d[i]≥d[j]。i>j。通常认为,这个问题的最低可行时间复杂度为O(n2>。不过,这个问题只多了一个d[i]≥d[j]的限制,是不是也可以优化呢?我们注意到max{f(j>}的部分,它的时间复杂度为O(n>。但对于这样的式子,我们通常都可以用一个优先队列来使这个max运算的时间复杂度降至O(logn>。对于该问题,我们也可以用这样的方法。在计算d[i]时,我们要先有一个平衡排序二叉树<例如红黑树)对d[1]~d[i-1]进行排序

5、。并且我们在树的每一个节点新增一个MAX域记录它的左子树中的函数f的最大值。这样,我们在计算f(i>时,只需用O(logn>时间找出不比d[i]大的最大数所对应的节点,并用O(1>的时间访问它的MAX域就可以得出f(i>的值。并且,插入操作和更新MAX域的操作也都只用O(logn>的时间<我们不需要删除操作),故总时间复杂度为O(nlogn>。实际运行时这样的程序也是十分快的,n=10000时用不到1秒就可以得出结果,而原来的程序需要30秒。RTCrpUDGiT从以上的讨论可以看出,再从程序设计上对问题

6、优化时,要尽量减少问题的约束,尽可能的化为情况1。若不可以变为情况1,那么就要仔细考虑数据上的联系,设计好的数据结构来解决问题。5PCzVD7HxA二.方程上的优化:5/5对于方程上的优化,其主要的方法就是通过某些数学结论对方程进行优化,避免不必要的运算。对于某一些特殊的问题,我们可以使用数学分析的方法对写出的方程求最值,这样甚至不用状态之间的递推计算就可以解决问题。不过用该方法解决的问题数量是在有限,并且这个方法也十分复杂。不过,却的确有相当数量的比较一般的问题,在应用某些数学结论后,可以提高程序的效

7、率。jLBHrnAILg一个比较典型的例子是最优排序二叉树问题的算法。但是否会有更有效的算法呢?我们考虑一下w(i,j>的性质。它表示的是结点i到结点j的频率之和。很明显,若有[i,j]Í[i’,j’],则有w[i,j]£w[i’,j’],这样可知C[i,j]具有凸性[1]。为了表示方便,我们记Ck(i,j>=w(i,j>+C[i,k-1]+C[k,j],并用Ki,j表示取到最优值C[i,j]时的Ck(i,j

8、>的k值。我们令k=Ki,j-1,并取i+w(i,j>+C[i,.k-1]+C[i,k’-1],可得:LDAYtRyKfECk’(i,j-1>+Ck(i,j>£Ck’(i,j>+Ck(i,j-1>由k的定义可知Ck(i,j-1>£Ck’(i,j-1>,故Ck(i,j>£Ck’(i

当前文档最多预览五页,下载文档查看全文

此文档下载收益归作者所有

当前文档最多预览五页,下载文档查看全文
温馨提示:
1. 部分包含数学公式或PPT动画的文件,查看预览时可能会显示错乱或异常,文件下载后无此问题,请放心下载。
2. 本文档由用户上传,版权归属用户,天天文库负责整理代发布。如果您对本文档版权有争议请及时联系客服。
3. 下载前请仔细阅读文档内容,确认文档内容符合您的需求后进行下载,若出现内容与标题不符可向本站投诉处理。
4. 下载文档时可能由于网络波动等原因无法下载或下载错误,付费完成后未能成功下载的用户请联系客服处理。