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

和申的个人主页

专注于java开发,1985wanggang

 
 
 

日志

 
 

动态规划实现中的问题  

2008-11-05 14:10:05|  分类: 算法 |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

应用动态规划解决问题,在有了基本的思路之后,一般来说,算法实现是比较好考虑的。但有时也会遇到一些问题,而使算法难以实现。动态规划思想设计的 算法从整体上来看基本都是按照得出的递推关系式进行递推,这种递推相对于计算机来说,只要设计得当,效率往往是比较高的,这样在时间上溢出的可能性不大, 而相反地,动态规划需要很大的空间以存储中间产生的结果,这样可以使包含同一个子问题的所有问题共用一个子问题解,从而体现动态规划的优越性,但这是以牺 牲空间为代价的,为了有效地访问已有结果,数据也不易压缩存储,因而空间矛盾是比较突出的。另一方面,动态规划的高时效性往往要通过大的测试数据体现出来 (以与搜索作比较),因而,对于大规模的问题如何在基本不影响运行速度的条件下,解决空间溢出的问题,是动态规划解决问题时一个普遍会遇到的问题。

对于这个问题,可以考虑从以下一些方面去尝试:

一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑,仅仅存储必不可少的内容,以及数据存储范围上精打细算(按位存储、压缩存储等)。当然 这要因问题而异,进行分析。另外,在实现动态规划时,一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策,这对于倒推求得一种实现最 优解的方法是十分方便的,而且处理速度也有一些提高。但是在内存空间紧张的情况下,我们就应该抓住问题的主要矛盾。省去这个存储决策的数组,而改成在从最 优解逐级倒推时,再计算一次,选择某个可能达到这个值的上一阶段的状态,直到推出结果为止。这样做,在程序编写上比上一种做法稍微多花一点时间,运行的时 效也可能会有一些(但往往很小)的下降,但却换来了很多的空间。因而这种思想在处理某些问题时,是很有意义的。

但有时,即使采用这样的方法也会发现空间溢出的问题。这时就要分析,这些保留下来的数据是否有必要同时存在于内存之中。因为有很多问题,动态规划递 推在处理后面的内容时,前面比较远处的内容实际上是用不着的。对于这类问题,在已经确信不会再被使用的数据上覆盖数据,从而使空间得以重复利用,如果能有 效地使用这一手段,对于相当大规模的问题,空间也不至于溢出(为了求出最优方案,保留每一步的决策仍是必要的,这同样需要空间)。

一般地说,这种方法可以通过两种思路来实现:一种是递推结果仅使用Data1和Data2这样两个数组,每次将Data1作为上一阶段,推得 Data2数组,然后,将Data2通过复制覆盖到Data1之上,如此反复,即可推得最终结果。这种做法有一个局限性,就是对于递推与前面若干阶段相关 的问题,这种做法就比较麻烦;而且,每递推一级,就需要复制很多的内容,与前面多个阶段相关的问题影响更大。另外一种实现方法是,对于一个可能与前N个阶 段相关的问题,建立数组Data[0..N],其中各项为最近N各阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的访问只要对应成对数组 Data中下标为k mod (N+1)的单元的访问就可以了。这种处理方法对于程序修改的代码很少,速度几乎不受影响,而且需要保留不同的阶段数也都能很容易实现。

当采用以上方法仍无法解决内存问题时,也可以采用对内存的动态申请来使绝大多数情况能有效出解。而且,使用动态内存还有一点好处,就是在重复使用内存而进行交换时,可以只对指针进行交换,而不复制数据,这在实践中也是十分有效的。

  评论这张
 
阅读(499)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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