下载文档原格式
动态规划入门1(2008-09-20 21:40:51)第一节动态规划基本概念一，动态规划三要素：阶段，状态，决策。
他们的概念到处都是，我就不多说了，我只说说我对他们的理解：如果把动态规划的求解过程看成一个工厂的生产线，阶段就是生产某个商品的不同的环节，状态就是工件当前的形态，决策就是对工件的操作。
显然不同阶段是对产品的一个前面各个状态的小结，有一个个的小结构成了最终的整个生产线。
每个状态间又有关联（下一个状态是由上一个状态做了某个决策后产生的）。
下面举个例子：要生产一批雪糕，在这个过程中要分好多环节：购买牛奶，对牛奶提纯处理，放入工厂加工，加工后的商品要包装，包装后就去销售……，这样没个环节就可以看做是一个阶段；产品在不同的时候有不同的状态，刚开始时只是白白的牛奶，进入生产后做成了各种造型，从冷冻库拿出来后就变成雪糕（由液态变成固态=_=||）。
每个形态就是一个状态，那从液态变成固态经过了冰冻这一操作，这个操作就是一个决策。
一个状态经过一个决策变成了另外一个状态，这个过程就是状态转移，用来描述状态转移的方程就是状态转移方程。
经过这个例子相信大家对动态规划有所了解了吧。
下面在说说我对动态规划的另外一个理解：用图论知识理解动态规划：把动态规划中的状态抽象成一个点，在有直接关联的状态间连一条有向边，状态转移的代价就是边上的权。
这样就形成了一个有向无环图AOE网（为什么无环呢？往下看）。
对这个图进行拓扑排序，删除一个边后同时出现入度为0的状态在同一阶段。
这样对图求最优路径就是动态规划问题的求解。
二，动态规划的适用范围动态规划用于解决多阶段决策最优化问题，但是不是所有的最优化问题都可以用动态规划解答呢？一般在题目中出现求最优解的问题就要考虑动态规划了，但是否可以用还要满足两个条件：最优子结构（最优化原理）无后效性最优化原理在下面的最短路径问题中有详细的解答；什么是无后效性呢？就是说在状态i求解时用到状态j而状态j就解有用到状态k…..状态N。
第1章 动态规划的基本概念和基本原理在这一章中，我们将通过一个具体而典型的例子（最短行军路线问题），引出有关动态规划的一些名词和记号，进而得到动态规划的基本原理。
1.1 最短行军路线问题及标号法问题描述：图1.1中给出一个行军路线网络，从A 点要走到G 点，中间要经过B 、C 、D 、……等很多点，各点间的距离如图中所示，今要求选择一条由A 点到G点的最短行军路线。
图 1.1这是个多阶段决策问题。
从A 点到G 点可以分为6个阶段，从A 点出发到B 点为第一阶段。
这时有两个选择：一是到B 1点；二是到B 2点。
若我们选择到B 2点的决策，则B 2点就是第一阶段决策的结果，它既是第一阶段的终点，又是下一阶段（第二阶段）路线的始点。
在第二阶段，再从B 2点出发，这时有三个选择，即对应于B 2点就有一个可供选择的终点集合{,,}。
若选择由B 2C 3C 4C 2走到C 2为第二阶段的决策，则C 2就是第二阶段的终点，同时又是第三阶段的始点。
类似地可以递推下去，直到终点G 点。
我们可以看到，各个阶段的决策不同，所走的路线也就不同。
现在要求：在各个阶段中选取一个恰当的决策，使由这些决策所决定的一条路线，其总距离最近。
下面我们利用“标号法”来求解这个问题。
首先要注意到下面一个明显面重要的事实：如果某一条路线，如是最优路线，那么无论从该路线中的哪一点开始（如从D G F E D C B A →→→→→→221211点开始）到达终点G 点的那一段路线，仍然是从D 1点到达终点G 的所有可能选择的不同的路线的最优路线，称为由D 1出发的最短子路线。
这一事实，以后我们称之为“最优化原理”。
因为如果不是这样，从D 1点到终点还有另一条更短的子路线存在，那么把它和原来最短路线由始点A 到达D 1点的那部分连接起来，就会形成一条比原来最短路线更短的路线，而这是不可能的。
根据上面的事实，我们可以从后段开始逐段往前求最优子路线，从而得到全过程最优路线。
教学基本文件模板课程教学大纲：《运筹学》课程教学大纲课程编号：课程名称：运筹学/Operational Research课程总学时/学分：72/4 （其中理论60学时，实验12学时）适用专业：适用本科四年制信息管理与信息系统专业一、课程简介本课程的授课对象是信息管理与信息系统专业本科生，属管理类专业专业基础必修课。
《运筹学》是以定量分析为主来研究经济管理问题，将工程思想和管理思想相结合，应用系统的、科学的、数学分析的方法，通过建模、检验和求解数学模型获得最优决策方案。
本课程的主要内容包括线性规划、运输问题、整数规划、目标规划、动态规划、网络分析等与经济、管理和工程领域密切相关的运筹学分支的基本模型、方法和应用。
运用科学的模型化方法来描述、求解和分析问题，从而支持决策。
二、教学目的和任务本课程旨在使同学们正确、全面地掌握各级管理工作中已被广泛应用、发展比较成熟的最优化理论与方法，并能运用所学理论和方法解决管理工作中出现的各种优化问题，为后续课程奠定定量分析基础。
在已学过高等数学、微积分、线性代数等课程基础上学习本课程，通过教授、自学、复习、作业练习、辅导、上机等教学环节达到上述目的。
学习中要注意到学科系统性，数学概念和逻辑的严密性、准确性和完整性，但不偏重纯数学方法论证。
注重基本概念、基本思路、基本方法、算法步骤的掌握，了解各种方法特点和实用价值，提高建立模型、分析求解能力和技巧。
应注重实际应用中建立模型，选择可行求解的理论方法，运用计算机工具求解这三方面训练的有机结合。
三、教学基本要求信息管理与信息系统专业的学生应系统地学习《运筹学》的全部内容。
系统掌握线性规划、运输问题、目标规划、整数规划、动态规划、图与网络分析的理论和方法；能借助Excel、Lingo等电子计算手段，运用所学理论和方法解决实际问题。
通过该课程的学习，进一步培养学生的分析问题和解决问题的能力。
四、教学内容与学时分配绪论（2学时）第一节运筹学的定义与发展简史1、运筹学名称的来历；2、运筹学的发展简史。
动态规划部分知识点总结动态规划的基本思想动态规划的基本思想可以用“递推”来描述。
在解决一个问题时，通常需要先确定一个递推关系，然后利用递推关系逐步求解问题的最优解。
以求解最长递增子序列（Longest Increasing Subsequence，LIS）问题为例，最长递增子序列是指在一个无序的序列中找到一个最长的子序列，要求子序列中的元素是递增的。
假设原序列为A，最长递增子序列的长度为LIS(i)，则可以通过递推关系来解决这个问题：LIS(i) = max(LIS(j)+1)，其中j<i 且A[j]<A[i]通过这个递推关系，我们可以逐步求解出从A[1]到A[n]的最长递增子序列的长度，最终得到整个序列的最长递增子序列。
动态规划的特点动态规划有一些特点，可以帮助我们更好地理解和应用这种方法。
1. 重叠子问题：动态规划的关键特点之一是重叠子问题，即原问题可以分解为若干个子问题，不同的子问题可能有重叠的部分。
通过记录和利用子问题的解，可以避免重复计算，提高计算效率。
2. 最优子结构：动态规划适用于具有最优子结构性质的问题。
最优子结构指的是原问题的最优解可以通过子问题的最优解来求解。
换句话说，原问题的最优解可以由子问题的最优解推导出来。
3. 状态转移方程：动态规划问题通常可以通过状态转移方程来描述。
状态转移方程是指原问题与子问题之间的关系，它可以用数学公式或递推关系来表示。
通过状态转移方程，可以确定问题的递推规律，从而求解问题的最优解。
动态规划的应用动态规划广泛应用于各种领域，比如算法设计、优化问题、数据挖掘等。
它可以解决许多经典问题，比如最短路径、背包问题、编辑距离、最长公共子序列等。
1. 最短路径：最短路径问题是指在一个加权有向图或加权无向图中，找到一条从起点到终点的路径，使得路径上的边权重之和最小。
动态规划可以用于求解最短路径问题，比如利用Floyd-Warshall算法或Dijkstra算法，通过记录并利用子问题的解来求解最短路径。
