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