动态规划优化.ppt

浅谈动态规划优化2009曹文信息学奥林匹克夏令营Author:Will盆剖脾键假刊钓授虑设纯鉴钉楚取敛丹消毒帚茹戌菩丸倍武订降螺挥站炯动态规划优化动态规划优化简介动态规划优化的主要方法:1、降维(优化状态)2、优化转移3、,其实质就是通过改变动态规划的状态含义,或者抛弃一些冗余状态环节,达到减少状态,,当得出某种动态规划模型的时候,不要着急动手,而是需要仔细思考一下,是不是有更好的状态表示方法多积累经验,同时又不能拘泥于死板的模型理论,要有创新意识。*M的空白棋盘,在其中放任意放车(可以不放),要使得放在棋盘上的车两两不能攻击,求方案总数MODP的值。。opt[K][S]表示已经放了前K行,并且每一列是否有车的状态为S(S为一个0/1的2进制序列,那一位为1则表示对应一列已经放过了一个车)的合法方案的数量。比如opt[2][(101)2]即表示前2行放了车且第1,3列有车的状态。,如果放的话则枚举所有没有放车的行,将对应的2进制位标记为1,进行转移。时间复杂度O(NM2M)空间复杂度O(2M)但是……如果N,M>1000该怎么办呢?,我们需要知道的只是有多少列目前没有放车,并不需要知道具体是哪些列没有放车!因此opt[k][(101)2]和opt[k][(110)2]是本质等价的。于是我们可以把状态改为:opt[k][S]表示放置了前k行,并且有S列没有放置。[k+1][S]=opt[k][S]+opt[k][S+1]*(S+1)此时时间复杂度为O(NM)空间复杂度为O(NM)问题得到了解决可见对问题透彻的分析是得出最有效规划方式的前提。,或者某些维是可以合并的。经过合理的分析我们可以抛弃一些冗余信息,减少状态,加速转移。蚌歹隧证鞠埂繁试缺崩仿轰盆伎峻诈携盔牧洲刁巧侍迢膳摸炸边善均妮寺动态规划优化动态规划优化