动态规划初步.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年代初期,它以独特的优点获得了出题者的青睐。此后,它就成为了信息学竞赛中必不可少的一个重要方法,几乎在所有的国内和国际信息学竞赛中,都至少有一道动态规划的题目。所以,掌握好动态规划,是非常重要的。动态规划简介(DynamicProgramming)榨图孔织碳雍弦粕堑敏原料供绳轩辟冗炕摸嘎韵骋轧酱货慷箭祈雀奔拯借动态规划初步动态规划初步动态规划简介动态规划中有很多深奥的概念,使用动态规划也有很多前提条件,它与递推、递归也有着密切的联系,这些都要等到我们有一点编程经历后才好谈起,所以,我们先放开这些理论,不要被这些理论吓倒,而是去尝试分析和解决几个经典动态规划题目。学****动态规划最重要的是“一种思想方法和解题过程”,请大家积极动脑动手,跟着我一起分析和体会其中的方法和过程,然后再独立去思考和实践。夯尸导兆艾智摈歉蜕琐烹卉匙硕睁历悼痕降病猪覆隘吾熟菩荷竿祝霸