注册 登录  
 加关注
查看详情
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

zorksylar

Nothing is impossible , if distributed.

 
 
 

日志

 
 

动态规划_一个菜鸟的体会  

2011-08-09 09:29:02|  分类: ACM_动态规划 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
动态规划:
说明:本人菜鸟一个,最近做了一些DP的问题,有感而发
动规是一种记忆化的搜索,在思考问题的时候,可以先按照搜索的思路想解决问题的方法,然后在对这种解法进行分析,看是否有重复计算的地方和最优子结构,然后再在搜索的基础上把重复计算的地方进行记忆化,找到递推关系,这个问题就迎刃而解了。
思考的时候,可以按照递归的方式思考,
另外:DP的问题一般分为两种思考方式:顺推和逆推,
顺推就是当递推方程不好找到的时候,就看访问当前的点能够对以后的点进行怎样的更新,抱着一种更新的思想,这样当这个点所有之前的点都访问过之后,这个点的解就求出来了。
逆推就是找当前点是怎样由这个点之前的点求出来的,找到递推方程。

推荐参考资料:
黑书和黑书的课件
入门题目:
(1)背包问题. (poj1837,poj1276) 
     (2)型如下表的简单DP(可参考lrj的书 page149):  
       1.E[j]=opt{D[i]+w(i,j)} (poj3267,poj1836,poj1260,poj2533) 
       2.E[i,j]=opt{D[i-1,j]+xi,D[i,j-1]+yj,D[i-1][j-1]+zij} (最长公共子序列)     
         (poj3176,poj1080,poj1159) 
       3.C[i,j]=w[i,j]+opt{C[i,k-1]+C[k,j]}.(最优二分检索树问题)  
 提高题目:
     (1)较为复杂的动态规划(如动态规划解特别的施行商问题等) 
         (poj1191,poj1054,poj3280,poj2029,poj2948,poj1925,poj3034) 
     (2)记录状态的动态规划. (POJ3254,poj2411,poj1185) 
     (3)树型动态规划(poj2057,poj1947,poj2486,poj3140) 


以下摘自PKU陈峰宏大牛的PKU_ACM暑期课程的课件:http://poj.org/summerschool/pku_acm_train.htm 
递推——将最优性变成统计的动态规划
递推同样需要状态的划分和无后效性
但是递推的转移函数(状态转移方程)通常不包括max和min,而是一些统计函数——如求和
递推的难点通常在状态建模和转移函数的确定
综上所述,将递推看成动态规划的一种形式是没问题的
因此,接下来的内容将不区别动态规划和递推
思路:
核心思想——提取信息的共性,将影响到今后状态决策的信息提取出来。

提取的信息要尽可能精简,信息提取的思路可以从搜索开始设想(DP本来就是一种记忆化的搜索,本人添加)

寻找一个合适的顺序去求得每个状态——弱化阶段的概念
提取信息的共性:
动态规划可以看成是对搜索的一种记忆化优化

动态规划需要尽量使得搜索的状态保存的信息尽可能的精简——说白了就是搜索的总状态数越少越好。这一点和搜索是相同的

和搜索不同的是,动态规划会需要按照某种特定的顺序

倒推---寻找最长不降子序列
寻找求得当前状态f[i]的方法

F[0]=0;
For (i=1;i<=n;i++)
{
       for (j=0;j<i;j++) 
       if (a[j]<=a[i]&&f[j]+1>f[i]) f[i]=f[j]+1;
}

顺推---寻找最长不降子序列--更新思想
根据当前状态f[i],寻找能够更新的状态

For (i=1;i<=n;i++) f[i]=1;
For (i=1;i<n;i++)
{
       for (j=i+1;i<=n;j++)
       if (f[i]+1>f[j]&&a[i]<=a[j]) f[j]=f[i]+1;
}

由于习惯性,几乎所有的动态规划书上都使用了倒推形式的状态转移方程。这导致

大多数动态规划顺推、倒推思想都能用——但是,在很多时候,使用顺推思路会方便很多。

顺推思路的一个基本应用——dijstra

有些时候不知道本状态会由哪些状态转移过来,但是知道本状态会对哪些状态产生影响。

这种时候就是和用顺推思路,而不是死板硬套形式化的状态转移方程的倒推思路

根据时间复杂度分析,合理选择模型也很重要
  评论这张
 
阅读(142)| 评论(2)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2018