文档介绍：动态规划初步
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)
问题描述:
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有一个缺陷