1 / 41
文档名称:

动态规划初步.ppt

格式:ppt   页数:41页
下载后只包含 1 个 PPT 格式的文档,没有任何的图纸或源代码,查看文件列表

如果您已付费下载过本站文档,您可以点这里二次下载

分享

预览

动态规划初步.ppt

上传人:endfrs 2015/6/6 文件大小:0 KB

下载得到文件列表

动态规划初步.ppt

相关文档

文档介绍

文档介绍:动态规划初步
JSOI2007夏令营B层次(泰州)
1
问题:城市交通
有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。
动态规划的引入
2
输入样例:
11
0 5 3 0 0 0 0 0 0 0 0
5 0 0 1 6 3 0 0 0 0 0
3 0 0 0 8 0 4 0 0 0 0
0 1 0 0 0 0 0 5 6 0 0
0 6 8 0 0 0 0 5 0 0 0
0 3 0 0 0 0 0 0 0 8 0
0 0 4 0 0 0 0 0 0 3 0
0 0 0 5 5 0 0 0 0 0 3
0 0 0 6 0 0 0 0 0 0 4
0 0 0 0 0 8 3 0 0 0 3
0 0 0 0 0 0 0 3 4 3 0
动态规划的引入
3
设一个数组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。
城市交通分析
4
现在我们把问题一般化,如何求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]即可。
城市交通分析
5
……
dis[1]:=0;
for i:=2 to n do
begin
min:=maxint; {用打擂台的方法求出最小值}
for j:=1 to i-1 do
if map[j,i]<>0 then
if dis[j]+map[j,i]<min then min:=dis[j]+map[j,i];
dis[i]:=min;
end;
writeln('min=',dis[n]);
城市交通分析
6
动态规划是运筹学的一个分支。它是解决多阶段决策过程最优化问题的一种方法。1951年,“最优化原则”,1957年发表了他的名著《动态规划》,该书是动态规划方面的第一本著作。动态规划问世以来,在工农业生产、经济、军事、工程技术等许多方面都得到了广泛的应用,取得了显著的效果。
动态规划运用于信息学竞赛是在90年代初期,它以独特的优点获得了出题者的青睐。此后,它就成为了信息学竞赛中必不可少的一个重要方法,几乎在所有的国内和国际信息学竞赛中,都至少有一道动态规划的题目。所以,掌握好动态规划,是非常重要的。
动态规划简介
(Dynamic Programming)
7
动态规划简介
动态规划中有很多深奥的概念,使用动态规划也有很多前提条件,它与递推、递归也有着密切的联系,这些都要等到我们有一点编程经历后才好谈起,所以,我们先放开这些理论,不要被这些理论吓倒,而是去尝试分析和解决几个经典动态规划题目。
学习动态规划最重要的是“一种思想方法和解题过程”,请大家积极动脑动手,跟着我一起分析和体会其中的方法和过程,然后再独立去思考和实践。
8
动态规划简介
拦截导弹(NOIP1999)
问题描述:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷

最近更新

2025年张家口职业技术学院单招职业技能考试题.. 72页

2025年哈尔滨铁道职业技术学院单招职业倾向性.. 72页

2025年唐山幼儿师范高等专科学校单招职业适应.. 76页

2025年德宏职业学院单招职业适应性测试题库1套.. 74页

2025年德州科技职业学院单招职业适应性测试题.. 72页

2025年德阳城市轨道交通职业学院单招综合素质.. 74页

2025年忻州职业技术学院单招职业倾向性测试题.. 71页

2025年四川中医药高等专科学校单招职业技能考.. 73页

初中语文现代文阅读答题技巧ppt课件 39页

2025年四川卫生康复职业学院单招职业适应性测.. 73页

2025年四川商务职业学院单招职业技能测试题库.. 74页

2025年成都外国语学院单招职业倾向性考试题库.. 73页

2025年四川希望汽车职业学院单招综合素质考试.. 73页

2025年成都文理学院单招职业倾向性考试题库最.. 72页

2025年四川文化艺术学院单招职业倾向性考试题.. 73页

2025年扬州工业职业技术学院单招综合素质考试.. 71页

2025年扬州市职业大学单招职业技能考试题库完.. 72页

各种常见引流管的护理-PPT 36页

伊利乳业纯牛奶工艺流程图 4页

水利工程中隧洞固结灌浆施工技术分析 32页

牌匾施工方案 26页

牌匾规范施工方案 10页

年产15万吨环己醇工艺设计【完整版】 37页

粗盐提纯除去可溶性杂质课件 19页

西田龙雄:关于十六世纪西康省藏语天全方言—.. 92页

起重机试运转检验记录 1页

wh-6f电脑袜机成圈机构设计与优化 95页