动态剡范解的特点 √通常多阶段决簟过程的发畏是通过状态的一糸列变换来 实现的。 一般情况下,糸统在某个阶段的状态转移除与本 阶段的状态和决箓有关外,还可能与糸统过去经历的 状态和决策有关。 √烫合于用动态规划方法求解的只是一类特殊的多阶段决 策问题,即具有“无后效性”的多阶段决策过程。 无后效性(又称马尔柯夫性)是指糸统从某个阶段往 后的发長,仅由本阶段所处的状态及其往后的决策所 决定,与糸统以前经历的状态和决簟(历史)无关
动态规划求解的特点 ✓ 通常多阶段决策过程的发展是通过状态的一系列变换来 实现的。 一般情况下，系统在某个阶段的状态转移除与本 阶段的状态和决策有关外，还可能与系统过去经历的 状态和决策有关。 ✓ 适合于用动态规划方法求解的只是一类特殊的多阶段决 策问题，即具有“无后效性”的多阶段决策过程。 无后效性(又称马尔柯夫性)是指系统从某个阶段往 后的发展，仅由本阶段所处的状态及其往后的决策所 决定，与系统以前经历的状态和决策(历史)无关
动态视州问氩实俐 例6-1给定一个线路网络,要从A向F铺设一条輪油管, 各点间连线上的数字表示距离,问应选择什么路线,可 使总距离最短? 2 E1人3 B,K3 E G B
A 动态规划问题实例 C4 C2 D3 D2 G B2 B1 C1 C3 D1 E3 E2 E1 F2 F1 5 3 1 3 6 8 7 6 6 8 3 5 3 3 8 4 2 2 1 2 3 3 3 5 5 2 6 6 4 3 例6-1 给定一个线路网络，要从A向F铺设一条输油管， 各点间连线上的数字表示距离，问应选择什么路线，可 使总距离最短？
动态视
A 动态规划C4 C2 D 3 D 2 G B 2 B 1 C 1 C 3 D 1 E 3 E 2 E 1 F 2 F 1 53 1 36 8 7 6 6 8 353384 2212 3 3 3 5 52 6 6 4 3
动态說剡的基本食 1.阶段与阶段变量 为了便于求解和表示决策及过程的发畏顺序, 而把所给问题恰当地划分为若干个相互联糸又有 区别的子闷题,称为多段决簟问题的阶段。 描述阶段的变量称为阶段变量,常用k表示。 阶段的划分,一般是根据肘间和空间的自然特征 来进行的,但要便于问题转化为多阶段决策
1.阶段与阶段变量 为了便于求解和表示决策及过程的发展顺序， 而把所给问题恰当地划分为若干个相互联系又有 区别的子问题，称为多段决策问题的阶段。 描述阶段的变量称为阶段变量，常用k表示。 阶段的划分，一般是根据时间和空间的自然特征 来进行的，但要便于问题转化为多阶段决策。 动态规划的基本概念
动态說剡的基本食 2状态、状态变量与可能状态集 描述事物(或糸统)在某特定的肘间与空间城中所处 位置及运动特征的量,称为状态。反映状态化的量叫 做状态变量。状态变量包含在给定的阶段上确定金部允 许决簟所需要的信息。 每个阶段的状态可分为初始状态和终止状态,或称 輪入状态和输出状态,阶段k的初始状态记作Sk,终止状 态记为Sk1通霈定义阶段的状态即指其初始状态。 般状态变量的取值有一定的范圄或允许集合,称 为可能状态集,或可达状态集。可能状态集实际上是关 于状态的约柬条件。通常可能状态集用相应阶段状态Sk 的火写字母Sk表示,Sk∈Sk
动态规划的基本概念 2.状态、状态变量与可能状态集 描述事物(或系统)在某特定的时间与空间域中所处 位置及运动特征的量，称为状态。反映状态变化的量叫 做状态变量。状态变量包含在给定的阶段上确定全部允 许决策所需要的信息。 每个阶段的状态可分为初始状态和终止状态，或称 输入状态和输出状态，阶段k的初始状态记作sk，终止状 态记为sk+1。通常定义阶段的状态即指其初始状态。 一般状态变量的取值有一定的范围或允许集合，称 为可能状态集，或可达状态集。可能状态集实际上是关 于状态的约束条件。通常可能状态集用相应阶段状态sk 的大写字母Sk表示，sk∈Sk