动态规划算法在生活中的应用.docx

动态规划算法在生活中的应用 摘要：动态规划是运筹学的一个分支，它是解决多阶段决策过程最优化的一种数学方法。文中首先分别运用递归法和动态规划法对斐波拉契数列项进行求解，通过其不同的求解过程具体说明动态规划算法的原理以及建模过程，并突出用其求解具有重叠子问题的问题的优势。最终，文中通过用其对生活中的房屋物品购买以及旅行花费最少路径选择问题进行建模，完成相应的分析求解。 关键词：动态规划；运筹学；重叠子问题；问题建模 中图分类号：TP30 文献标识码：A 文章编号：1019-304417-0253-03 1引言 20世纪50年头初，美国数学家R.E.Bellman等人在优化多阶段决策过程的探讨中，提出了闻名的最优化原理。即把多阶段过程转化为一系列单阶段问题，并利用各阶段之间的关系，逐个求解，为解决这类过程优化问题创建了一种新的方法，即动态规划。运用动态规划中的最优化原则，可以将某一个活动过程划分为多个相互关联的阶段。基于前一阶段的决策结果，依次选择出各个不同阶段所处条件下可以选择的最优方案。通过这种方式，不仅可以确定当前状态到目标状态的最优值，而且还可以求出到中间状态的最优值，从而大大优化整个过程的经济效益。 由于用动态规划的思想解决问题，不仅可以令问题简化，而且可以避开计算的冗余。因此，动态规划问世后被广泛应用于生产调度，经济管理和优化限制等领域。 2动态规划算法介绍 两种解法的不同之处： 用递归法求解时会存在子过程重复求解状况，例如图1中因为求解fib须要运用到fib和fib的值，所以计算机会依次递归对fib和fib的值。虽然在求解fib时计算机已经递归求解出了fib的值，但是当求解fib的时候，计算机仍旧会对fib的值进行重复求解。这样就会大大增加计算时间。 而当采纳动态规划法求解问题时，因为该算法对各状态的数值有所保存，故每个数值计算一次即可，当下次计算须要运用到相应数值时，干脆采纳即可。这样就避开了数据的冗余计算，从而大大地削减了计算的时间。 2.1动态规划的思想 从上面的例子可以看出：动态规划的本质是分治思想和解决冗余。它是一种将问题实例分解成更小和相像的子问题，通过存储子问题的解来避开相同子问题的重复计算的算法策略。 动态规划算法的关键在于找到基本的递推关系式和恰当的边界条件，即状态转移方程或基本方程。上面的例子就是在已知关系式的状况下求解问题，所以要减省很多步骤。题中的fib公式就是相应的状态转移方程。 2.2建立动态规划模型的步骤 A.对决策过程划分阶段 划分阶段是利用动态规划解决多阶段决策问题的第一步。在确定了多阶段特征后，依据时间或空间的先后依次将该过程划分成若干相互关联的阶段。静态问题应当被人为地给予“时间”概念，以便于划分阶段。 B.对个阶段确定状态变量 选择的变量不仅要精确地描述过程地演化，还要满意无后效性，并且可以确定每个阶段状态变量地值。一般而言，我们是从过程演化的特点中找寻的状态变量。 C.确定决策变量及允许决策集合 通常选择所求问题的关键变量作为决策变量，同时要给出决策变量地取值范围，即确定允许决策集合。 D.建立个阶段状态变量的转移过程，确定状态转移方程 依据k阶段状态变量和决策变量，写出k+1阶段状态变量，状态转移方程应当具有地推关系。 E.確定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第k阶段的增益，最优指标函数是指从第k阶段状态到第n阶段结束时所获得收益的最优值。最终，写出动态规划的基本方程。 2.3动态规划的优点 能得到全局最优解 能提高算法效率。从上面例子可见，用递归法求解斐波那契数列时，算法的时间困难度为o2n，采纳动态规划法时其困难度为on，对比明显可见其效率的差异。 3动态规划在生活中的应用 3.1动态规划与日常购物 场景描述： 小明今日很快乐，因为在家买的新居子即将拿到钥匙。新居里面有一间他自己专用的、特别宽敞的房间。让他更兴奋的是，他的母亲昨天对他说：“你的房间须要购买什么物品？怎 么布置，你说了算，只要他们的价格总和不超过N元钱”。小明今日早上起先预算，但他想买太多的东西，确定会超过母亲的N元限额。因此，他把对每件物品的渴望程度，分为5等级：用整数1->5表示，第5等表示最想要。他还从互联网上找到了每件商品的价格。他希望在不超过N元的状况下，将每件商品的价格与效益度的乘积的总和最大化。 动态规划法 问题分析： 依据这个题目，我们须要在金额肯定的状况下求解舒适度最高的购物单，可见这是一个最优化问题。又因为小明在做出每一个选择都跟前面已经做出的选择有关，像这种子问题具有重叠性的最优化问题求解，动态规划占有很大的优势。 模型建立： 为了设计一个动态规划算法，我们须要推导出一个递推关系。下面，让我们来考虑一个由前i1iK个商品定义的实例。 设商品的价格依次为P1，P2，.Pi，商品对应的效益度分别为v1，v2，.vi，用户的预算为N元。式子dpiN表示：在前i个物品中选择购买物品，在不超过N元的前提下，使每件物品的价格与效益度的乘积的最大化的购物清单。 可以把在N元预算下，前i个物品的购买清单子集分成两个类别：包含第i个物品的子集和不包含第i个物品的子集。然后就有如下的结论： 依据定义，在不包含第i个物品的子集中，最优子集中每件物品的价格与效益度的乘积的总和为dpi-1，N； 在包含第i个物品的子集中因此，N-Pi0，最优子集是由该物品和前i-1个物品的购买清单的最优子集组成。这种最优子集中每件物品的价格与效益度的乘积的总和为pi×vi+dpi-1，N-pi； 因此，在前i个物品中最优子集的价格与效益度的乘积的总和等于这两个总和中的最大值。当然，假如当预算不足以购买第i个物品时，前i个物品中最优子集的价格与效益度的乘积的总和等于前i-1个物品中最优子集的价格与效益度的乘积的总和。这个结果导致了如下的递推式： 即所得购物单为：J1，J5，J6。 总结：当我们通过分析得到相应的动态规划状态方程时，用其求解问题的效率会优于一般的理论计算。 3.2动态规划与旅行路径选择 问题描述： 在一个风和日丽的假期，你和你的家人确定去度假放松一下心情，但是为了节约成本。你调查了你的城市到度假地点之间全部可能的线路以及每条线路上的花费。你想知道怎么选择一条详细的路途才能使你的城市到你的度假地点的总共的花费最少。 场景描述：已知从a地到e地有7条路径，其路径图如下图所示： 求解从a地到e地花费最小的路径。 问题分析： 首先，我先引入Floyed算法的相应的概念。Floyd 算法是一种经典的动态规划算法，它主要用于求解完全最短路径问题，即找到每个顶点到其他全部定点之间的距离。 其次，我们分析一下Floyed算法是否能用以求解此问题。分析如下：Floyed算法是已知两点之间的全部路径以及每条路径的长度，求取最短路径。而本题是已知两点之间的全部路径，以及每条路径的基础消费，求取消费最少的路径。可见，这里只是把“距离最短”换成了“消费最少”，其计算核心并没有变更。两者实属一种问题，我们可以暂且把“消费额”看成“距离值”，然后引用Floyed算法的相应思想，对问题进行求解。也就是说我们可以把求解的问题替代为求解最短路径的问题。两点之间最短路径问题分析思路如下： 从随意节点i到任何节点j的最短路径有两种可能性。一是干脆从i到j，二 是从i经过若干个中间节点k 然后到j。因此，我们假设Dis 是从节点u 到节点p 的最短路径的距离。对于每个节点k，我们检查推断Dis + Dis < Dis是否为真，如果条件为真，则表示从i到k再到j的路径比i直接到j的路径短，我们便设置Dis=Dis+Dis。如此反复进行判断，当我们遍历完所有节点k，Dis 记录的便是从i到j的最短路径的距离。 4结束语 从文中我们可以看出动态规划算法在解决多阶段最优决策问题上具有很大的优势，对比于递归算法，动态规划的算法效率更高。同时，我们可见该算法在我们生活中的实际案例的解决上发挥着强大的功能。但它也具有肯定的局限性，因为每个问题对应的模型不同，要找到其相应的状态转移方程并不是一件简单的事情。因此，如何有效地运用动态规划来解决问题还待做进一步的探究。 参考文献： 1罗伯特.E.拉森， 约翰.L.卡斯梯， 陈伟. 动态规划原理M. 清华高校出版社， 11014. 2拉森. 动态规划原理M. 清华高校出版社， 11014. 3闫萍， 王见勇. 斐波那契数列与黄金分割数J. 高等数学探讨， 2022， 8：28-29. 4朱振元， 朱承. 递归算法的非递归化实现J. 小型微型计算机系统， 2003， 24：567-573. 5郝自军， 何尚录. 最短路问题的Floyd算法的若干探讨J. 重庆理工高校学报， 2022， 22：156-159. 6叶奇明， 石世光. Floyd算法的演示模型探讨J. 海南高校学报， 2022， 26：47-50. 7曾方俊. Floyd算法求解最短路径的简明方法J. 价值工程， 2022， 31：167-168. 8谢剑辉， 郭嵩山. 国际高校生程序设计竞赛试题与分析动态规划及其应用杂题J. 现代计算机， 2000：92-101. 9任家时. 多阶段决策过程优化方法的数学证明J. 内蒙古民族高校学报， 11014：5-6. 10张玉斌. 迭代动态规划算法及并行化探讨D. 中国石油高校， 2022. 11万润泽， 朱彦松. 从动态规划算法的应用谈算法设计的教学J. 湖北其次师范学院学报， 2022：124-126. 12劳贵. 动态规划简介J. 数学的实践与相识， 11014：77-88. 13侯昶. 結构最优设计J. 数学的实践与相识， 11019：73-77. 第9页 共9页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页第 9 页 共 9 页