5
常用算法与程序设计
3. 最优性原理
最优性原理：“作为整个过程的最优策略具有这样的 性质，无论过去的状态和决策如何,对前面的决策所形成 的状态而言,余下的诸决策必须构成最优策略”。 也就是说,最优决策序列中的任何子序列都是最优的。 最优性原理体现为问题的最优子结构特性。当一个问 题的最优解中包含了子问题的最优解时，则称该问题具 有最优子结构特性。 最优子结构特性是动态规划求解问题的必要条件。
cij ai1 b1 j ai 2 b2 j ain bnj a ik bkj k 1 cmp am1b1 p am 2 b2 p amn bnp a mk12 bkp 返回
Visual FoxPro
k 1 n k 1 n
k 1 n
常用算法与程序设计
3
常用算法与程序设计
2一般方法
多阶段决策问题 多阶段决策过程的每一阶段可能有多种可供 选择的决策，必须从中选择一种决策。各阶 段的决策构成一个决策序列。决策序列不同， 所导致的问题的结果可能不同。 多阶段决策的最优化问题就是：求能够获得 问题最优解的决策序列——最优决策序列。
4
常用算法 a11 b11 a12b21 a1n bn1 a1k bk 1
c1 j a11 b1 j a12b2 j a1n bnj a1k bkj
k 1 n
n
ci1 ai1 b11 ai 2 b21 ain bn1 a ik bk 1
给定n个矩阵{A0,A1,…,An－1}， 其中Ai
， i=0,…,n-1 的 维 数为 pipi+1 ，并且 Ai 与 Ai+1 是可乘的。考察这 n个矩阵的连 乘积 A0A1…An1 ，由于矩阵乘法满足
结合律，所以计算矩阵的连乘可有许
多不同的计算次序。
14
常用算法与程序设计
1. 问题描述
常用算法与程序设计
1
常用算法与程序设计
第 3 章 动态规划
教学要求
掌握最优性原理与动态规划设计的基本步骤 掌握应用动态规划设计求解0-1背包问题、三角
形划分、最长子序列与最优路径问题等多阶段决
策典型案例
本章重点
根据案例的实际构建状态转移方程 在案例求解基础上理解与掌握最优性原理
i 1,2, , m; j 1,2, , p.
运算过程演示
11
演示
a11 a a1n c11 c1 j c1 p 12 b b b 11 1 j 1 p b21 b2 j b2 p a c a c cij ip i1 i 2 ain i1 c b b c b c a a a nj np m1 mj mp m1 m 2 mn n1
矩阵连乘问题是确定计算矩阵连乘积

6
常用算法与程序设计
3.1.2 动态规划求解步骤
1. 利用动态规划求解问题的前提 1) 证明问题满足最优性原理 如果对所求解问题证明满足最优性原理，则说明 用动态规划方法有可能解决该问题 2) 获得问题状态的递推关系式 获得各阶段间的递推关系式是解决问题的关键
7
常用算法与程序设计
2.动态规划求解步骤
8
常用算法与程序设计
设计一个动态规划算法，通常可以按以下几个步 骤进行： （1）刻画最优解的结构特性； （2）递归定义最优解值； （3）以自底向上方式计算最优解值；
（4）根据计算得到的信息构造一个最优解。
其中，第（1）至（3）步是动态规划算法的基本
步骤。最优解值是最优解的目标函数的值。
9
常用算法与程序设计
2. 多阶段决策过程的求解策略
1）枚举法 穷举可能的决策序列，从中选取可以获得最优解的 决策序列 2）动态规划 20世纪50年代初美国数学家R.E.Bellman等人在研究 多阶段决策过程的优化问题时，提出了著名的最优化 原理(principle of optimality)，把多阶段过程转化为一系 列单阶段问题，创立了解决这类过程优化问题的新方 法——动态规划。
3.1 矩阵连乘问题
10
常用算法与程序设计
定义 设A=(aij)是m×n矩阵，B=(bij)是n×p矩 阵，则A与B的乘积AB是一个m×p矩阵，这个 矩阵的第i行第j 列位置上的元素cij等于A 的第i 行的元素与B的第j列的对应元素的乘积的和. 即
cij ai1b1 j ai 2b2 j ainbnj ,
2
常用算法与程序设计
3.1 一般方法与求解步骤
动态规划简介 动态规划是运筹学的一个分支，是求解决策过 程最优化的数学方法。 20世纪50年代美国数学家贝尔曼（R.Bellman） 等人在研究多阶段决策过程的优化问题时，提 出了著名的最优性原理，创立了解决多阶段过 程优化问题的新方法——动态规划。 动态规划问世以来，在经济管理、生产调度、 工程技术和最优控制等方面得到了广泛应用。
由矩阵的定义可以看出:
1. 两个矩阵的乘积AB亦是矩阵, AB的行数等
于矩阵A的行数, AB的列数等于矩阵B的列
数.
2. 前行乘后列: 乘积矩阵AB中第i行第j列的
元素等于A的第i行与B的第j列对应元素乘积 之和, 简称行乘列的法则。
3.矩阵相乘的数乘次数为：n*m*p
13
常用算法与程序设计
1. 问题描述
（1） 把所求最优化问题分成若干个阶段，找出最优


解的性质，并刻划其结构特性。 （2） 将问题发展到各个阶段时所处不同的状态表示 出来，确定各个阶段状态之间的递推关系，并确定初 始（边界）条件。 （3） 应用递推求解最优值。 （4） 根据计算最优值时所得到的信息，构造最优解。 构造最优解就是具体求出最优决策序列。通常在计 算最优值时，根据问题具体实际记录更多的信息，根 据所记录的信息构造出问题的最优解。