动态规划讲稿1.docx

第四章 动态规划

第一节 动态规划原理一、基本概念

引例

53【例4－1】最短路程问题。某地区需要由发电厂A至用户端E架设一条高压输电线路，途中经过三个城镇B、C、D，每个城镇又各需建设一个变电站。城镇B和D各有二个站址可供选择，城镇C有三个站址可供选择，相互间地理位置如图4－1所示，图中各线段旁数据表示该段路径相对长度。问如何选址，才能使由A到E所用输电线

5

3

解：问题分4段。

A ?1

B?2

C?3

D?4 E

本例是一个四阶段决策过程。

穷举法：共有2×3×2×1＝12个不同方案，比较后

可得最短路径为：

1 2 3 4

A ?B ?C

2 2

?D ?E

1

最短路线总长为12。

记f ：第k 阶段某位置到E的最短距离，

k

d ：第k 阶段某出发位置至第k 阶段某终点位置

k

的距离。

f(A)、f (C

1 3 2

)、d

2

(B,C

1 3

)表示什么？

目的：求f(A)，

1

?d(A,B

)?f

(B)?

f(A)?min? 1

1 2 1 ?

??1 d(A,B

?

?

1 2

)?f

2

(B)

2

需先求f

2

(B)、f (B

1 2 2

)，进一步，需先求f

3

(C)、f (C)、

1 3 2

f (C)，…

3 3

求解过程：f ?f ?f ?f

4 3 2 1

本例求解过程

k?4时，

f (D

4 1

f (D

4 2

)?4

)?6

k?3时，

f(C

)?min?d3

(C,D

1 1

)?f

4

(D)??min?6?4??8

?1?3 1 d

?

1

?

3

(C,D

1 2

)?f

4

(D)

2

?2?6?

? ? ??最短路径为：C ?

? ? ?

?

? ?

? ? ?

1

f(C

)?min?d3(C2

,D)?f

1 4

(D)??min?3?4??7

???3 2 d(C,D

?

?

?

3 2 2

)?f

4

(D)

2

?2?6?

最短路径为：C

2

?D ?E

?

? ? ?

f(C

)?min?d3

(C,D

?3 1

?

)?f

4

(D)??min?4?4??8

?1?3 3 d

?

1

?

3

(C,D

3 2

)?f (D)

4 2

?5?6?

最短路径为：C

3

k?2时，

?D ?E

1

?d (B,C

? 2 1 1

)?f

3

(C)? ?1?8?

1 ? ? ?

f (B)?min?d (B,C )?f

(C )???3?7??9

2 1 ? 2( 1, 2)? 3

2 ? ?6?8?

?d B C f (C)? ? ?

2 1 3 3 3

最短路径为：B

1

?C ?D ?E

1 2

?d (B

? 2 2

,C)?f

1 3

(C)? ?4?8?

1 ? ? ?

f (B

2 2

)?min?d

?

(B,C

2 2

( ,

)?f (C

2 3 2

)?

)???2?7??9

? ?3?8?

?d B C f (C)? ? ?

2 2 3 3 3

最短路径为：B

2

?C ?D ?E

2 1

k?1时，

?d

(A,B)?f(B)? ?5?9?

?f(A)?min? 1

?

1 2 1

??min? ??12

?1 d(A,B

?

1 2

)?f

2

(B)

2

?3?9?

由A到E的最短距离为12，最短路径为：

A?B ?C

2 2

?D ?E。

1

将每段中各点至E的最短距离标在该点旁边，即可得图4－2。

B(9)

C(8)

D(4)

1

1

1

A(12)

C(7)

2

E(0)

B(9)

C(8)

D(6)

232图4－2各点至

2

3

2

下面对本例使用的动态规划解法进行简单的分析总

结。

与穷举法相比，动态规划方法有优点之一就是

大大减少了计算工作量。本例中用动态规划方法求解共用了14次相加计算、8次比较运算。事实上，问题规模越大，动态规划方法比穷举法节省的计算工作量越多。

用动态规划方法不仅求了全过程的最优方案，耐用得