文档介绍：教案要点
文件名:;
授课时间:第十五讲
授课内容:第九章动态规划
预备知识:图论、LP问题.
复****图论的基本概念,最短路算法.
难点:标号算法、最优化原理.
重点:最短路问题的Dijkstra算法,动态规划问题,最优化原理,投资问题等动态规划的应用实例。
下节预****教材第十章图与网络模型。
5/10/2018
运筹学
计算机系信管03级
.
5/10/2018
第九章动态规划 Dynamic Programming
最短路径问题
基本概念
最优化原理
动态规划的应用
5/10/2018
最短路问题
无(有)向图的边赋权
赋权图
最短路径
Dijkstra的标号法
图上作业
表上作业
5/10/2018
最短路问题的标号法
Dijkstra标号法:所有结点分为:
未标号:尚未标号(缺或写“∞”);
临时标号:从已永久标号的点一步可达的,比较后标“长”最小的数;
永久标号:所有当前已临时标号的结点中最小者改为“永久”,(加框)。
可从“起点”做起顺推,也可从“终点”一步一步地逆推。
5/10/2018
(顺走)
A
B1
B2
C1
C2
C3
D1
D2
E
3
6
4
4
4
4
3
2
5
5
3
1
2
2
0
4
3
6
9
7
5
10
9
8
9
12
3
5
6
8
7
9
12
4
最短路为:
A→B1→C1→D1→E
最短路问题的Dijkstra标号法
5/10/2018
12
(逆推)
A
B1
B2
C1
C2
C3
D1
D2
E
3
6
4
4
4
4
3
2
5
5
3
1
2
2
12
9
9
6
8
7
4
5
9
8
6
4
7
5
0
9
最短路为:
A→B1→C1→D1→E
10
13
最短路问题的标号法
5/10/2018
最短路问题的表上作业法
0
3
6 5 9
+∞+∞+∞
4
6 5 7
+∞+∞+∞
5
6
7 9 10
+∞
6
7 8 10
+∞
7
9 12
+∞
8
9
12
8 9
3
4
4
+∞+∞+∞
+∞+∞+∞
5/10/2018
最短路问题的Dijkstra标号法
小华家住在下图中①处,每天要到在⑨处的小
学上学,街道位置
及长度如图,请给
小华找一条最短上
学路线,并求出该
最短的路径之长。
1
9
5/10/2018
3
6
9
2
5
8
1
4
7
26 33
35 31 29
28 33
32 24 22
27 36
0
32
32
27
27
51
63
67
82
84
113
51
63
67
82
84
113
115
最短路:
①
↓
④
↓
⑤
↓
⑧
↓
⑨
总长:
113
5/10/2018