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年有关实践活动的心得体会 33页

11-19年高考物理真题分专题汇编之84电表的改装.. 8页

工艺参数对Ni-SiO 2镀层耐蚀性的影响 4页

2025年嘉兴职业技术学院单招职业技能测试题库.. 65页

2025年有关垃圾分类的作文800字 9页

2025年有关圣诞的作文范文 4页

工程机械电气故障应急修理方法 3页

工程机械产品色彩与视觉效果浅析 3页

2025年有关压岁钱的作文450字 4页

2025年有关军训的作文700字 10页

2025年商洛职业技术学院单招职业倾向性测试题.. 63页

2025年有关写童年趣事的优秀范文600字 4页

2025年有关写暑假趣事精彩作文500字 5页

2025年商丘学院单招职业倾向性测试题库推荐 66页

2025年有关写我心中的狼优秀范文 4页

2025年有关写好习惯伴我成长作文600字 5页

2025年有关关于诚信的作文 8页

服装企业NC财务供应链项目实施方案 98页

2025年有关伴我成长的作文600字 7页

2025年唐山幼儿师范高等专科学校单招职业技能.. 65页

岩溶地区紧邻地铁隧道两侧深基坑施工技术 3页

2025年有关于描写珍珠鸟的作文 5页

2025年有关于写爱国主义的优秀范文 4页

山西长治区块煤层气集水系统优化 3页

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

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

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

牌匾施工方案 26页

牌匾规范施工方案 10页

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