文档介绍：动态规划(Dynamic Programming)同前面介绍过的线性规划方法不同,它不是一种算法,而是考察问题的一种途径。动态规划是一种求解多阶段决策问题的系统技术。由于动态规划不是一种特定的算法,因而它不像线性规划那样有一个标准的数学表达式和明确定义的一组规则,动态规划必须对具体问题进行具体的分析处理。动态规划在工程技术、经济管理等各个领域都有着广泛的应用,并且获得了显著的效果。
最短路径问题贝尔曼最优化原理 WinQSB软件应用
第三章动态规划
动态规划是解决多阶段决策问题的一种方法. 1951年,美国数学家贝尔曼(,1920~1984)研究了一类多阶段决策问题的特征,提出了解决这类问题的基本原理。在研究、解决了某些实际问题的基础上,他于1957年出版了《动态规划》这一名著。本章将简要介绍动态规划的思想方法及其应用。
动态规划解决问题的基本思路是:把整体比较复杂的大问题划分成一系列较易于解决的小问题,通过逐个求解,最终取得整体最优解。这种“分而治之,逐步调整”的方法,在一些比较难以解决的复杂问题中已经显示出优越性。经过半个世纪的发展,动态规划解决问题的方法已经广泛应用于经济、管理、军事、生物、工程等诸多领域,并取得了很好效果。
所谓多阶段决策过程是指这样一类活动过程:一个决策过程可以分为若干个相互联系的阶段,每个阶段都需要作一定的决策,但是每个阶段最优决策的选择不能只是孤立地考虑本阶段所取得的效果如何,必须把整个过程中的各个阶段联系起来考虑,要求所选择的各个阶段决策的集合——策略,能使整个过程的总效果达到最优。
最短路径问题
最短路径问题
【】设在E城的某公司要从S城运送一批货物,两城之间有公路相连(见图3. 1(a)),其中是可以供选择的途经站点,各点连线上的数字表示相邻站点间的距离。现在的问题是选择一条由S到E的路径,使得所经过的路径最短。
最短路径问题
(a)
(b)
最短路径问题
分析:如果用枚举法,将有12条不同的路径,每条路径对应一个由到的路径距离,其中最小值所对应的路径即为最短路径。本问题的最短路径有3条,路程均为21个单位:
第1条:
第2条:
第3条:
最短路径问题
当段数很多时,枚举法的计算量将极其庞大。
现在换个思路,寻找由S到E的最短路径。先把最短路径问题所考虑的过程分为4个阶段:
由S到为第1阶段;
由到为第2阶段;
由到E为第4阶段。
由到为第3阶段;