动态规划初步.ppt

动态规划初步JSOI2007夏令营B层次(泰州)苇嫡稚炎谰字脚悲卫汀傈锅作笆为飞纱刮撅侧硕馋豢究遂匡窑抨源恰榔薪动态规划初步动态规划初步问题:城市交通有n个城市,编号1~n,有些城市之间有路相连,有些则没有,有路则当然有一个距离。现在规定只能从编号小的城市走到编号大的城市,问你从编号为1的城市走到编号为n的城市要花费的最短距离是多少?输入格式:先输入一个n,表示城市数,n<100。下面的n行,是一个n*n的邻接矩阵map[1..n,1..n]。map[i,j]=0,表示城市i和城市j之间没有路相连,否则为两者之间的距离。输出格式:一个数,表示从城市1走到城市n的最短距离。输入数据保证可以从城市1走到城市n。动态规划的引入抵汁队续害疾湛赊揉吸搪瀑仕钱害杭犁襄镜懂资祈兔易趋挎绅情澳裸诌实动态规划初步动态规划初步输入样例:110530000000050016300000300080400000100000560006800005000030000000800040000003000055000003000600000040000083000300000003430动态规划的引入孝伪捧慌内址乡医恰评市芍盯听吞防辛颁青贬取工衣赘陌代忱萍境耙房丧动态规划初步动态规划初步设一个数组dis[1..n],dis[i]表示城市1到城市i的最短距离。题目就是要求dis[n]。根据题目的限制条件:只能从编号小的城市到编号大的城市。显然,我们可以从城市1、城市2、……、城市n-1到城市n,前提是城市i与城市n之间有路,其中i=1,2,3,……,n-1。所以,dis[n]就应该取dis[i]+map[i,n]中的最小值,且要求map[i,n]<>0,i=1,2,3,……,n-1。也就是说要求dis[n],就必须先求出dis[1]~dis[n-1],类似于递推算法中的“倒推法”,那么如何求dis[n-1]呢?dis[n-1]=min{dis[i]+map[i,n-1]}且要求map[i,n-1]<>0,i<n-1。城市交通分析淋了彤眺煮剔黑遂彼伦径雇香九室慕境确匝怕鲁状弱辩拇缅薛顺葵剩暇荷动态规划初步动态规划初步现在我们把问题一般化,如何求dis[i]呢?其中,i=1..n。Dis[i]=min{dis[j]+map[j,i]}要满足:map[j,i]<>0,j=1..i-1这是一个类似于递归的公式,意思为:要求dis[n]就要先求dis[n-1]~dis[1],要求dis[n-1]就要先求dis[n-2]~dis[1],而要求dis[i],就要先求dis[i-1]~dis[1],……,而dis[1]=0。在具体计算的时候,只要从dis[1]开始“顺推”下去,依次求出dis[2]、dis[3]、……、dis[n-1]、dis[n]即可。城市交通分析壳花八友斋疮梗阳速铀标陆那漾蚁漂罩汛鳃挺近湘沼帜撮讲领抠铸秦洒噬动态规划初步动态规划初步……dis[1]:=0;fori:=2tondobeginmin:=maxint;{用打擂台的方法求出最小值}forj:=1toi-1doifmap[j,i]<>0thenifdis[j]+map[j,i]<minthenmin:=dis[j]+map[j,i];dis[i]:=min;end;writeln('min=',dis[n]);城市交通分析披高奋诲翌揣奏钧绿穴的坍犯痕警燎济俘浇肺泌劫司确哨弹匙话功馒哭俱动态规划初步动态规划初步动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年,“最优化原则”,1957年发表了他的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用,取得了显著的效果。动态规划运用于信息学竞赛是在90年代初期,它以独特的优点获得了出题者的青睐。此后,它就成为了信息学竞赛中必不可少的一个重要方法,几乎在所有的国内和国际信息学竞赛中,都至少有一道动态规划的题目。所以,掌握好动态规划,是非常重要的。夸乌哪莎郝怯铂买桑卒凹煎常秃压答痕耕啤坦坐渝足船琴悸寿拴浚畔擅肌动态规划初步动态规划初步动态规划简介动态规划中有很多深奥的概念,使用动态规划也有很多前提条件,它与递推、递归也有着密切的联系,这些都要等到我们有一点编程经历后才好谈起,所以,我们先放开这些理论,不要被这些理论吓倒,而是去尝试分析和解决几个经典动态规划题目。学****动态规划最重要的是“一种思想方法和解题过程”,请大家积极动脑动手,跟着我一起分析和体会其中的方法和过程,然后再独立去思考和实践。烘簧有架兼希蕾土在实昼忿宅朴碌融鼠鹿锣龚秽摈修遂徊疲霜残栖瞄臻订动态规划初步动态规划初步动态规划简介拦截导弹(N