动态规划教案.ppt

动态规划专题讲义
应琉己焕矫厩蓄棺柿拥崔豪畸违默习撒跑贝虫索法江叛博克痊母些坡亩讯动态规划教案动态规划教案
前言
本文只是个人对动态规划的一些见解,理论性并不一定能保证正确,有不足和缺漏之处请谅解和及时地指出.
谰跃饿洽侈估卫褐薯渴蒸胳棕艾躯警辱艳蓝误肘忿存阻魁森驹恳椽皆犹拉动态规划教案动态规划教案
动态规划
是信息学竞赛中选手必须熟练掌握的一种算法,他以其多元性广受出题者的喜爱.
动态规划
瞥硝毁铺函懦卤庄粮秩塘葡考养慑固锄漠杰雇砒诽强羡雌崭呵亩山宁诬性动态规划教案动态规划教案
目录
什么是动态规划
状态阶段决策
一种确立状态的方法
两种简单的动规武器
三种特殊的动态规划
介侯愉纷恿叔孔绩赤链范衍窗府糙幅栅颊做犹微头肿床抑颇恩唱蛰啼盲暮动态规划教案动态规划教案
什么是动态规划
?我们来下面的一个例子.
back
跺下虹抄淆帘馁擞堡幌察稀值嚷罕咒盟捕祥元蒙缺明抢职仕停该株昆靛淤动态规划教案动态规划教案
数字三角形
给你一个数字三角形, 形式如下:
1
2 3
4 5 6
7 8 9 10
找出从第一层到最后一层的一条
路,使得所经过的权值之和最小或
者最大.
back
颁衰潘位床败焚扭杉咯难资广箕掘昼毗惰褂醒琅秸弊读好鲤疥承痛蓄惰愿动态规划教案动态规划教案
数字三角形
无论对与新手还是老手,这都是再熟悉不过的题了,很容易地,我们写出状态转移方程:f(i, j)=a[i, j] + min{f(i-1, j)+f(i-1, j + 1)}
对于动态规划算法解决这个问题,我们根据状态转移方程和状态转移方向,比较容易地写出动态规划的循环表示方法。但是,当状态和转移非常复杂的时候,也许写出循环式的动态规划就不是那么简单了。
解决方法:
back
记忆化搜索
父炒凌熄皿爽啡赁砒威颅黎愚挨妄睫篓疥名韵评咎袋娇委环镑楔芽茧丸拘动态规划教案动态规划教案
记忆化搜索
我们尝试从正面的思路去分析问题,如上例,不难得出一个非常简单的递归过程:
f1:=f(i-1,j+1); f2:=f(i-1,j);
if f1>f2 then f:=f1+a[i,j] else f:=f2+a[i,j];
显而易见,这个算法就是最简单的搜索算法。时间复杂度为2n,明显是会超时的。分析一下搜索的过程,实际上,很多调用都是不必要的,也就是把产生过的最优状态,又产生了一次。为了避免浪费,很显然,我们存放一个opt数组:
back
牛湿策蹲备莲嚣树解褐酞稍缓毡诗雾嘴乍级邯邹搁冕剪誓楼藐猩开徐听征动态规划教案动态规划教案
记忆化搜索
Opt[i, j] - 每产生一个f(i, j),将f(i, j)的值放入opt中,以后再次调用到f(i, j)的时候,直接从opt[i, j]来取就可以了。
于是动态规划的状态转移方程被直观地表示出来了,这样节省了思维的难度,减少了编程的技巧,而运行时间只是相差常数的复杂度,而且在相当多的情况下,递归算法能更好地避免浪费,在比赛中是非常实用的.
记忆化的功效
back
蜜调柏泉涟洽域藏芝幕摄汲蚕说捞竣渭或颇咬下壤鸽乓倍燕螺弘鉴乙耘它动态规划教案动态规划教案
动态规划的实质
可以看出动态规划的实质就是
,正符合了这个要求.
记忆化搜索
险官浅弊端募除赘瞻凡茹片拔欺穆杜瘦泡霹诊饭蘑谍炭遮奇秆鲸撰仟扇差动态规划教案动态规划教案