身要阶段来求过程的艇戏化 (15) 3 )8 (18)/(15)4 (12 ③Q 如x12 3 图5-1运输网络图示
11 1.多阶段决策过程的最优化 图5-11 运输网络图示
项多阶段决歌过程的圾优化 动恋规求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的 系列变换来实现的。一般情况下,系统在某个阶 段的状态转移除与本阶段的状态和决策有关外 还可能与系统过去经历的状态和决策有关。因此, 问题的求解就比较困难复杂。而适合于用动态规 划方法求解的只是一类特殊的多阶段决策问题, 即具有“元后效性”的多阶段决策过程。所谓无 后效性,又称马尔柯夫性,是指系统从某个阶段 往后的发展。仅由本阶段所处的状态及其往后的 决策所决定,与系统以前经历的状态和决策(历史 无关
12 1.多阶段决策过程的最优化 三、动态规划求解的多阶段决策问题的特点 通常多阶段决策过程的发展是通过状态的一 系列变换来实现的。一般情况下，系统在某个阶 段的状态转移除与本阶段的状态和决策有关外， 还可能与系统过去经历的状态和决策有关。因此， 问题的求解就比较困难复杂。而适合于用动态规 划方法求解的只是一类特殊的多阶段决策问题， 即具有“无后效性”的多阶段决策过程。所谓无 后效性，又称马尔柯夫性，是指系统从某个阶段 往后的发展，仅由本阶段所处的状态及其往后的 决策所决定，与系统以前经历的状态和决策(历史) 无关
1多阶段决过程的量优化 四、动忞规划方法导 例5.1:为了说明动态规划的基本思想方法 和特点。下面以图5-1所示为例讨论的求最短路 问题的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果, 再对它们—一进行比较,求出最优方案。这里从 V到v的路程可以分为4个阶段。第一段的走法 有三种,第二三两段的走法各有两种,第四段的 走法仅一种,因此共有3×2×2X1=12条可能的 路线,分别算出各条路线的距离,最后进行比较, 可知最优路线是ⅵ→巧咋·丙0,最短 距离是18
13 1.多阶段决策过程的最优化 四、动态规划方法导引 例5.1：为了说明动态规划的基本思想方法 和特点，下面以图5-1所示为例讨论的求最短路 问题的方法。 第一种方法称做全枚举法或穷举法。它的 基本思想是列举出所有可能发生的方案和结果， 再对它们一一进行比较，求出最优方案。这里从 v1到v10的路程可以分为4个阶段。第一段的走法 有三种，第二三两段的走法各有两种，第四段的 走法仅一种，因此共有3×2×2×1＝12条可能的 路线，分别算出各条路线的距离，最后进行比较， 可知最优路线是v1 →v3 → v7 → v9 →v10 ,最短 距离是18．
项多阶段决歌过程的圾优化 显然。当组成交通网络的节点很多 时,用穷举法求最优路线的讣算工作量 将会十分庞大,而且其中包含着许多重 复计算 第二种方法即所谓“局部最优路径” 法,是说某人从k出发,他并不顾及全线 是否最短,只是选择当前最短途径 “逢近便走”,错误地以为局部最优会 致整体最优,在这种想法指导下,所取 决策必是Ⅵ→>VV18”0 全 程长度是20:显然,这种方法的结果常 是错误的
14 1.多阶段决策过程的最优化 显然，当组成交通网络的节点很多 时，用穷举法求最优路线的计算工作量 将会十分庞大，而且其中包含着许多重 复计算． 第二种方法即所谓“局部最优路径” 法，是说某人从k出发，他并不顾及全线 是否最短，只是选择当前最短途径， “逢近便走” ，错误地以为局部最优会 致整体最优，在这种想法指导下，所取 决策必是v1 →v3 →v5 → v8 → v10 ，全 程长度是20；显然，这种方法的结果常 是错误的．
1多阶段决过程的优化 第三种方法是动态规划方法。动态 规划方法寻求该最短路问题的基本思規 是。首先将问题划分为4个阶段,每次的 选择总是综合后继过程的一并最优进行 考慮,在各段所有可能状态的最优后继 过程都已求得的情况下,全程的最优路 线便也随之得到。 为了找出所有可能状态的最优后继 过程。动态规划方法总是从过程的最后 阶段开始考慮,然后逆着实际过程发展 的顺序,逐段向前递推计算直至始点
15 1.多阶段决策过程的最优化 第三种方法是动态规划方法。动态 规划方法寻求该最短路问题的基本思想 是，首先将问题划分为4个阶段，每次的 选择总是综合后继过程的一并最优进行 考虑，在各段所有可能状态的最优后继 过程都已求得的情况下，全程的最优路 线便也随之得到。 为了找出所有可能状态的最优后继 过程，动态规划方法总是从过程的最后 阶段开始考虑，然后逆着实际过程发展 的顺序，逐段向前递推计算直至始点