动态规划法
动态规划算法
矩阵连乘问题
[问题描述] 设有4个矩阵连乘积ABCD ，设它们的维数分别为A:45×8，B:8×40，C:40×
25，D:25×10，请求出它们的最优计算次序及对应的最少计算量。
算法分析：设A1=A, A2=B, A3=C, A4=D
p0=45,p1=8,p2=40,p3=25,p4=10 ,
用两个二维数组m 和s 记录中间结果，其中，m[i][j]记录矩阵连乘积A[i:j]的最少计算量，s[i][j]记录A[i:j]的最优断开位置。 由动态规划思想，得递归式为：
???
?
?<+++==-<≤j i p p p j k m k i m j i j i m j k i }],1[],[{min 0],[1j
k i 其中，k 的取值有j-i 种可能：i,i+1,...,j-1.
计算过程如下：
(1) m[i][i]=0, i=1,2,3,4 (2) 求m[i][i+1], i=1,2,3
m[1][2]= p0×p1×p2=45×8×40=14400 s[1][2]=1 m[2][3]= p1×p2×p3=8×40×25=8000 s[2][3]=2 m[3][4]= p2×p3×p4=40×25×10=10000 s[3][4]=3 (3) 求m[i][i+2], i=1,2
m[1][3]=min{m[1][1]+m[2][3]+p0×p1×p3, m[1][2]+m[3][3]+p0×p2×p3 } =min{8000+45×8×25,14400+45×40×25} =min{17000, 59400} =17000 s[1][3]=1
m[2][4]=min{m[2][2]+m[3][4]+p1×p2×p4, m[2][3]+m[4][4]+p1×p3×p4 } =min{10000+8×40×10,8000+8×25×10} =min{13200, 10000} =10000 s[2][4]=3
(4) 求m[i][i+3], i=1
m[1][4]=min{m[1][1]+m[2][4]+p0×p1×p4 , m[1][2]+m[3][4]+p0×p2×p4 , m[1][3]+m[4][4]+p0×p3×p4 }
=min{10000+45×8×10, 14400+10000+45×40×10, 17000+45×25×10 } =min{13600, 42400, 28250} =13600 s[1][4]=1
m[1][4]即A[1:4]的最少计算量，也即ABCD 连乘积的最少计算量为13600。 以上求出了最少计算量，下面由s 数组构造ABCD 的最优计算次序： s[1][4]=1, 则有(A(BCD))；
对于(BCD)，s[2][4]=3,有((BC)D)；对于(BC)，s[2][3]=2, 即最优计算次序为(A((BC)D))。
动态规划算法实验
一、实验目的 (2) 二、实验内容 (2) 三、实验步骤 (3) 四.程序调试及运行结果分析 (5) 附录：程序清单（程序过长，可附主要部分） (7)
实验四动态规划算法的应用 一、实验目的 1．掌握动态规划算法的基本思想，包括最优子结构性质和基于表格的最优值计算方法。 2．熟练掌握分阶段的和递推的最优子结构分析方法。 3．学会利用动态规划算法解决实际问题。 二、实验内容 1.问题描述： 题目一：数塔问题 给定一个数塔，其存储形式为如下所示的下三角矩阵。在此数塔中，从顶部出发，在每一节点可以选择向下走还是向右走，一直走到底层。请找出一条路径，使路径上的数值和最大。 输入样例（数塔）： 9 12 15 10 6 8 2 18 9 5 19 7 10 4 16 输出样例（最大路径和）： 59 题目二：最长单调递增子序列问题(课本184页例28) 设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、……、a(n)且a(i)<>a(j) (i<>j) 若存在i1 题目三 0-1背包问题 给定n种物品和一个背包。物品i的重量是wi，其价值为vi，背包的容量为c，。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大? 在选择装入背包的物品时，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量c，，物品的个数n。接下来的n 行表示n个物品的重量和价值。输出为最大的总价值。 输入样例： 20 3 11 9 9 10 7 5 输出样例 19 2.数据输入：个人设定，由键盘输入。 3.要求： 1）上述题目任选一做。上机前，完成程序代码的编写 2）独立完成实验及实验报告 三、实验步骤 1.理解算法思想和问题要求； 2.编程实现题目要求； 3.上机输入和调试自己所编的程序； 4.验证分析实验结果； 5.整理出实验报告。 第四章动态规划 §1 引言 1.1 动态规划的发展及研究内容 动态规划（dynamic programming）是运筹学的一个分支，是求解决策过程（decision process）最优化的数学方法。20 世纪50 年代初R. E. Bellman 等人在研究多阶段决策过程(multistep decision process)的优化问题时，提出了著名的最优性原理（principle of optimality），把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法—动态规划。1957 年出版了他的名著《Dynamic Programming》，这是该领域的第一本著作。 动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比用其它方法求解更为方便。 虽然动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），只要人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。 应指出，动态规划是求解某类问题的一种方法，是考察问题的一种途径，而不是一种特殊算法（如线性规划是一种算法）。因而，它不象线性规划那样有一个标准的数学表达式和明确定义的一组规则，而必须对具体问题进行具体分析处理。因此，在学习时，除了要对基本概念和方法正确理解外，应以丰富的想象力去建立模型，用创造性的技巧去求解。 例1 最短路线问题 图1 是一个线路网，连线上的数字表示两点之间的距离（或费用）。试寻求一条由A 到G距离最短（或费用最省）的路线。 图1 最短路线问题 例2 生产计划问题 工厂生产某种产品，每单位（千件）的成本为1（千元），每次开工的固定成本为3 （千元），工厂每季度的最大生产能力为6（千件）。经调查，市场对该产品的需求量第一、二、三、四季度分别为2，3，2，4（千件）。如果工厂在第一、二季度将全年的需求都生产出来，自然可以降低成本（少付固定成本费），但是对于第三、四季度才能上市的产品需付存储费，每季每千件的存储费为0.5（千元）。还规定年初和年末这种产品均无库存。试制定一个生产计划，即安排每个季度的产量，使一年的总费用（生产成本和存储费）最少。 1.2 决策过程的分类根据过程的时间变量是离散的还是连续的，分为离散时间 决策过程（discrete-time -56- 动态规划算法原理及其应用研究 系别：x x x 姓名：x x x 指导教员： x x x 2012年5月20日 摘要：动态规划是解决最优化问题的基本方法，本文介绍了动态规划的基本思想和基本步骤，并通过几个实例的分析，研究了利用动态规划设计算法的具体途径。关键词：动态规划多阶段决策 1.引言 规划问题的最终目的就是确定各决策变量的取值，以使目标函数达到极大或极小。在线性规划和非线性规划中，决策变量都是以集合的形式被一次性处理的；然而，有时我们也会面对决策变量需分期、分批处理的多阶段决策问题。所谓多阶段决策问题是指这样一类活动过程：它可以分解为若干个互相联系的阶段，在每一阶段分别对应着一组可供选取的决策集合；即构成过程的每个阶段都需要进行一次决策的决策问题。将各个阶段的决策综合起来构成一个决策序列，称为一个策略。显然，由于各个阶段选取的决策不同，对应整个过程可以有一系列不同的策略。当过程采取某个具体策略时，相应可以得到一个确定的效果，采取不同的策略，就会得到不同的效果。多阶段的决策问题，就是要在所有可能采取的策略中选取一个最优的策略，以便得到最佳的效果。动态规划是一种求解多阶段决策问题的系统技术，可以说它横跨整个规划领域（线性规划和非线性规划）。在多阶段决策问题中，有些问题对阶段的划分具有明显的时序性，动态规划的“动态”二字也由此而得名。动态规划的主要创始人是美国数学家贝尔曼（Bellman）。20世纪40年代末50年代初，当时在兰德公司（Rand Corporation）从事研究工作的贝尔曼首先提出了动态规划的概念。1957年贝尔曼发表了数篇研究论文，并出版了他的第一部著作《动态规划》。该著作成为了当时唯一的进一步研究和应用动态规划的理论源泉。在贝尔曼及其助手们致力于发展和推广这一技术的同时，其他一些学者也对动态规划的发展做出了重大的贡献，其中最值得一提的是爱尔思（Aris）和梅特顿（Mitten）。爱尔思先后于1961年和1964年出版了两部关于动态规划的著作，并于1964年同尼母霍思尔（Nemhauser）、威尔德（Wild）一道创建了处理分枝、循环性多阶段决策系统的一般性理论。梅特顿提出了许多对动态规划后来发展有着重要意义的基础性观点，并且对明晰动态规划路径的数 第四章 数学规划模型 【教学目的】：深刻理解线性规划，非线性规划，动态规划方法建模的基本特点，并能熟练建立一些实际问题的数学规划模型；熟练掌握用数学软件（Matlab ，Lindo ，Lingo 等）求解优化问题的方法。 【教学重点难点】： 教学重点：线性规划和非线性规划的基本概念和算法，解决数学规划问题的一般思路和 方法，线性规划模型、整数规划模型、非线性规划模型的构建及其Matlab 与Lingo 实现。 教学难点：区分线性规划模型和非线性模型适用的实际问题，以及何时采用线性模型， 何时采用非线性模型，线性模型与非线性模型的转化。 【课时安排】：10学时 【教学方法】：采用多媒体教学手段，配合实例教学法，通过对典型例题的讲解启发学生思维，并给与学生适当的课后思考讨论的时间，加深知识掌握的程度。安排一定课时的上机操作。 【教学内容】： 在众多实际问题中，常常要求决策（确定）一些可控制量的值，使得相关的量（目标）达到最佳（最大或最小）。这些问题就叫优化问题，通常需要建立规划模型进行求解。称这些可控制量为决策变量，相关的目标量为目标函数；一般情况下，决策变量x 的取值是受限制的，不妨记为x ∈Ω，Ω称为可行域，优化问题的数学模型可表示为 Max(或Min)f(x), x ∈Ω 一般情况下，x 是一个多元变量，f(x)为多元函数，可行域比较复杂，一般可用一组不等式组来表示，这样规划问题的一般形式为 () x Min f x . ()0,1,2,,i st g x i m ≤= 虽然，该问题属于多元函数极值问题，但变量个数和约束条件比较多，一般不能用微分法进行解决，而通过规划方法来求解；这里讨论的不是规划问题的具体算法，主要是讨论如何将一个实际问题建立优化模型，并利用优化软件包进行求解。 根据目标函数和约束函数是否为线性，将规划模型分为线性规划和非线性规划。 4.1线性规划 线性规划(LP)研究的实际问题多种多样的，它在工农业生产、经济管理、优化设计与控 8、《近期建设规划工作暂行办法》 2002年建设部制定了《近期建设规划工作暂行办法》和《城市规划强制性内容暂行规定》（建规[2002]218号），要求各地依据《办法》和《规定》，切实抓紧组织制定近期建设规划和明确城市规划强制性内容工作。 （1）近期建设规划的基本任务（第四条） （2）编制近期建设规划遵循原则（第五、六条） （3）近期建设规划的强制性内容（第七条） （4）近期建设规划的指导性内容（第八、九条） （5）近期建设规划的审批（第十条） 9、《城市规划强制性内容暂行规定》 （1）城市规划强制性内容的定义（第二条） （2）城市规划强制性内容的基本要求（第三、四条） （3）省域城镇体系规划的强制性内容（第五条） （4）城市总体规划的强制性内容（第六条） （5）城市详细规划的强制性内容（第七条） （6）有关规划强制性内容的调整（第九至十一条） 10、《城市紫线管理办法》 建设部制定的《城市紫线管理办法》，2003年11月15日建设部第22次常务会议审议通过，自2004年2月1日起施行。 （1）城市紫线定义 本办法所称城市紫线，是指国家历史文化名城内的历史文化街区和省、自治区、直辖市人民政府公布的历史文化街区的保护范围界线，以及历史文化街区外经县级以上人民政府公布保护的历史建筑的保护范围界线。本办法所称紫线管理是划定城市紫线和对城市紫线范围内的建设活动实施监督、管理。 （2）主管部门（第四条） （3）划定紫线应当遵循的原则（第六条） （4）城市紫线的调整与撤销（第八、十一条）。 （5）城市紫线范围内禁止进行下列活动（第十三条）。 （6）紫线范围内建设的要求（第十二、十四至十七条）。 11、《城市绿线管理办法》 建设部制定的《城市绿线管理办法》，2002年9月9日建设部第63次常务会议审议通过，随后发布， 动态规划是对最优化问题的一种新的算法设计方法。由于各种问题的性质不同，确定最优解的条件也互不相同，因而动态规划的没计法对不同的问题，有各具特色的表示方式。不存在一种万能的动态规划算法。但是可以通过对若干有代表性的问题的动态规划算法进行讨论，学会这一设计方法。 多阶段决策过程最优化问题 ——动态规划的基本模型 在现实生活中，有一类活动的过程，由于它的特殊性，可将过程分成若干个互相联系的阶段，在它的每一阶段都需要作出决策，从而使整个过程达到最好的活动效果。因此各个阶段决策的选取不能任意确定，它依赖于当前面临的状态，又影响以后的发展。当各个阶段决策确定后，就组成一个决策序列，因而也就确定了整个过程的一条活动路线。这种把一个问题看做是一个前后关联具有链状结构的多阶段过程就称为多阶段决策过程，这种问题称为多阶段决策最优化问题。 【例题1】最短路径问题。图中给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。现在，想从城市A到达城市E，怎样走路程最短，最短路程的长度是多少? 【分析】把从A到E的全过程分成四个阶段，用k表示阶段变量，第1阶段有一个初始状态A，两条可供选择的支路ABl、AB2；第2阶段有两个初始状态B1、 B2，B1有三条可供选择的支路，B2有两条可供选择的支路……。用dk(x k，x k+1)表示在第k阶段由初始状态x k到下阶段的初始状态x k+1的路径距离，Fk(x k)表示从第k阶段的x k到终点E的最短距离，利用倒推方法求解A到E的最短距离。具体计算过程如下： S1：K=4，有：F4(D1)=3，F4(D2)=4，F4(D3)=3 S2: K=3，有： F3(C1)=min{d3(C1,D1)+F4(D1),d3(C1,D2)+F4(d2)}=min{8,10}=8 F3(C2)=d3(C2,D1)+f4(D1)=5+3=8 F3(C3)=d3(C3,D3)+f4(D3)=8+3=11 F3(C4)=d3(C4,D3)+f4(D3)=3+3=6 解题思路 多代入法 二叉树 度 叶子结点就是没有孩子的结点，其度为0，度为二的结点是指有两个子数的结点。 注意树的度和图的度区别 叶子结点 二叉排序树 完全二叉树 若设二叉树的深度为h，除第h 层外，其它各层(1～h-1) 的结点数都达到最大个数，第h 层所有的结点都连续集中在最左边，这就是完全二叉树。 完全二叉树——只有最下面的两层结点度小于2，并且最下面一层的结点都集中在该层最左边的若干位置的二叉树； 最优二叉树（就是哈弗曼树） 平衡二叉树 平衡二叉树，又称AVL树。它或者是一棵空树，或者是具有下列性质的二叉树：它的左子树和右子树都是平衡二叉树，且左子树和右子树的高度之差之差的绝对值不超过1.。 满二叉树 满二叉树——除了叶结点外每一个结点都有左右子叶且叶结点都处在最底层的二叉树,。 除最后一层无任何子节点外，每一层上的所有结点都有两个子结点（最后一层上的无子结点的结点为叶子结点）。也可以这样理解，除叶子结点外的所有结点均有两个子结点。节点数达到最大值。所有叶子结点必须在同一层上. 本题主要考查一些特殊二叉树的性质。 若二叉树中最多只有最下面两层的结点度数可以小于2，并且最下面一层的叶子结点都依次排列在该层最左边的位置上，则这样的二叉树称为完全二叉树，因此在完全二叉树中，任意一个结点的左、右子树的高度之差的绝对值不超过1。 二叉排序树的递归定义如下：二叉排序树或者是一棵空树；或者是具有下列性质的二叉树： (1)若左子树不空，则左子树上所有结点的值均小于根结点的值； (2)若右子树不空，则右子树上所有结点的值均大于根结点的值； (3)左右子树也都是二叉排序树。 在n个结点的二叉树链式存储中存在n+1个空指针，造成了巨大的空间浪费，为了充分利用存储资源，可以将这些空链域存放指向结点在遍历过程中的直接前驱或直接后继的指针，这种空链域就称为线索，含有线索的二叉树就是线索二叉树。 最优二叉树即哈夫曼树。 题目：用动态规划法实现求两序列的最长公共子序列。 程序代码 #include 实验报告 （2009/2010学年第一学期） 课程名称算法分析与设计A 实验名称动态规划法 实验时间2009 年11 月20 日指导单位计算机学院软件工程系 指导教师张怡婷 学生姓名丁力琪班级学号B07030907 学院(系) 计算机学院专业软件工程 实验报告 实验名称动态规划法指导教师张怡婷实验类型验证实验学时2×2实验时间2009-11-20一、实验目的和任务 目的：加深对动态规划法的算法原理及实现过程的理解，学习用动态规划法解决实际应用中的最长公共子序列问题。 任务：用动态规划法实现求两序列的最长公共子序列，其比较结果可用于基因比较、文章比较等多个领域。 要求：掌握动态规划法的思想，及动态规划法在实际中的应用；分析最长公共子序列的问题特征，选择算法策略并设计具体算法，编程实现两输入序列的比较，并输出它们的最长公共子序列。 二、实验环境(实验设备) 硬件：计算机 软件：Visual C++ 三、实验原理及内容（包括操作过程、结果分析等） 1、最长公共子序列（LCS）问题是：给定两个字符序列X={x1,x2,……,x m}和Y={y1,y2,……,y n}，要求找出X和Y的一个最长公共子序列。 例如：X={a,b,c,b,d,a,b},Y={b,d,c,a,b,a}。它们的最长公共子序列LSC={b,c,d,a}。 通过“穷举法”列出所有X的所有子序列，检查其是否为Y的子序列并记录最长公共子序列并记录最长公共子序列的长度这种方法，求解时间为指数级别的，因此不可取。 2、分析LCS问题特征可知，如果Z={z1,z2,……，z k}为它们的最长公共子序列，则它们一定具有以下性质： （1）若x m=y n，则z k=x m=y n，且Z k-1是X m-1和Y n-1的最长公共子序列； （2）若x m≠y n且x m≠z k，则Z是X m-1和Y的最长公共子序列； （3）若x m≠y n且z k≠y n，则Z是X和Y的最长公共子序列。 这样就将求X和Y的最长公共子序列问题，分解为求解较小规模的问题： 若x m=y m，则进一步分解为求解两个（前缀）子字符序列X m-1和Y n-1的最长公共子序列问题； 如果x m≠y n，则原问题转化为求解两个子问题，即找出X m-1和Y的最长公共子序列与找出X 和Y n-1的最长公共子序列，取两者中较长者作为X和Y的最长公共子序列。 由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列，具有最优子结构性质。 3、令c[i][j]保存字符序列X i={x1,x2,……,x i}和Y j={y1,y2,……,y j}的最长公共子序列的长度，由上述分析可得如下递推式： 0 i=0或j=0 c[i][j]= c[i-1][j-1]+1 i,j>0且x i=y j max{c[i][j-1],c[i-1][j]} i,j>0且x i≠y j 由此可见，最长公共子序列的求解具有重叠子问题性质，如果采用递归算法实现，会得到一个指数时间算法，因此需要采用动态规划法自底向上求解，并保存子问题的解，这样可以避免重复计算子问题，在多项式时间内完成计算。 4、为了能由最优解值进一步得到最优解（即最长公共子序列），还需要一个二维数组s[][]，数组中的元素s[i][j]记录c[i][j]的值是由三个子问题c[i-1][j-1]+1,c[i][j-1]和c[i-1][j]中的哪一个计算得到，从而可以得到最优解的当前解分量（即最长公共子序列中的当前字符），最终构造出最长公共子序列自身。 第三章城乡规划法 大纲要求 3.《中华人民共和国城乡规划法》 3.1了解《中华人民共和国城乡规划法》立法背景 3.2熟悉《中华人民共和国城乡规划法》的重要意义与作用 3.3掌握《中华人民共和国城乡规划法》内容与说明 新版教材的变动 第三节《<城乡规划法>主要内容》中“城乡规划的实施原则”新增在城乡规划确定的建设用地以外不得作出规划许可的原则。“城乡规划实施管理制度”新增临时建设和临时用地规划管理。“规划修改的报审程序”新增城市、县、镇人民政府修改近期建设规划的情形。“城乡规划的法律责任”新增违反《城乡规划法》构成犯罪行为的处理办法。 授课时间 本章大约需要一讲的时间。 《中华人民共和国城乡规划法》是我国社会主义现代化建设新时期，适应新形势需要，为加强城乡规划管理，协调城乡空间布局，改善人居环境，涉及城乡建设和发展全局，促进城乡经济社会全面、协调、可持续发展而制定的一部基本法。该法经2007年10月28日第十届全国人民代表大会常务委员会第三十次会议通过并颁布，自2008年1月1日起施行。 一、立法指导思想、背景和重要意义 1、立法指导思想 制定《城乡规划法》的指导思想是：按照贯彻落实科学发展观和构建社会主义和谐社会的要求，统筹城乡建设和发展，确立科学的规划体系和严格的规划实施制度，正确处理近期建设与长远发展、局部利益与整体利益、经济发展与环境保护、现代化建设与历史文化保护等关系，促进合理布局，节约资源，保护环境，体现特色，充分发挥城乡规划在引导城镇化健康发展、促进城乡经济社会可持续发展中的统筹协调和综合调控作用。 2、立法背景 《城乡规划法》是由建设部起草的。它总结了1990年4月1日起施行的《城市规划法》和1993年11月1日起施行的《村庄和集镇规划建设管理条例》的实施经验，结合我国城镇化发展战略实行以来城市经 中华人民共和国城乡规划法解读对比旧版《城市规划法》～《城乡规划法》有哪些变化, 对比旧版《城市规划法》～最大的不同是强调城乡统筹～最显著的进展是强化监督职能～最明确的要求是落实政府责任。 《城乡规划法》共七章七十条～与《城市规划法》比较～取消 了“城市新区开发和旧区改造”这一章～新增加了“城乡规划的 修改”和“监督检查”两个章节。 中华人民共和国城乡规划法 ,2007年10月28日第十届全国人民代表大会常务委员会第三十次会议通过, 目录 第一章总则 第二章城乡规划的制定 第三章城乡规划的实施 第四章城乡规划的修改 第五章监督检查 第六章法律责任 第七章附则 第一章总则 《城乡规划法》的重要内容可概括为十个方面: 第一～突出城乡规划的公共政策属性。《城乡规划法》明确提 出:为了加强城乡规划管理～协调城乡空间布局～改善人居环境～ 促进城乡经济社会全面、协调、可持续发展～制定本法。从内容上看～重视资源节约、环境保护、文化与自然遗产保护,促进公共财政首先投到基础设施、公共 设施项目,强调城乡规划制定、实施全过程的公众参与,保证公平～明确了有关赔偿或补偿责任。第二～强调城乡规划综合调控的地位和作用。《城乡规划法》指出:“任何单位和个人都应当遵守依法批准并公布的城乡规划～服从规划管理”。这就从法律上明确～城乡规划是政府引导和调控城乡建设和发展的一项重要公共政策～是具有法定地位的发展蓝图。同时～法律适用范围扩大～强调城乡统筹、区域统筹,确立先规划后建设的原则,“三规合一”是规划未来发展的必然趋势。第三～新的城乡规划体系的建立。体现了一级政府、一级规划、一级事权的规划编制要求,明确规划的强制性内容,突出近期建设规划的地位,强调规划编制责任。 第四～严格城乡规划修改程序。对城乡规划评估～修改省域城镇体系规划、城市体规划、镇总体规划～修改详细规划等～都做出了详细的规定。 第五～城乡规划行政许可制度的完善。建立完善了针对土地有偿使用制度和投资体制改革的建设用地规划管理制度,规定了各项城乡规划的行政许可。 第六～对行政权力的监督制约。明确了上级行政部门的监督～人民代表大会的监督～以及全社会的公众监督。 第七～对城乡规划编制单位提出了新的要求。对城乡规划编制单 位的资质管理～对规划师职业的管理～都有明确规定。第八～加强人民代表大会的监督作用。省域城镇体系规划、城市和县城关镇总体规划由本级人大常委会审议～镇总体规划由人大审议。城市控制性详细规划报本级人大常委会备案～县城关镇控制性详细规划报县人大常委会备案。省域城镇体系规划、城市和镇总体规划定期评估须向人大报告。 第九～强化法律责任。追究政府和行政人员的责任,追究城乡规划编制单位的责任,追究违法建设行为的责任,明确对违法行为给予罚款的范围和数额,授予市政府强制拆除权。 第十～法律授权～建立完善的城乡规划法律体系。 动态规划算法 1. 动态规划算法介绍 基本思想是将待求解问题分解成若干子问题，先求解子问题，最后用这些子问题带到原问题，与分治算法的不同是，经分解得到的子问题往往是不是相互独立，若用分治则子问题太多。 2. 适用动态规划算法问题的特征 （1）最优子结构 设计动态规划算法的第一步骤通常是要刻画最优解的结构。当问题的最优解包含了其子问题的最优解时，称该问题具有最优子结构性质。问题的最优子结构性质提供了该问题可用动态规划算法求解的重要线索。 在动态规划算法中，问题的最优子结构性质使我们能够以自底向下的方式递归地从子问题的最优解逐步构造出整个问题的最优解。同时，它也使我们能在相对小的子问题空间中考虑问题。 （2）重叠子问题 可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。在用递归算法自顶向下解此问题时，每次产生的子问题并不总是新问题，有些子问题被反复计算多次。动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只有简单地用常数时间查看一下结果。通常，不同的子问题个数随输入问题的大小呈多项式增长。因此，用动态规划算法通常只需要多项式时间，从而获得较高的解题效率。 （3）备忘录方法 动态规划算法的一个变形是备忘录方法。备忘录方法也是一个表格来保存已解决的子问题的答案，在下次需要解此子问题时，只要简单地查看该子问题的解答，而不必重新计算。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上递归的。因此，备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。 备忘录方法为每个子问题建立一个记录项，初始化时，该记录项存入一个特殊的值，表示该子问题尚未求解。在求解过程中，对每个待求的子问题，首先查看其相应的记录项。若记录项中存储的是初始化时存入的特殊值，则表示该子问题是第一次遇到，则此时计算出该子问题的解，并保存在其相应的记录项中。若记录项中存储的已不是初始化时存入的特殊值，则表示该子问题已被计算过，其相应的记录项中存储的是该子问题的解答。此时，只要从记录项中取出该子问题的解答即可。 3. 基本步骤 a 、找出最优解的性质，并刻画其结构特征。 b 、递归地定义最优值。 c 、以自底向上的方式计算出最优值。 d 、根据计算最优值时得到的信息构造一个最优解。（可省） 例1-1 [0/1背包问题] [问题描述] 用贪心算法不能保证求出最优解。在0/1背包问题中，需要对容量为c 的背包进行装载。从n 个物品中选取装入背包的物品，每件物品i 的重量为i w ，价 值为 i v 。对于可行的背包装载，背包中物品的总重量不能超过背包的容量，最佳 装载是指所装入的物品价值最高，即∑=n i i i x v 1 取得最大值。约束条件为 c x w n i i i ≤∑=1 ， {}() n i x i ≤≤∈11,0。 实验3动态规划上机 [实验目的] 1．掌握动态规划的基本思想和效率分析方法； 2．掌握使用动态规划算法的基本步骤； 3．学会利用动态规划解决实际问题。 [实验要求] 按以下实验内容完成题目，并把编译、运行过程中出现的问题以及解决方法填入实验报告中，按时上交。 [实验学时] 2学时。 [实验内容] 一、实验内容 利用动态规划算法编程求解多段图问题，要求读入多段图，考虑多段图的排序方式，求源点到汇点的最小成本路径。并请对自己的程序进行复杂性分析。 二、算法描述 先输入点的个数和路径数以及每段路径的起点、长度、终点，再计算所有路径的值大小，比较输出后最小值。 三、源程序 #define N 2147483647 #include } array2[pointnum]=N; array3[pointnum]=N; for(i=0;i 湖州师范学院实验报告 课程名称：算法 实验二：动态规划方法及其应用 一、实验目的 1、掌握动态规划方法的基本思想和算法设计的基本步骤。 2、应用动态规划方法解决实际问题。 二、实验内容 1、问题描述 1 ）背包问题 给定 N 种物品和一个背包。物品 i 的重量是 C i ，价值为 W i ；背包的容量为 V。问应如何选择装入背包中的物品，使得装入背包中物品的总价值最大？在选择装入背包的物品，对每种物品只有两个选择：装入或不装入，且不能重复装入。输入数据的第一行分别为：背包的容量 V，物品的个数 N。接下来的 N 行表示 N 个物品的重量和价值。输出为最大的总价值。 2）矩阵连乘问题 给定 n 个矩阵：A1,A2,...,An，其中 Ai 与 Ai+1 是可乘的，i=1 ， 2... ， n-1。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。 3 ）LCS问题 给定两个序列，求最长的公共子序列及其长度。输出为最长公共子序列及其长度。 2、数据输入：文件输入或键盘输入。 3、要求： 1）完成上述两个问题，时间为 2 次课。 2）独立完成实验及实验报告。 三、实验步骤 1、理解方法思想和问题要求。 2、采用编程语言实现题目要求。 3、上机输入和调试自己所写的程序。 4、附程序主要代码： (1) #include 算法第4-7章部分答案 第四章 第4题： 想法： 求两个正整数m和n的最小公倍数，由题目给出的提示可以知道，m和n的最小公倍数等于两个数的积除以它们的最大公约数。在第一张的事后要我们就已经用欧几里德算法求过两个数的最大公约数，所以对于题目4，我们就可以直接引用欧几里德算法辅助求最小公倍数。 算法： 输入：两个自然数m和n 输出：m和n的最小公倍数 1.r=m%n; 1.循环直到r=0 1.1m=n; 1.2n=r; 1.3r=m%n; 2.return n 3.调用2输出(m*n)/n 程序： #include { m = n; n = r; r = m % n; } return n; } 第6题： 想法： 首先要建立一个大根堆，然后实现删除操作，关键是如何实现删除操作，我的想法是将要删除的元素和建立的大根堆的最后一个元素交换，然后再调用建立大根堆的函数将前n-1个函数进行大根堆操作 算法： 输入：要删除的元素的下标 输出：删除后排序好的大根堆 1.构造一个大根堆堆顺序函数SiftHeap（） 2.构造一个大根堆函数初始建堆函数HeapSort（），调用函数SiftHeap（） 3.建立初始大根堆 4.输入要删除的元素的下标 5.将要删除的元素与最后一个一个元素交换 6.建立前n-1个元素的大根堆 程序： //想法：先将已知序列排列成一个大根堆，删除某个元素后，将最后一个元素赋值给删除节点，然后再进行堆排序（堆排序只是有序排序中的一部分） #include 第四章《城乡规划法》配套行政法规与规章 大纲要求 4.《中华人民共和国城乡规划法》配套法规 4.1熟悉城乡规划编制与审批现行法规的适用条件 4.2掌握城乡规划编制与审批现行法规的主要内容 4.3熟悉城乡规划实施与监督检查现行法规的适用条件 4.4掌握城乡规划实施与监督检查现行法规的主要内容 新版教材的变动 《村庄和集镇规划建设管理条例》增添了《城乡规划法》对本条例的调整。《历史文化名城名镇名村保护条例》中增加了申报批准、保护措施、法律责任方面的内容。新增《风景名胜区条例》、《省域城镇体系规划编制审批办法》、《城市、镇控制性详细规划编制审批办法》，删除《城镇体系规划编制办法》、《村镇规划编制办法》、《历史文化名城保护规划编制要求》。 授课时间 本章大约需要两讲半的时间。 《城乡规划法》配套行政法规与规章，是指为实施《城乡规划法》，由国务院制定的若干法规，以及由国务院城乡规划主管部门制定的一系列部门规章。这些法规和规章分别是对《城乡规划法》某一专项内容的延展和细化，与《城乡规划法》共同组合成一整套具有内在联系的法律规范体系。自《城乡规划法》2008年施行以来，我国城市规划的法制建设逐步健全与完善，相继颁布了若干与《城乡规划法》配套的行政法规与规章及规范性文件。期间对一些已有配套法规和规章还进行了修订。 一、行政法规 1、《村庄和集镇规划建设管理条例》 （1）立法背景及适用范围 为加强村庄、集镇的规划建设管理，改善村庄、集镇的生产、生活环境，促进农村经济和社会发展，1993年6月29日国务院以第116号令颁布了《村庄和集镇规划建设管理条例》，并于同年11月1日起施行。 《城乡规划法》将乡规划和村庄规划纳入了城乡规划的概念，并对其规划编制组织、编制内容、编制程序等作出了明确规定。由于法律的效力高于行政法规，所以《城乡规划法》的实施也使得《村庄和集镇 TSP问题算法实验报告 指导教师：季晓慧 姓名：辛瑞乾 学号： 提交日期： 2015年11月 目录 总述...................................................................... 动态规划法................................................................ 算法问题分析............................................................ 算法设计................................................................ 实现代码................................................................ 输入输出截图............................................................ OJ提交截图.............................................................. 算法优化分析............................................................ 回溯法.................................................................... 算法问题分析............................................................ 算法设计................................................................ 实现代码................................................................ 输入输出截图............................................................ OJ提交截图.............................................................. 算法优化分析............................................................ 分支限界法................................................................ 算法问题分析............................................................ 第九章规划分析 [本章提要]本章主要通过生产管理和经营决策中的最优配置问题，介绍Excel 2000的规划求解工具的应用。着重说明了规划求解工具的适应范围，求解步骤，结果分析以及限制条件的修改。 在生产管理和经营决策过程中，经常会遇到一些规划问题。例如生产的组织安排，产品的运输调度，作物的合理布局以及原料的恰当搭配等问题，其共同点就是如何合理地利用有限的人力、物力、财力等资源，得到最佳的经济效果，即达到产量最高、利润最大、成本最小、资源消耗最少等目标。这些问题中通常要涉及到众多的关联因素，复杂的数量关系，只凭经验进行简单估算显然是不行的。而线性规划、非线性规划和动态规划等方法正是研究和求解该类问题的有效数学方法。但是这些方法的求解大多十分繁琐复杂，常令人望而却步。而利用Excel 2000的规划求解工具，可以方便快捷地帮助我们得到各种规划问题的最佳解。 9.1 规划模型 规划问题可以涉及到众多的生产或经营领域的常见问题。例如生产的组织安排问题：如果要生产若干种不同的产品，每种产品需要在不同的设备上加工，每种产品在不同设备上需要加工的时间不同，每种产品所获得的利润也不同。要求在各种设备生产能力的限制下，如何安排生产可获得最大利润。又如运输的调度问题：如果某种产品的产地和销地有若干个，从各产地到各销地的运费不同。要求在满足各销地的需要量的情况下，如何调度可使得运费最小。再如作物的合理布局问题：不同的作物在不同性质的土壤上单位面积的产量是不同的。要求在现有种植面积和完成种植计划的前提下，如何因地制宜使得总产值最高。还有原料的恰当搭配问题：在食品、化工、冶金等企业，经常需要使用多种原料配置包含一定成份的产品，不同原料的价格不同，所含成份也不同。要求在满足产品成份要求的情况下，如何配方可使产品成本最小。 虽然规划问题种类繁多，但是其所要解决的问题可以分成两类：一类是确定了某个任务，研究如何使用最少的人力、物力和财力去完成它；另一类是已经有了一定数量的人力、物力和财力，研究如何使它们获得最大的收益。而从数学角度来看，规划问题都有下述共同特征： 决策变量：每个规划问题都有一组需要求解的未知数（），称作决策变量。这组决策变量的一组确定值就代表一个具体的规划方案。 约束条件：对于规划问题的决策变量通常都有一定的限制条件，称作约束条件。约束条件可以用与决策变量有关的不等式或等式来表示。 目标：每个问题都有一个明确的目标，如利润最大或成本最小。目标通常可用与决策变量有关的函数表示。 如果约束条件和目标函数都是线性函数，则称作线性规划；否则为非线性规划。如果要求决策变量的值为整数，则称为整数规划。规划求解问题的首要问题是将实际问题数学化、模型化。即将实际问题通过一组决策变量、一组用不等式或等式表示的约束条件以及目标函数来表示。这是求解规划问题的关键。然后即可应用Excel 2000的规划求解工具求解。 例如，某企业要指定下一年度的生产计划。按照合同规定，该企业第一季度到第四季度需分别向客户供货80、60、60和90台。该企业的季度最大生产能力为130台，生产费用为 （元），这里的为季度生产的台数。该函数反映出生产规模越大，(数学建模教材)4第四章动态规划
动态规划算法原理与的应用
第四章 数学规划模型
第13讲 第四章《城乡规划法》配套行政法规与规章(五)及第五章城市规划技术标准与规范(一)(2011年新版)
经典算法——动态规划教程
第九章-数据结构与算法基础
算法分析与设计实验二：动态规划法
南京邮电大学算法设计实验报告——动态规划法
第7讲 城乡规划法(一)(2011年新版)
中华人民共和国城乡规划法 解读
动态规划算法举例分析
算法实验 动态规划上机
动态规划算法及其应用
算法设计第四章部分作业
第9讲 第四章《城乡规划法》配套行政法规与规章一
动态规划法回溯法分支限界法求解TSP问题实验报告
第九章 规划分析