动态规划课件

第二讲第二讲 动态规划动态规划讲授：白丹宇1本章内容多阶段决策过程的最优化多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划模型的建立与求解动态规划模型的建立与求解2美国数学家贝尔曼美国数学家贝尔曼(Richard.Bellman)创始时间创始时间上个世纪上个世纪50年代年代创始人创始人3是运筹学的一个主要分支是运筹学的一个主要分支是解决是解决多阶段决策过程多阶段决策过程的最优化的一种方法多的最优化的一种方法多阶段决策过程：阶段决策过程：资源分配问题资源分配问题生产计划与库存问题生产计划与库存问题投资问题投资问题装载问题装载问题排序问题排序问题生产过程的最优控制等生产过程的最优控制等多阶段决策过程的多阶段决策过程的最优化的目标最优化的目标：达到整个活动过程的总体效果最优达到整个活动过程的总体效果最优主要用于解决：主要用于解决：最优路径问题最优路径问题4动态规划动态规划模型分类模型分类离散确定型离散确定型离散随机型离散随机型连续确定型连续确定型连续随机型连续随机型5多阶段决策问题(Multi-Stage decision process)状态 x1阶段1T1决策u1状态 x2决策u2阶段2T2状态 x3.状态 xk决策uk阶段kTk状态 xk+1.状态 xn决策un阶段nTn状态 xn+11 1多阶段决策过程的最优化多阶段决策过程的最优化61.多阶段决策过程的最优化 动动态态规规划划方方法法与与“时时间间”关关系系很很密密切切，随随着着时时间间过过程程的的发发展展而而决决定定各各时时段段的的决决策策，产产生生一一个个决决策策序序列列，这这就就是是“动动态态”的的意意思思。然然而而它它也也可可以以处处理理与与时时间间无无关关的的静静态态问问题题，只只要要在在问问题题中中人人为为地地引引入入“时时段段”因因素素，就就可可以以将将其其转转化化为为一一个个多多阶阶段段决决策策问问题题。在在本本章章中中将将介介绍绍这这种种处处理理方方法。法。1 1多阶段决策过程的最优化多阶段决策过程的最优化72.多阶段决策问题举例多阶段决策问题举例 属于多阶段决策类的问题很多，例如属于多阶段决策类的问题很多，例如 1)1)工厂生产过程工厂生产过程：由于市场需求是一随着：由于市场需求是一随着时间而变化的因素，因此，为了取得全年时间而变化的因素，因此，为了取得全年最佳经济效益，就要在全年的生产过程中，最佳经济效益，就要在全年的生产过程中，逐月或者逐季度地根据库存和需求情况决逐月或者逐季度地根据库存和需求情况决定生产计划安排。定生产计划安排。1 1多阶段决策过程的最优化多阶段决策过程的最优化8例例1：某厂与用户签订了如表所示的交货合同，：某厂与用户签订了如表所示的交货合同，表中数字为月底的交货量。该厂的生产能力为每表中数字为月底的交货量。该厂的生产能力为每月月400件，该厂仓库的存货能力为件，该厂仓库的存货能力为300件。已知件。已知每百件货物的生产费用为每百件货物的生产费用为10000元。在进行生产元。在进行生产的月份，工厂还要支付经常费的月份，工厂还要支付经常费4000元。仓库保元。仓库保管费为每百件货物每月管费为每百件货物每月1000元。假设开始时及元。假设开始时及6月底交货后无存货。月底交货后无存货。月份123456交货量（百件）1253211 1多阶段决策过程的最优化多阶段决策过程的最优化92)2)设设备备更更新新问问题题：一一般般企企业业用用于于生生产产活活动动的的设设备备，刚刚买买来来时时故故障障少少，经经济济效效益益高高，即即使使进进行行转转让让，处处理理价价值值也也高高，随随着着使使用用年年限限的的增增加加，就就会会逐逐渐渐变变为为故故障障多多，维维修修费费用用增增加加，可可正正常常使使用用的的工工时时减减少少，加加工工质质量量下下降降，经经济济效效益益差差，并并且且，使使用用的的年年限限越越长长、处处理理价价值值也也越越低低，自自然然，如如果果卖卖去去旧旧的的买买新新的的，还还需需要要付付出出更更新新费费因因此此就就需需要要综综合合权权衡衡决决定定设设备备的使用年限，使总的经济效益最好。的使用年限，使总的经济效益最好。例例2 2：下下表表给给出出了了某某单单位位的的预预测测数数据据，现现决决定定考考虑虑到到19981998年（年（n=5n=5），试作），试作5 5年内的设备更新计划年内的设备更新计划1 1多阶段决策过程的最优化多阶段决策过程的最优化10产品年代机龄收入额维护费新设备购置费旧设备折价199312345181616141488991050201510521994012342221201816668810503025201510199501232725242256895231262115199601229262455652332820199701302845553530199803246040113)3)连连续续生生产产过过程程的的控控制制问问题题：一一般般化化工工生生产产过过程程中中，常常包包含含一一系系列列完完成成生生产产过过程程的的设设备备，前前一一工工序序设设备备的的输输出出则则是是后后一一工工序序设设备备的的输输入入，因因此此，应应该该如如何何根根据据各各工工序序的的运运行行工工况况，控控制制生生产产过过程程中中各各设设备备的的输输入入和和输输出出，以以使使总产量最大。总产量最大。1 1多阶段决策过程的最优化多阶段决策过程的最优化12 以以上上所所举举问问题题的的发发展展过过程程都都与与时时间间因因素素有有关关，因因此此在在这这类类多多阶阶段段决决策策问问题题中中，阶阶段段的的划划分分常常取取时时间间区区段段来来表表示示，并并且且各各个个阶阶段段上上的的决决策策往往往往也也与与时时间间因因素素有有关关，这这就就使使它它具具有有了了“动动态态”的的含含义义，所所以以把把处处理理这这类类动动态态问问题题的的方方法法称称为为动动态态规规划方法。划方法。不不过过，实实际际中中尚尚有有许许多多不不包包含含时时间间因因素素的的一一类类“静静态态”决决策策问问题题，就就其其本本质质而而言言是是一一次次决决策策问问题题，是是非非动动态态决决策策问问题题，但但是是也也可可以以人人为为地地引引入入阶阶段段的的概概念念当当作作多多阶阶段段决决策策问问题题，应应用用动动态态规规划方法加以解决。划方法加以解决。1 1多阶段决策过程的最优化多阶段决策过程的最优化13 4 4）资资源源分分配配问问题题：便属于这类静态问题。如：某工业部门或公司，拟对其所属企业进行稀缺资源分配，为此需要制定出收益最大的资源分配方案。这种问题原本要求一次确定出对各企业的资源分配量，它与时间因素无关，不属动态决策，但是，我们可以人为地规定一个资源分配的阶段和顺序，从而使其变成一个多阶段决策问题(后面我们将详细讨论这个问题后面我们将详细讨论这个问题)。1 1多阶段决策过程的最优化多阶段决策过程的最优化14例3：某工厂生产A、B、C三种产品，都使用某种原材料，现有原材料4吨。将不同数量的这种原料分配给各种产品时产生的收益如表所示，试确定使总收益最大的分配法。ABC0123010172006171808111115 5 5）运运输输网网络络问问题题：如如图图7-17-1所所示示的的运运输输网网络络，点点间间连连线线上上的的数数字字表表示示两两地地距距离离(也也可可是是运运费、时间等费、时间等)，要求从，要求从A A至至F F的最短路线。的最短路线。这这种种运运输输网网络络问问题题也也是是静静态态决决策策问问题题。但但是是，按按照照网网络络中中点点的的分分布布，可可以以把把它它分分为为5 5个阶段，而作为多阶段决策问题来研究。个阶段，而作为多阶段决策问题来研究。1 1多阶段决策过程的最优化多阶段决策过程的最优化161 1多阶段决策过程的最优化多阶段决策过程的最优化17本章内容多阶段决策过程的最优化多阶段决策过程的最优化动态规划的基本概念和基本原理动态规划的基本概念和基本原理动态规划模型的建立与求解动态规划模型的建立与求解181、阶段：、阶段：p把一个问题的过程，恰当地分为若干个相互联系的把一个问题的过程，恰当地分为若干个相互联系的阶段阶段，以便于按，以便于按一定的次序去求解。一定的次序去求解。p描述阶段的变量称为描述阶段的变量称为阶段变量阶段变量。阶段的划分，一般是根据时间和空。阶段的划分，一般是根据时间和空间的自然特征来进行的，但要便于问题转化为多阶段决策。间的自然特征来进行的，但要便于问题转化为多阶段决策。2、状态：、状态：表示每个阶段开始所处的表示每个阶段开始所处的自然状况或客观条件自然状况或客观条件。通常一个阶段有若。通常一个阶段有若干个状态，描述过程状态的变量称为干个状态，描述过程状态的变量称为状态变量状态变量。年、年、月、月、路段路段一个数、一个数、一组数、一组数、一个向量一个向量 状态变量的取值有一定的允许集合或范围，此集合称为状态变量的取值有一定的允许集合或范围，此集合称为状态允许集合状态允许集合。5.2 动态规划的基本概念193、决策：、决策：表示当过程处于某一阶段的某个状态时，可以作出不同的决定，表示当过程处于某一阶段的某个状态时，可以作出不同的决定，从而确定下一阶段的状态从而确定下一阶段的状态，这种决定称为这种决定称为决策决策。描述决策的变量，称为描述决策的变量，称为决策变量决策变量。决策变量是状态变量的函数。可。决策变量是状态变量的函数。可用一个数、一组数或一向量（多维情形）来描述。用一个数、一组数或一向量（多维情形）来描述。在实际问题中决策变量的取值往往在某一范围之内，此范围称为在实际问题中决策变量的取值往往在某一范围之内，此范围称为允允许决策集合许决策集合。系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，系统在某一阶段的状态转移不但与系统的当前的状态和决策有关，而且还与系统过去的历史状态和决策有关。而且还与系统过去的历史状态和决策有关。4、多阶段决策过程、多阶段决策过程可以在各个阶段进行决策，去控制过程发展的多段过程；可以在各个阶段进行决策，去控制过程发展的多段过程；其发展是通过一系列的状态转移来实现的；其发展是通过一系列的状态转移来实现的；20图示如下：图示如下：状态转移方程是确定过程由一状态转移方程是确定过程由一个状态到另一个状态的演变过个状态到另一个状态的演变过程。如果第程。如果第k阶段状态变量阶段状态变量sk的值、该阶段的决策变量一经的值、该阶段的决策变量一经确定，第确定，第k+1阶段状态变量阶段状态变量sk+1的值也就确定。的值也就确定。其状态转移方程如下（一般形式）其状态转移方程如下（一般形式）12ks1u1s2u2s3skuksk+1能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，能用动态规划方法求解的多阶段决策过程是一类特殊的多阶段决策过程，即即具有无后效性具有无后效性的多阶段决策过程。的多阶段决策过程。21动态规划中能动态规划中能处理的状态转移处理的状态转移方程的形式方程的形式。状态具有无后效性的多阶段决策过程的状态转移方程如下状态具有无后效性的多阶段决策过程的状态转移方程如下无后效性无后效性(马尔可夫性马尔可夫性)如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个如果某阶段状态给定后，则在这个阶段以后过程的发展不受这个阶段以前各段状态的影响；阶段以前各段状态的影响；过程的过去历史只能通过当前的状态去影响它未来的发展；构造过程的过去历史只能通过当前的状态去影响它未来的发展；构造动态规划模型时，要充分注意是否满足无后效性的要求；动态规划模型时，要充分注意是否满足无后效性的要求；状态变量要满足无后效性的要求；状态变量要满足无后效性的要求；如果状态变量不能满足无后效如果状态变量不能满足无后效性的要求，应适当地改变状态的定义或规定方法。性的要求，应适当地改变状态的定义或规定方法。22 5、策略：、策略：是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的是一个按顺序排列的决策组成的集合。在实际问题中，可供选择的策略有一定的范围，称为策略有一定的范围，称为允许策略集合允许策略集合。从允许策略集合中找出达。从允许策略集合中找出达到最优效果的策略称为到最优效果的策略称为最优策略最优策略。6、状态转移方程：、状态转移方程：是确定过程由一个状态到另一个状态的演变过程，描述了状态转是确定过程由一个状态到另一个状态的演变过程，描述了状态转移规律。移规律。7、指标函数和最优值函数：、指标函数和最优值函数：用来衡量所实现过程优劣的一种数量指标，为用来衡量所实现过程优劣的一种数量指标，为指标函数指标函数。指标函。指标函数的最优值，称为数的最优值，称为最优值函数最优值函数。在不同的问题中，指标函数的含。在不同的问题中，指标函数的含义是不同的，它可能是距离、利润、成本、产量或资源消耗等。义是不同的，它可能是距离、利润、成本、产量或资源消耗等。动态规划模型的指标函数应具有动态规划模型的指标函数应具有可分离性可分离性，并满足，并满足递推递推关系。关系。23指标函数指标函数:指标函数形式指标函数形式:和、和、积积可递推可递推 效益效益最优函数最优函数:24解多阶段决策过程问题，求出解多阶段决策过程问题，求出 最优策略最优策略，即最优，即最优决策序列决策序列f1(s1)最优轨线最优轨线，即执行最优策略时的即执行最优策略时的状态序列状态序列 最优目标函数值最优目标函数值从从 k 到终点最优策略到终点最优策略子策略的最优目标函数值子策略的最优目标函数值251、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的、动态规划方法的关键在于正确地写出基本的递推关系式和恰当的边界条件（简称基本方程）。边界条件（简称基本方程）。要做到这一点，就必须将问题的过程分成几个相互联系的阶要做到这一点，就必须将问题的过程分成几个相互联系的阶段，恰当的选取状态变量和决策变量及定义最优值函数，从段，恰当的选取状态变量和决策变量及定义最优值函数，从而把一个大问题转化成一组同类型的子问题，然后逐个求解。而把一个大问题转化成一组同类型的子问题，然后逐个求解。即从边界条件开始，逐段递推寻优，在每一个子问题的求解即从边界条件开始，逐段递推寻优，在每一个子问题的求解中，均利用了它前面的子问题的最优化结果，依次进行，最中，均利用了它前面的子问题的最优化结果，依次进行，最后一个子问题所得的最优解，就是整个问题的最优解。后一个子问题所得的最优解，就是整个问题的最优解。5.3 动态规划的基本思想262、在多阶段决策过程中，动态规划方法是既把当前一段和未来一、在多阶段决策过程中，动态规划方法是既把当前一段和未来一段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。段分开，又把当前效益和未来效益结合起来考虑的一种最优化方法。因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案因此，每段决策的选取是从全局来考虑的，与该段的最优选择答案一般是不同的一般是不同的.最优化原理：作为整个过程的最优策略具有这样的性质：无论过去最优化原理：作为整个过程的最优策略具有这样的性质：无论过去的状态和决策如何，相对于前面的决策所形成的状态而言，余下的的状态和决策如何，相对于前面的决策所形成的状态而言，余下的决策序列必然构成最优子策略。决策序列必然构成最优子策略。”也就是说，一个最优策略的子策也就是说，一个最优策略的子策略也是最优的。略也是最优的。3、在求整个问题的最优策略时，由于初始状态是已知的，而每段、在求整个问题的最优策略时，由于初始状态是已知的，而每段的决策都是该段状态的函数，故最优策略所经过的各段状态便可的决策都是该段状态的函数，故最优策略所经过的各段状态便可逐段变换得到，从而确定了最优路线。逐段变换得到，从而确定了最优路线。27建立动态规划模型的步骤建立动态规划模型的步骤 1、划分阶段、划分阶段划划分分阶阶段段是是运运用用动动态态规规划划求求解解多多阶阶段段决决策策问问题题的的第第一一步步，在在确确定定多多阶阶段段特特性性后后，按按时时间间或或空空间间先先后后顺顺序序，将将过过程程划划分分为为若若干干相相互互联联系系的的阶阶段段。对对于于静静态态问问题题要要人人为为地地赋赋予予“时时间间”概概念念，以便划分阶段。以便划分阶段。2、正确选择状态变量、正确选择状态变量选选择择变变量量既既要要能能确确切切描描述述过过程程演演变变又又要要满满足足无无后后效效性性，而而且且各各阶阶段段状状态态变变量量的的取取值值能能够够确确定定。一一般般地地，状状态态变变量量的的选选择择是是从从过程演变的特点中寻找。过程演变的特点中寻找。3、确定决策变量及允许决策集合、确定决策变量及允许决策集合通通常常选选择择所所求求解解问问题题的的关关键键变变量量作作为为决决策策变变量量，同同时时要要给给出出决决策变量的取值范围，即确定允许决策集合。策变量的取值范围，即确定允许决策集合。284、确定状态转移方程、确定状态转移方程根据根据k 阶段状态变量和决策变量，写出阶段状态变量和决策变量，写出k+1阶段状态变量阶段状态变量，状态状态转移方程应当具有递推关系。转移方程应当具有递推关系。5、确定阶段指标函数和最优指标函数，建立动态规划基本方程、确定阶段指标函数和最优指标函数，建立动态规划基本方程 阶段指标函数是指第阶段指标函数是指第k 阶段的收益，最优指标函数是指从第阶段的收益，最优指标函数是指从第k 阶段状态出发到第阶段状态出发到第n 阶段末所获得收益的最优值，最后写出动阶段末所获得收益的最优值，最后写出动态规划基本方程。态规划基本方程。以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线以上五步是建立动态规划数学模型的一般步骤。由于动态规划模型与线性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体性规划模型不同，动态规划模型没有统一的模式，建模时必须根据具体问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。问题具体分析，只有通过不断实践总结，才能较好掌握建模方法与技巧。292511214106104131112396581052C1C3D1AB1B3B2D2EC2一、最短路径问题求从A到E的最短路径302511214106104131112396581052C1C3D1AB1B3B2D2EC2f5(E)=0312511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D1)=5f5(E)=0322511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f4(D1)=5332511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C1)=8f4(D1)=5342511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C2)=7f4(D1)=5f3(C1)=8352511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f3(C1)=8f3(C2)=7362511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B1)=20f3(C2)=7f3(C1)=8372511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B2)=14f3(C2)=7f3(C1)=8f2(B1)=21382511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f2(B1)=21f2(B2)=14392511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21402511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2412511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1422511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1432511214106104131112396581052C1C3D1AB1B3B2D2EC2f4(D2)=2f5(E)=0f3(C3)=12f4(D1)=5f2(B3)=19f3(C2)=7f3(C1)=8f1(A)=19f2(B2)=14f2(B1)=21状态 最优决策 状态 最优决策 状态 最优决策 状态 最优决策 状态A （A，B2）B2 （B2，C1）C1 （C1，D1）D1 （D1，E）E从A到E的最短路径为19，路线为AB 2C1 D1 E 44课堂练习用动态规划方法求最短路45 先先从从F F开开始始，因因为为F F是是终终点点。再再无无后后继继过过程程，故故可可以以接接着着考考虑虑第第5 5阶阶段段上上所所有有可可能能状状态态E E1 1，E E2 2的的最最优优后后续续过过程程。因因为为从从E E1 1,E,E2 2到到F F的的路路线线是是唯唯一一的的，所所以以E E1 1，E E2 2的的最最优优决决策策和和最最优优后后继继过过程程就就是是到到F F，它它们们的的最最短短距离分别是距离分别是4 4和和3 3。接接着着考考虑虑阶阶段段4 4上上可可能能的的状状态态D D1 1，D D2 2，D D3 3 到到F F的的最最优优决决策策和和最最优优后后继继过过程程在在状状态态D D1 1上上，到到E E1 1是是3 3，到到E E2 2是是5 5，综综合合考考虑虑后后继继过过程程整整体体最最优优，取取最最优优决决策策是是到到E E1 1,最最优优后后继继过过程程是是D D1 1EE1 1FF ，最最短短距距离离是是7 7。同同理理，状状态态D D2 2的的最最优优决决策策是是至至E E2 2 ；D D3 3的的最最优优决决策是到策是到E E1 1。46 同同样样，当当阶阶段段4 4上上所所有有可可能能状状态态的的最最优优后后继继过过程程都都已已求求得得后后，便便可可以以开开始始考考虑虑阶阶段段3 3上上所所有有可可能能状状态态的的最最优优决决策策和和最最优优后后继继过过程程，如如 C C1 1的的 最最 优优 决决 策策 是是 到到D D1 1,最最 优优 路路 线线 是是C C1 1D D1 1E E1 1F F ，最最短短距距离离是是1212依依此此类类推推，最最后后可可以以得得到到从从初初始始状状态态A A的的最最优优决决策策是是到到F F最最优优路路线线是是A AB B1 1C C2 2D D2 2E E2 2 F F ，全全程程的的最最短短距距离离是是1717。图图7 71 1中中粗粗实实线线表表示示各各点点到到的的最最优优路路线线，每每点点上上方方括括号号内内的的数数字字表表示示该该点点到终点的最短路距离。到终点的最短路距离。4748495051 综综上上所所述述可可见见，全全枚枚举举法法虽虽可可找找出出最最优优方方案案，但但不不是是个个好好算算法法，局局部部最最优优法法则则完完全全是是个个错错误误方方法法，只只有有动动态态规规划划方方法法属属较较科科学学有有效效的的算算法法。它它的的基基本本思思想想是是，把把一一个个比比较较复复杂杂的的问问题题分分解解为为一一系系列列同同类类型型的的更更易易求求解解的的子子问问题题，便便于于应应用用计计算算机机。整整个个求求解解过过程程分分为为两两个个阶阶段段，先先按按整整体体最最优优的的思思想想逆逆序序地地求求出出各各个个子子问问题题中中所所有有可可能能状状态态的的最最优优决决策策与与最最优优路路线线值值，然然后后再再顺顺序序地地求求出出整整个个问问题题的的最最优优策策略略和和最最优优路路线线。计计算算过过程程中中，系系统统地地删删去去了了所所有有中中间间非非最最优优的的方方案组合，从而使计算工作量比穷举法大为减少。案组合，从而使计算工作量比穷举法大为减少。52作业：求作业：求A A到到E E的最短路径的最短路径AB1B2C1C2C3D1D2E100200352002407080706012015016015025022025053