下载文档原格式
多阶段决策过程(multistepdecisionpr （Shortest-paths ）7．1 问题描述在一个带权无向或者有向图中，如果从图中某顶点（称源点）到达另顶点（称为终点）路径可能不止一条，如何找到一条路径使得沿此路径上各边上权值总和达到最小。
实际应用中，有把交通运输网络作为一个图，图中顶点表示城市，图中各边表示城市之间交通运输线。
边上权值就根据具体需要，可以用各种代价表示，比如路程，运费，时间。
同时，可以用有向图表示往返代价不一致。
计算机网络中，把网络结构看成带权图，路由选择时候采用固定路由算法其中有使用最短路径算法。
此外，最短路径算法还应用于电子导航中，根据已知地理网络，得出合适航线；应用于电力、通讯等各种管网、管线布局设计，城市规划等等。
由于应用需要，最短路径算法问题成为计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究一个热点。
在最短路径问题中，给出是一个带权有向图G ＝(V , E)，加权函数w:E R 为从边到实型权值映射。
路径p=(v0,v1,v2,…,vk)权是指组成边所有权值之和：w(p)=∑w(vi-1,vi) i=1—k;定义从u 到v 间最短路径权为：()(){}⎩⎨⎧∞−→−=otherelse v u v u p w v u p :min ,存在一条通路到若从δ 从顶点u 到v 最短路径定义为权w(p)=&(u,v)任何路径.不带权图最短路径问题是一个特例，可将图视为没条边权值均为1带权图。
两种最常见最短路径问题：从某个源点到其余各顶点最短路径每对顶点间最短路径7．2 松弛技术Relaxation在后面介绍几个算法中都用到了松弛技术，现在就来看看松弛技术。
对于每个顶点v∈V，都设置一个属性d[v]，用来描述从源点s到v最短路径上权值上界，称为最短路径估计（shortest-path estimate）。
我们用下面Θ(V)时间过程来对最短路径估计和前趋进行初始化。
多阶段决策问题
应用条件应用条件
从起始点到终点最短距离
最优子结构性质：任何最短路径的子路径都是相对于子路径的始点和终点
的最短路径
子问题重叠性质：任何中间节点到终点的距离都被前面的节点多次使用基本思想步骤
常见的实现形式搜索，备忘录，递推
搜索，备忘录，递推搜索，备忘录，递推
搜索，备忘录，递推0-1背包问题（1）
0-1
最长子序列（
最长子序列（最长子序列（最长子序列（邮局问题（
邮局问题（
状态选择
状态选择时间与空间的权衡学习动态规划的方法。
动态规划多阶段决策过程（multistep decision process ）是指这样一类特殊的活动过程，过程可以按时间顺序分解成若干个相互联系的阶段，在每一个阶段都需要做出决策，全部过程的决策是一个决策序列。
动态规划（dynamic programming ）算法是解决多阶段决策过程最优化问题的一种常用方法，难度比较大，技巧性也很强。
利用动态规划算法，可以优雅而高效地解决很多贪婪算法或分治算法不能解决的问题。
动态规划算法的基本思想是：将待求解的问题分解成若干个相互联系的子问题，先求解子问题，然后从这些子问题的解得到原问题的解；对于重复出现的子问题，只在第一次遇到的时候对它进行求解，并把答案保存起来，让以后再次遇到时直接引用答案，不必重新求解。
动态规划算法将问题的解决方案视为一系列决策的结果，与贪婪算法不同的是，在贪婪算法中，每采用一次贪婪准则，便做出一个不可撤回的决策；而在动态规划算法中，还要考察每个最优决策序列中是否包含一个最优决策子序列，即问题是否具有最优子结构性质。
动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质：最优子结构性质和子问题重叠性质。
1 、最优子结构性质。
如果问题的最优解所包含的子问题的解也是最优的，我们就称该问题具有最优子结构性质（即满足最优化原理）。
最优子结构性质为动态规划算法解决问题提供了重要线索。
2 、子问题重叠性质。
子问题重叠性质是指在用递归算法自顶向下对问题进行求解时，每次产生的子问题并不总是新问题，有些子问题会被重复计算多次。
动态规划算法正是利用了这种子问题的重叠性质，对每一个子问题只计算一次，然后将其计算结果保存在一个表格中，当再次需要计算已经计算过的子问题时，只是在表格中简单地查看一下结果，从而获得较高的解题效率。
当我们已经确定待解决的问题需要用动态规划算法求解时，通常可以按照以下步骤设计动态规划算法：1 、分析问题的最优解，找出最优解的性质，并刻画其结构特征；2 、递归地定义最优值；3 、采用自底向上的方式计算问题的最优值；4 、根据计算最优值时得到的信息，构造最优解。
dpmsolvermultistepscheduler原理DPMSolverMultistepScheduler 是指动态规划（Dynamic Programming，DP）多步骤调度器，它是一种用于优化多步骤决策过程的算法。
其原理基于动态规划的思想，通过将问题分解为一系列相互关联的子问题，并按照时间顺序进行决策，以找到最优解。
DPMSolverMultistepScheduler 的工作原理可以概括如下：
1.将多步骤决策过程划分为若干个阶段（stage），每个阶段都包含一
系列决策。
2.为每个阶段定义状态（state）和状态转移方程（state transition
equation）。
状态表示在该阶段开始时系统的状态，状态转移方程描述了在该阶段内进行决策后系统状态的转移。
3.为每个阶段定义代价函数（cost function），它表示在该阶段执行
特定决策的代价。
4.使用动态规划算法，从最后一个阶段开始，反向求解每个阶段的
最优解，直到第一个阶段。
在每个阶段，根据状态转移方程和最优解，确定在该阶段的最优决策。
5.将所有阶段的最优解组合起来，得到整个多步骤决策过程的最优
解。
DPMSolverMultistepScheduler 的优点在于它能够考虑到整个多步骤决策过程的代价，而不是仅仅关注单个步骤的代价。
此外，它能够处理具有不确定性的多步骤决策过程，通过概率模型描述每个阶段的转
移概率和代价函数。
这种算法广泛应用于各种优化问题，如生产调度、路径规划、库存管理等。
多阶段确定型决策（动态规划）若整个确定型决策过程又分为几个阶段，而在每个阶段（通常以时间为标志）要根据过程的演变情况确定一个决策，使全过程的某个指标达到最优，此时的决策问题称为多阶段确定型决策。
多阶段确定型决策过程实际上是一个状态转移问题，如最短路问题、资源的最优分配问题、设备更新问题和生产计划与存贮问题等。
动态规划模型理论是解决此类问题的有力工具。
它的目的就是求一个策略，使得各阶段的效益总和达到最优。
是1951年，美国数学家R.. Bellman 等人提出并创建形成的。
动态规划方法的基本思想：将一个复杂系统分解成若干阶段，每一个阶段系统都有一个决策集合，从中选择一个决策，从而决定整个过程的策略。
阶段往往用时间划分，这就具有“动态”的含义，然而，一些与时间无关的静态规划中的优化决策，也可以人为地把问题分为若干阶段作为多阶段决策问题处理。
多阶段确定型决策问题主要包括两种情况：一是阶段数固定，一是阶段数不固定。
各有各的解法，我们下面只介绍第一种情况。
求解思想主要来源于图论中的最短路径问题的思想（见图论中最短路径）。
下面结合图论最短路径问题的求解过程介绍动态规划的基本概念和原理：例：图7-5是一个线路图，边上的权表示两点之间的运输费用，寻求一条从A 到G 的路线，使运费最省。
分析：由图可知任意一条从A 到G 的路线均由六条支路构成，所以此例的最优路线问题，可看作是能够分成若干阶段的一个过程。
在过程的每一个阶段都需要作出选择，决定究竟走哪一条支路。
这些决定不同，直接导致整个选择的路线不同，走的路线的距离也不同。
如何选择路线呢？动态规划最优化原理：美国数学家R.. Bellman 指出：“作为整个过程的最优策略具有这样的性质，即无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。
”其含义是：最优策略的任何状态后的部分策略，都是相应于以此时状态作为初始状态的最优策略。
简言之，每个最优策略只能是由最优子策略构成的。
多阶段决策和序贯决策教材引言多阶段决策和序贯决策是决策理论中重要的概念和方法。
在很多实际应用中，决策问题往往不仅仅是一次性的选择，而是需要在不同阶段进行多次决策，每次决策都受之前决策的影响。
本教材将介绍多阶段决策和序贯决策的基本概念和方法，并提供案例来帮助读者理解和应用这些概念和方法。
多阶段决策多阶段决策是指决策问题中包含多个决策节点的情况。
在每个决策节点，决策者需要面临不同的选择，并根据选择的结果进行下一阶段的决策。
多阶段决策常见于实际生活中的许多问题，比如投资决策、项目管理等。
多阶段决策可以通过决策树来表示。
决策树是一种树状结构，其中每个节点表示一个决策点，每个边表示一个选择。
通过自顶向下的递归过程，从根节点到叶子节点，决策树可以表示整个多阶段决策的过程。
在每个决策节点，决策者根据一定的决策准则选择一个最优的方案。
常用的决策准则包括最大化效益、最小化风险等。
序贯决策序贯决策是多阶段决策的一种特殊形式，它是指在每个决策节点上，决策者只能看到当前状态的信息，并且只做当前状态下最优的决策，无法事先知道所有后续状态的信息。
序贯决策常见于动态环境下的问题，比如控制系统、机器人等。
序贯决策可以通过动态规划来求解。
动态规划是一种递推的算法，通过将问题划分为一系列子问题，并利用子问题的最优解来推导出整个问题的最优解。
在序贯决策中，我们可以定义一个价值函数来表示当前状态的价值，然后利用动态规划算法不断更新和求解价值函数，最终得到最优的决策序列。
案例分析为了帮助读者理解和应用多阶段决策和序贯决策的概念和方法，下面将给出一个案例分析。
假设你是一家餐厅的经理，现在面临一个供应商选择的问题。
你可以选择三个不同的供应商，每个供应商的价格和质量都不同。
此外，每个供应商的产品质量在未来可能会有变化。
你需要决策在当前时间选取哪个供应商，并在之后的时间里根据每个供应商的质量变化重新评估和选择供应商。
这个问题可以通过多阶段决策和序贯决策的方法来解决。
多阶段决策过程
m u l t i s t e p d e c i s i o n p
r
Revised as of 23 November 2020
第七部分 最短路径
（Shortest-paths ）
7．1 问题描述
在一个带权的无向或者有向图中，如果从图中某顶点（称源点）到达另顶点（称为终点）的路径可能不止一条，如何找到一条路径使得沿此路径上各边上的权值总和达到最小。
实际应用中，有把交通运输网络作为一个图，图中顶点表示城市，图中各边表示城市之间的交通运输线。
边上的权值就根据具体需要，可以用各种代价表示，比如路程，运费，时间。
同时，可以用有向图表示往返代价的不一致。
计算机网络中，把网络结构看成带权图，路由选择的时候采用的固定路由算法其中有使用最短路径算法。
此外，最短路径算法还应用于电子导航中，根据已知地理网络，得出合适的航线；应用于电力、通讯等各种管网、管线的布局设计，城市规划等等。
由于应用的需要，最短路径算法问题成为计算机科学、运筹学、地理信息系统和交通诱导、导航系统等领域研究的一个热点。
在最短路径问题中，给出的是一个带权有向图G ＝(V , E )，加权函数w:ER 为从边到实型权值的映射。
路径p=(v0,v1,v2,…,vk)的权是指组成边的所有权值之和：
w(p)=∑w(vi-1,vi) i=1—k;
定义从u 到v 间的最短路径的权为：
()(){}⎩⎨⎧∞−→−=otherelse v u v u p w v u p
:min ,存在一条通路到若从δ 从顶点u 到v 的最短路径定义为权w(p)=&(u,v)的任何路径.
不带权图的最短路径问题是一个特例，可将图视为没条边的权值均为1的带权图。
两种最常见的最短路径问题：
● 从某个源点到其余各顶点的最短路径
● 每对顶点间的最短路径
7．2 松弛技术Relaxation
在后面介绍的几个算法中都用到了松弛技术，现在就来看看松弛技术。
对于每个顶点v∈V，都设置一个属性d[v]，用来描述从源点s到v的最短路径上权值的上界，称为最短路径估计（shortest-path estimate）。
我们用下面的Θ(V)时间的过程来对最短路径估计和前趋进行初始化。
INITIALIZE-SINGLE-SOURCE(G,s)
1 for each vertex v∈V[G]
2 do d[v]←∞
3 π[v]←NIL
4 d[s]←0
经过初始化以后，对所有v∈V，π[v]=NIL，对v∈V-{s}，有d[s]=0以及d[v]=∞。
在松弛一条边(u,v)的过程中，要测试是否可以通过u，对迄今找到的v的最短路径进行改进；如果可以改进的话，则更新d[v]和π[v]。
一次松弛操作
可以减小最短路径估计的值d[v]，并更新v的前趋域π[v]。
下面的伪代码对
边(u,v)进行了一步松弛操作。
RELAX(u, v, w)
1 if(d[v]>d[u]+w(u,v))
2 then d[v]←d[u]+w(u,v)
3 π[v]←u
在Bellman-Ford algorithm和Dijkstra’s algorithm都会调用到INITIALIZE-SINGLE-SOURCE(G,s)，然后重复对边进行松弛的过程。
另外松弛是改变最短路径和前趋的唯一方式，在两个算法之间的区别在于对每条边进行的松弛操作的次数，以及对边执行松弛操作的次序不同。
在Dijkstra’s algorithm以及关于有向无回路图的最短路径算法中，对每条边执行情况一次松弛操作。
而在Bellman-Ford算法中，对每条边要执行多次松弛操作。
7．3 Bellman-Ford algorithm
思想：运用松弛技术，对每一个结点v∈V，逐步减少从源s到v的最短路径
的权的估计值d[v]，直至其达到实际最短路径的权δ(s,v)。
算法返回布尔值TURE当且仅当图中没有源结点可达的负权回路。
优点：解决更一般情况的单源最短路径问题。
且边的权值可以为负，可检测出图中是否存在一个从源结点可达的负权回路，如果存在负权回路则无解；否则将产生最短路径及其权。
BELLMAN-FORD（G,w,s）
1 INITIALIZE-SINGLE-SOURCE(G,s)
2 for i1 to |V[G]|-1
3 do for each edge(u,v)∈E[G]
4 do RELAX(u,v,w)
5 for each edge(u,v) ∈E[G]
6 do if d[v]>d[u]+w(u,v)
7 then return false;
8 return true
引理 7.3.1 设为带权有向图，其源点为s，权函数为w：ER，并且假定G中不包含从s点可达的负权回路。
那么BELLMAN-FORD第2—4行循环的|V|-1次迭代后，对任何s可达的顶点v，有d[v]=∮(s,v)。
推论：设G=（V，E）为带权有向图，源顶点为s，加权函数为w:ER，对每个顶点v(v∈V)，从s到v存在一条通路，当且仅当对G运行BELLMAN-FORD（G,w,s）算法，算法终止时，有d[v]<∞。
定理：设G=（V，E）为带权有向图，源顶点为s，加权函数为w:ER，对该图运行BELLMAN-FORD（G,w,s）算法，若G不包含s可达的负权回路，则算法返回TRUE，对所有顶点v(v∈V)，有d[v]=∮(s,v)成立。
前趋子图G是以s为根的最短路径树。
如果G包含从s可达的负权回路，则算法返回FALSE。
7．4Dijkstra’s algorithm
目的：解决有向加权图的最短路径问题。
条件：该图的所有边的权值非负。
算法思想：设置一个结点集合S，从源点s到集合中结点的最终最短路径的权均已确定。
算法反复挑选出其最短路径估计为最小的结点u∈V-S，把u插入到集合S中，并对离开u的所有边进行松弛。
Dijkstra算法总是在集合V-S中选择“最近”的结点插入集合S中，它使用了贪心策略。
Dijkstra(G,w,s)Init-Singlesource(G,s)s = emptyQ = V[G]while ( Q != empty) do u = extract-min(Q) s = s and {u} for 每个顶点v属于Adj[u] do Relax(u,v,w)
Dijkstra执行过程：
定理：Dijkstra算法的正确性证明
证明：将证明对每一结点u属于V，当u被插入集合S时有d[u]＝Q(s,u)成立，且此后该等式一直保持成立。
设u为插入集合S中的第一个满足d[u]!=Q(s,u)的结点。
可知u!=s，可知u被插入集合S前S!=空。
从s到u必存在某条通路，否则
d[u]=Q(s,u)＝inf，与
d[u]!=Q(s,u)矛盾。
因为存在一条通路，所以存在一条最短路p。
路径p联结集合S中的结点S 到V-S的结点u。
考察沿路径p的第一个属于V-S的结点y。
设x属于V是y的
先辈。
路径p可以分解为s~p->x和y~p2->u。
（若第一个点为u，则
d[u]=Q(s,u)，已得证）
因为s到u的最短路径上y出现在y之前且所有边的权均为非负，我们有Q(s,y)<=Q(s,u),因而d[y] = Q(s,y) <= Q(s,u) <=d[u],但因为在第5行选择u时结点u和y都属于V-S，所以有d[u]<=d[y]。
因此d[u]=d[y]。
最后得出结论d[u]=Q(s,u)，这与我们对u的假设矛盾。
Dijkstra算法效率：若用线性数组实现优先队列：每次Extract_Min为O(v)，存在V次，则为O(v^2)。
for中有E次迭代。
所以整个算法运行时间O(V^2)。
稀疏图用二叉堆比较合适。
Extract_Min需要O(lgv)，建立需要O(V)。
更改权值用Decrease_key。
总时间为O((V+E)lgV)。
如果用斐波那契堆可以进一步提高效率至O(VlgV+E)。
7．5总结
根据各种教材介绍，还有几种经典的算法，所有顶点之间的最短路径（Floyed算法）、特定两个顶点之间的最短路径（A*算法）等。
在上述介绍的算法，当减低问题规模时，为了降低算法的时间复杂度，应该想办法缩小搜索范围。
而缩小搜索范围，都用到了一个思想——尽可能的向接近最后结果的方向搜索，这就是贪婪算法的应用。
比如Dijkstra算法总是在V-S中选择“最轻”或“最近”的顶点插入到集合S中，所以我们说它用了贪心策略。
两种算法中用到的松弛技术就是通过缩小最短路径的估计值，尽可能的向接近最后结果的方向搜索。
