6 第八章动态规划 表86 项目投资额 数益值 3 60 0 40 1 64 S82动态规划的基本概念和基本原理 一、动态规划的基本概念 (一人、阶段 应用动态规划方法时，问题必须能划分为若干阶段。在每一阶段都可作出不同的决策 以控制这个阶段的发展过程.这就是所谓多阶段决策过程.前面已经指出，如果我们把一 个可能实现的从最初阶段到最后阶段的一系列决策（每个阶段一个决策）称为一个策略 那么，动态规划的目的便在于从众多的策略中寻求最优策略。这个寻求过程，在一般情况 下和实际决策过程的方向相反，即所谓逆序求解。通常用k作为表示阶段的变量.本书以 k=1表示计算的第1阶段，即实际决策的最后1个阶段，k=2表示实际决策的倒数第2 个阶段，如此逐阶段顺序编号，直至实际决策的最初阶段。 (二入、状态和状态变量 状态可理解为事物的某种特征。状态发生变化，意味着事物有了发展、变化。在动态 规划问题中，状态是划分阶段和各阶段决策的依据，阶段的推移意味着状态的变化，多阶 段决策过程的发展可以用过程各阶段状态的演变来措术。应用动态规划必须能够完格列 举出每一阶段开始时的一切可能状态 状态通带可以用一个数 组数)来表示，称为 状态变量（或向量）。我们用k表示阶段k的状态变量。例2投资间题中每一阶段开始时 的状态是尚未分配的投资额，在第1阶段（对C决策），81=0,1,2,3,4在第2阶段（对B 决策)，2=0,12,34在第3阶段（对A决策， 53 4.例1最短路线向题中各阶段开始时 的状态是铁路线通过地点，如第1阶段可能状态是D1和D2,它们不是数但如有必要可 约定用两个数（例如1和2）分别表示D1和D2。状态用数表示，以便于进行计算 (但入、决策和决策变量 实际过程从初始状态开始逐阶段向前发展，每一阶段达到一个可能状态。下一阶段进 入什么状态，取决于这一阶段作出的决策，也就是说，决策就是各阶段对状态演变诸种可 能性的选择。在许多何题中，决策可以自然而然地用一个数（或一组数）表示，称为决策变 量（或向量），我们用xk表示第k阶段的决策变量。例如，例2中的决策变量表示的是对 某一投资项目的选择，例1中各阶段的决策是路线的选择，不是数为了计算方便，可以 将不同的决策人为地规定为不同的数.各阶段全部可能的决策称为该阶段允许决策集合 记为Xk.每个阶段的允许决策集合不一定相同.每一阶段某一状态下可能的决策一般也 只能是该阶段允许决策集合的一个子集 (四)、状态转移方程 如果第k阶段开始时状态为，作出的决策为k,那么第k阶段末（即第k一1阶段
6 ÷✡ø✡ùûú➋ü✏ý✡þ Ù 8–6 ①③② ⑦ s✁⑧ ❡✁⑩✽ A 3 60 B 0 40 C 1 64 §8.2 ➞❧➟❧➠❧➡❧➢❧➤❧➥❧➦❧➧❧➨➩➤❧➥➩➫❧➭ ➽➺➾ ➞❧➟❧➠❧➡❧➢❧➤❧➥❧➦❧➧ (➯)❙✢▲✡◆ ➯Ó③Ó⑧✚Ó❻❈✇Ó②✭ , ❁Ó❂✢✓✢➲Ô ❈Ó❉☞Ó❊Ó❋Ó❘Ó❙, ☛Ó◗✧❘Ó❙✖Ó✗❚Ó❯ ❼Ó✬Ó✓Ó✳✡✴, ✷✢➳✢➵Ó✜●Ó❘Ó❙✓ç✢➸✒✁✼✡✛ ✜✢✆✡✦✡✱Ó⑦ ❨▲Ó◆Ó❬Ó❭✢➺✢➻Ó✛➼■✢☞Ö✍✏ÐÓ⑨❯ , ❴Ó❛Ó❱Ó❲Ó❜Ó✧ ● ✗ Ô✁☛✡✠✓✡❃✡✻✁✮❘✡❙✡✟✻✡➨❘✡❙✓✡✧❑❢✡✳✡✴ ( ◗✡●✡❘✡❙✧ ●✳✡✴) ✘ ☞✧ ● ❭✡❣, ❤✡✐, ⑧✚✡❻❈✡✓ ② ✓✡❧☛ ④✡❃♠ ❦✡✓✡✴✡♥➋♦r✸✡✹✰✻✡✼✰✴✡♥✡✛ ✜ ● ✸✰✹✡✒✝✼, ☛✧✁➃✁➽✁➾ í✢✚☛✢➙✳Ó✴Ó✒✢✼Ó✓✇ ✭❍✁➛, ❷Ó✱Ó⑦➪➚✢➶✢➹✢➘Ó✛➴✍✢➷Ó③ k ❚Ó☞ÙÓÚ❘Ó❙✓Ó✵Ó✶Ó✛ß➡✢➬✡✷ k = 1 Ù✡Ú✡ô✡➇✡✓✡Ñ 1 ❘✡❙, ❷☛✁➙✳✡✴✡✓✡✻✡➨ 1 ●✡❘✡❙,k = 2 Ù✡Ú☛✁➙✳✡✴✡✓❋Û✡Ñ 2 ●✡❘✡❙, ❴✡➈✡❶❘✡❙✁❻❡✁➮✡➍, ï✡ã☛✁➙✳✡✴✡✓✡✻✁✮❘✡❙✛ (➱)❙ ➄ t✁✃➄ t✁❐✁❒ ➄ t ✗✡✯✡❥☞✁❮✁❰✓✡⑤✡⑥✡✤✁Ï✡✛Ð➇✚✡ç➎✵✁Ñ, ❽✁Ò✁❉❮✁❰✲ ñ✡ç✁➸❙ ✵✁Ñ✡✛ ☛ ⑧✚ ❻ ❈✡❁✡❂➋♦, ➇ ✚✦✡❈✡❉❘✡❙✚✡➆❘✡❙✳✡✴✡✓✡P✝✶, ❘✡❙✓✰❹✁❽✁Ò✁❉✁➇✚ ✓✡✵✁Ñ✡✛✢❦❘ ❙✳✡✴✡✒✁✼✡✓ç✁➸✗✡✷✡③✰✒✝✼✡➆❘✰❙➇ ✚ ✓✝Ó✰✵✁✛✝Ô✩ ✛✢➯✰③✰⑧✚✰❻❈✁✓✝➲Ô✝➈✝Õ✁✻❢ ó ❯✰◗✧❘✰❙✫✝✬✭ ✓✰✧✝➆✰✗Ô➇ ✚ ✛☎➇✚✍✝➷✰✗✰✷✰③✰✧●Û (✩✰✧✝Ö✰Û) ✛✰Ù✰Ú, ✘ ☞ ➄ t✁❐✁❒(✩Ø×✁❒)✛➉❱✡❲✡③ sk Ù✡Ú❘✡❙ k ✓✁➇✚✵✡✶✡✛➉ÿ 2 ⑦ s✡❁✡❂➋♦◗ ✧❘✡❙✫✁✬✭ ✓✁➇✚✦❈Ù❖➋✡❉✁❷✡✓⑦ s✝⑧, ☛ Ñ 1 ❘✡❙ (✏ C ✳✡✴), s1 = 0,1,2,3,4; ☛ Ñ 2 ❘✡❙ (✏ B ✳✡✴),s2 = 0,1,2,3,4; ☛ Ñ 3 ❘✡❙ (✏ A ✳✡✴), s3 = 4✛➉ÿ 1 ✻✡ä✡➱✡➮✡❁✡❂➋♦✏➆❘✡❙✫✁✬✭ ✓✁➇✚✦✡Ï✡➱✡➮✁✍✡✒✡❰✡✥, ❴✡Ñ 1 ❘✡❙✗ Ô➇ ✚✦ D1 ✚ D2, ✂✡❲✡❼✡✦✡Û, ➁✡❴✡✲✁✓✡❖✡✗ Ú✔✡③→●Û (ÿ✡❴ 1 ✚ 2) ❉✁✴✡Ù✡Ú D1 ✚ D2 ✛☎➇✚ ③✡Û✡Ù✡Ú, ✷✡❧✡④å✡æô✡➇✡✛ (Û)❙✢❬✡❭✁✃✡❬✡❭✁❐✁❒ ☛✢➙✒✢✼Ó❃✢✮✢✬✢➇✚ ✫✢✬✡❶❘✡❙✭❖■ç✁➸, ◗ ✧❘Ó❙ÓðÓ✟✧ ● ✗ Ô➇ ✚ ✛ íÓ✧❘Ó❙✡å ❃✝Ü✰✐✝➇✚ , ➁✰✳✰④✰✜✰✧❘✰❙✰❚✰❯ ✓✰✳✰✴, ✾✝✆✰✦✰✫,❬✰❭Ý✆✰✦✰➆❘✰❙✏✝➇✚ Ó✰✵✝Þ✰⑥✰✗ Ô❺Ó✓Óàá ✛ ☛✢ß❦Ó❁Ó❂➋♦, ✳Ó✴Ó✗Ó✷áà✢➧✢✑Ó➧Ó❰Ó③✡✧●Û (✩Ó✧✢ÖÓÛ) ÙÓÚ, ✘ ☞ ❬Ó❭✢❐ ❒(✩â×✁❒)✛✢❱✡❲✡③ xk Ù✡Ú✡Ñ k ❘✡❙✓✡✳✡✴✡✵✡✶✡✛✢ÿ✡❴, ÿ 2 ♦✏✓✡✳✡✴✡✵✡✶✡Ù✡Ú✡✓✡✦✁✏ ⑤✰✧⑦ s ①➀② ✓✰àá , ÿ 1 ♦r➆❘✰❙✓✰✳✰✴✰✦✰➱✰➮✰✓✰àá , ❼✰✦✰Û✰✛ ☞✰ñ ô✰➇✇ ❧, ✗✰✷ ❇ ❼Ó✬Ó✓Ó✳Ó✴✢ã☞❰ ❻ ✔ ☞❼✡✬✡✓ÓÛ✡✛ ➆❘✡❙✢ä✎Ó✗Ô ✓Ó✳✡✴✡✘☞❪ ❘✡❙æå✢ç❬Ó❭✢è✢é, ✹✡☞ Xk ✛ ◗✡●✡❘✡❙✓✁êß ✳✡✴✁ë✁ì✡❼✡✧✁✔❍ ✬✡✛ ◗ ✧❘✡❙⑤✡✧✁➇✚í✡✗Ô ✓✡✳✡✴✡✧✁➃✡✾ ✵Ô✦✁❪❘✡❙êß ✳✡✴✁ë✁ì✡✓✡✧● ❳✁ë✡✛ (í)❙ ➄ t✁î✁ï✁ð✁➻ ❴✡❛✡Ñ k ❘✡❙✫✁✬✭ ➇ ✚✡☞ sk, ❚✡❯ ✓✡✳✡✴☞ xk, ❤✡✐✡Ñ k ❘✡❙✁ñ (❷✡Ñ k − 1 ❘✡❙
$82动态规划的基本概念和基本原理 7 初)的状态8k-1就已被确定.这就是说，Sk-1随sk及%而变化.可以把这一关系看成是 Sk-1与k和的函数关系，记为 Sk-1=g1(Sk:Tk) (8.1) 这一等式表示了某一阶段的状态向下一阶段状态转移的规律，称为状态转移方程.有很多 问题，这种函数关系可以用数学解析式表示.例如，对于例2有：5k-1=k一工k,S≥xk 这给计算带来方便.有的问题，例如例1，这种函数关系很雄用解析式表达，但这并不妨碍 我们用动态规划方法来解决向题。 (伍)、优劣指标 动态规划题的求解就是寻求最优策略，即寻找最优的可行的决策序列.这就需要有 一个指标，用以衡量一个策略的优劣，即衡量一个可以实现的状态演变过程的优劣，这个 指标称为优劣指标。例1中优劣指标是从A至E的路线总长度，例2是3个项目投资的 总效益值，优劣指标决定于过程的最初状态和各阶段所采取的决策，即它是初始状态和决 策序列的函数。而在各个阶段，在每一状态下所作出的每一决策都有一个影响总效果的直 接效果，它是sk和x的函数，记为dk(s,E)。例如例2中有： d山(s1,0)=48,51=0,1,2,3,4 d山(s3,2)=48,s3=4. 设整个过程从第n阶段开始.由第k阶段(k=1,2,)的状态sk开始至某一最 终状态的这一段过程，称为第k阶段状态跳的后部过程（相应的决策序列称为的后 部策略)。从例1、例2的解题步骤可知，动态规划方法的每一阶段都要找出该阶段每一状 态的最优后部过程（品优后部策路）从第k阶段状态开始的每一后部时程都可可象全 过程那样，规定一个指标，具有最优指标的后部过程称为最优后部过程。其相应指标记为 fk(s).例如在例2中，2(3)表示从第2阶段（对B投资）的状态3（剩余资金为3百万元） 开始的最优后部过程的总效益值。 (六)、指标递推方程 例1、例2中，在计算各个阶段的最优后部过程指标时，都要利用上一阶段已得到的 最优后部过程指标.第k阶段在状态5k下可采用不同的决策，每一决策都有一个影响目 标的直接指标d4(5k,xk):不同的决策又将使得过程进入第k-1阶段时，具有不同的开始 状态（各有不同的最优后部过程指标）.对于例1和例2，我们是这样计算第k阶段状态s 的最优后部过程指标的 fu(sk)=max/min{dx(sk,)+fk-1(g1(sk K)EX}, k=1,2,, (8.2) f0(so)=0 如果用f(sk,工)表示第k阶段在采取决策x的条件下影的最优后部过程指标，即 f(k,s)=d(sk,k)+fk-1(g1(sk,工k)》
§8.2 ú➋ü✏ý✡þ❈ò❖ó✁ô✁õ✁ö✁÷✁ó✁ô✁ø✁ù 7 ✮) ✓✁➇✚ sk−1 ✆➋✍❖ú●✔✡✛ ✜✁✆✡✦✡✫,sk−1 û sk ❤ xk ✑✡✵✁Ñ✡✛ ✗✡✷✡❜✡✜✡✧❩✡❑❆✡❞✡✦ sk−1 ➥ sk ✚ xk ✓✁ü✡Û❩✡❑, ✹✡☞ sk−1 = g1(sk, xk) (8.1) ✜Ó✧ÓÒ✢ýÓÙÓÚñ⑤Ó✧❘Ó❙✓✢➇✚ ✭×íÓ✧❘Ó❙➇ ✚❸Ó❹Ó✓❻✢þ, ✘ ☞ÿ➄t✢î✢ï✢ð✢➻Ó✛ ✲❝ ❦ ❁Ó❂, ✜Ó⑥✢üÓÛ❩Ó❑✗Ó✷Ó③ÓÛÓ➀✡❥✁✁ý✡ÙÓÚ✡✛ ÿ✡❴, ✏Ó④Óÿ 2 ✲: sk−1 = sk − xk, sk ≥ xk ✛ ✜✁➉✡ô✡➇✄✂✁✛✇ ❧✡✛ ✲✡✓✡❁✡❂, ÿ✡❴✡ÿ 1, ✜✡⑥✁ü✡Û❩✡❑✁❝➝✡③✡❥✄✁ý✡Ùð , ➁✡✜✡➂✡❼✄☎✄✆ ❱✡❲✡③✡⑧✚✡❻❈✇✡②✛✡❥✡✳✡❁✡❂✡✛ (✝)❙✟✞✄✠✄✡✄☛ ⑧✚Ó❻❈Ó❁Ó❂Ó✓Ó✹Ó❥✢✆Ó✦✡✸Ó✹✡✻✡✼Ó✴✡♥, ❷Ó✸ÓqÓ✻Ó✼Ó✓Ó✗æ ✓Ó✳Ó✴Ó❡✡❢Ó✛ ✜✢✆✡⑩Ó❖✡✲ ✧ ● ⑨✌☞, ③✰✷✌✍✰✶✰✧● ✴✰♥✰✓✰✼✌✎, ❷✌✍✰✶✰✧● ✗✰✷ ☛✰✠✓✝➇✚ Ó✰✵✰✒✝✼✰✓✰✼✌✎, ✜ ● ⑨✄☞✡✘☞ ✞✄✠✄✡✄☛✡✛ ÿ 1 ♦✏✼✄✎✡⑨✄☞✡✦✡❃ A ã E ✓✡➱✡➮❸õ✡ö, ÿ 2 ✦ 3 ●✁①③②⑤⑦s✡✓ ❸❡✁⑩✽, ✼✄✎✡⑨✄☞✡✳✁✔✡④✡✒✁✼✡✓✡✻✁✮✁➇✚ ✚✡➆❘✡❙✱✄✏✁➁✡✓✡✳✡✴, ❷✁✂✡✦✁✮✁✬✁➇✚ ✚✡✳ ✴Ó❡Ó❢Ó✓✢üÓÛÓ✛➼✑☛➆ ●Ó❘Ó❙, ☛Ó◗✧✢➇✚íÓ✱❚Ó❯ ✓◗ ✧✡✳Ó✴✡✖✡✲Ó✧●✁✑✄✒✁❸❡ ❛Ó✓✡ï ✣ ❡ ❛, ✂✡✦ sk ✚ xk ✓✁ü✡Û, ✹✡☞ dk(sk, xk)✛✢ÿ✡❴✡ÿ 2 ♦✏✲: d1(s1, 0) = 48, s1 = 0, 1, 2, 3, 4; d3(s3, 2) = 48, s3 = 4. ❮ ✻✰●✒✝✼✰❃✰Ñ n ❘✰❙✫✝✬✰✛❖✪rÑ k ❘✰❙ (k = 1,2,. . .,n) ✓✝➇✚ sk ✫✝✬✰ã✰⑤✰✧✰✻ è✝➇✚ ✓✰✜✰✧❙ ✒✝✼, ✘ ☞✔✓ k ▲✰◆➄ t sk ✕✌✖✌✗➺✝➻(❍➯✰✓✰✳✰✴✰❡✰❢✰✘☞ sk ✕✌✖ ✗❭✡❣)✛ ❃✡ÿ 1❙ ÿ 2 ✓✡❥✡❂✡➛✡➜✡✗✁✸, ⑧✚✡❻❈✇✡②✓◗ ✧❘✡❙✖✡❖✡q❯ ❪ ❘✡❙✡◗✧✁➇ ✚ ✓✰✻✰✼✰➨✝✎✰✒✝✼ (✻✰✼✰➨✝✎✰✴✰♥)✛ ❃✰Ñ k ❘✰❙➇ ✚ sk ✫✝✬✰✓◗ ✧✰➨✝✎✰✒✝✼✰✖✰✗✌✘ä ✒✁✼✡❤✡❀, ❻ ✔✡✧● ⑨✄☞, ➣ ✲✡✻✡✼✡⑨✄☞✡✓✡➨✁✎✡✒✁✼✡✘☞✚✙✞✖✄✗➺✁➻✡✛ ➫✡❍➯✡⑨✄☞✹✡☞ fk(sk)✛ ÿ✡❴☛ ÿ 2 ♦,f2(3) Ù✡Ú✡❃✡Ñ 2 ❘✡❙ (✏ B ⑦ s) ✓✁➇✚ 3(❺✁➂✁s✁t☞ 3 ✉✁✈✁✇) ✫✁✬✡✓✡✻✡✼✡➨✁✎✡✒✁✼✡✓❸❡✁⑩✽✡✛ (✛)❙✟✡✄☛✄✜✄✢✁ð✁➻ ÿ 1❙✢ÿ 2 ♦, ☛ô✡➇✡➆●✡❘✡❙✓✡✻✡✼✡➨✝✎✰✒✝✼✡⑨✌☞✭ , ✖✡❖✁★✡③❅✧❘✡❙ ✍❚ ✟ ✓ ✻✡✼✡➨✁✎✡✒✁✼✡⑨✄☞✡✛✢Ñ k ❘✡❙✡☛➇ ✚ sk í✡✗✄✏✡③✡❼✡✬✡✓✡✳✡✴, ◗ ✧✡✳✡✴✡✖✡✲✡✧●✄✑✄✒③② ☞✡✓✡ï✁✣✡⑨✄☞ dk(sk, xk); ❼✡✬✡✓✡✳✡✴✄✣❇❢ ❚✡✒✁✼å ❃✡Ñ k − 1 ❘✡❙✭ , ➣ ✲✡❼✡✬✡✓✁✫✁✬ ➇ ✚ (➆Ó✲Ó❼Ó✬Ó✓Ó✻Ó✼Ó➨✢✎Ó✒✁✼Ó⑨✄☞)✛ ✏Ó④✡ÿ 1 ✚Óÿ 2, ❱Ó❲Ó✦Ó✜Ó❀ÓôÓ➇ÓÑ k ❘Ó❙➇ ✚ sk ✓✡✻✡✼✡➨✁✎✡✒✁✼✡⑨✄☞✡✓: fk(sk) = max/min{dk(sk, xk) + fk−1(g1(sk, xk))|xk ∈ Xk}, k = 1, 2, . . . , n; f0(s0) = 0 (8.2) ❴✡❛✡③ fk(sk, xk) Ù✡Ú✡Ñ k ❘✡❙✡☛✏✁➁✡✳✡✴ xk ✓✡â✄✤✡í sk ✓✡✻✡✼✡➨✁✎✡✒✁✼✡⑨✄☞, ❷ fk(sk, xk) = dk(sk, xk) + fk−1(g1(sk, xk))
8 第八章动态规划 则式(82)可点为 f(sk)=max/min{fu(sx,rk)EX),k =1.2.....n; f(sk,工k)=d(sk,k)+f-1(g1(sk,工k)月 (8.3) fo(so)=0. 以例2中儿确具体数字为例（是见表8-3）： f2(3,0)=d2(3,0)+1(3-0)=40+78=118 f2(3.1)=d2(3.1)+f(3-1)=42+68=110 f2(3,2)=d2(3,2)+五3-2)=50+64=114. f26,3)=d2(3,3)+3-3)=60+48=108 2(3)=max{f2(3.0,f(3,1),f2(3,2).f2(3,3)} -max{118,110,114,108}-118. 诺推奢关政款为指被推方程电所为货全西的本方程只有建可这 ,策变对以理寻求从蕞以优值也始样值问题计算，， 宝零R》 fu(sk,x)=g2(dk(sk,K),fr-1(g1(sk,A))) (8.4) 出我要们变够写出我学表达式，但如不以每果式(8)中相加个形式例那要以段 f(sk,)=d(sk,x)·fk-1(g1(sk,x》 么解，此便还需 每6()-1, 中、动态规划基方原法 建同指用递推程←基种在例1中动指介即，更段以性个表规不果类国Bmam首 先提出，最优化原算： 此理过程不 个两警明 “据这理余甘 策略.。 具体寻求指用计算 ,要应盘相邻两优值，指用递推程. 化然后中包含着对 韩他这理要们就果动。略划寻求中 上相 安具备无后发安凭效式有县在甘论转移过阅护以设法划某鲨美 ,以后过程。发展仅仅取 省讨接中只要最1优位 表膜能这以质 各优值果经过什么 金法桨含西是优值个路 ,而与这以便则以前 债无 策要不管 路.例2中，股1优值只要剩余。投资额 泰不弹做针其A线 3奇有投资0剩下 ,还果向A投资2向B投资剩下，等待，都不影响在这以 属邦香上相策略较资1百下.这理然不果建同动 下对C ,论略划模计个基本要们十 、只变动过程而不具备无后效性就米果动， 不变据以建计诊划棋计靓例1，例2 无资果商阶下个计论较 对以理划例导求建同动论略划模计， 个 段以下儿理步：
8 ÷✡ø✡ùûú➋ü✏ý✡þ Õ✁ý (8.2) ✗✄✥☞ : fk(sk) = max/min{fk(sk, xk)|xk ∈ Xk}, k = 1, 2, . . . , n; fk(sk, xk) = dk(sk, xk) + fk−1(g1(sk, xk)); f0(s0) = 0. (8.3) ✷✡ÿ 2 ♦➩●✡➣✡↔Û✡Ü☞ ÿ (✦✁❁✡Ù 8–3): f2(3, 0) = d2(3, 0) + f1(3 − 0) = 40 + 78 = 118, f2(3, 1) = d2(3, 1) + f1(3 − 1) = 42 + 68 = 110, f2(3, 2) = d2(3, 2) + f1(3 − 2) = 50 + 64 = 114, f2(3, 3) = d2(3, 3) + f1(3 − 3) = 60 + 48 = 108, f2(3) = max{f2(3, 0), f2(3, 1), f2(3, 2), f2(3, 3)} = max{118, 110, 114, 108} = 118. ý (8.2) ✩ (8.3) ✘ ☞ ✡✄☛✄✜✄✢✁ð✁➻, ✾✡✘☞ s✡t✉✡✈✕✄✧✄★ð✁➻✄✩☎✵✄✪✄✫✄✬✄✭✄✮✄✯ ✰✄✱✄✲✄✳, ✴✄✵✄✶✄✷✄✯✄✸✄✹✄✺✄✻✄✷✄✼✄✽✄✾✄✿✄❀✄✽✄❁✄❂✄❃✄❄, ❅✄❆✄❇✄❈✄❉✄❊✄❋✄●✄❅✄❍✄■✄✩ ✮✄❏✄❑✄▲✄▼✄◆,fk(sk, xk) ❖✄P✄◗✄❘✄❙ dk(sk, xk) ❚ fk−1(g1(sk, xk)) ●✄❯✄❱: fk(sk, xk) = g2(dk(sk, xk), fk−1(g1(sk, xk))) (8.4) ❯✄❱ g2 ▲✄❲✄✵✄❳✄❨✄◆✄❱✄❩✄❬✄❭✄❪, ❫✄❴✄❵✄✷✄◗✄❛✄❪ (8.3) ❜❞❝✄❡✄●✄❢✄❪, ❣✄❤✄❖✄P✄❙ fk(sk, xk) = dk(sk, xk) · fk−1(g1(sk, xk)) ✐✄❥, ❦✄❧✄♠✄❑✄♥✄◗ f0(s0) = 1✩♦q♣❞rqsqtq✉q✈q✇q①q② ✫✁✬✁▼✁③✰✁✱✁④❋✁●✁⑤✄⑥, ⑦✁❣ 1 ❜✁⑧⑩⑨✁❶✁❷✁✩❹❸✁❙✁✷✁❺✁●✁❬✄❻✄❼✁❛✄❽✁❾ Bellman ❿ ➀✄➁◆✄●➃➂✄➄✄➅✄➆✄➇: “⑨✌❙✌➈✌✯✌❊✌❋✌●✌❅✌❍✌➉✌➊✌➋✌✪✌✮✌➌✌●✌➍✌➎: ➏✌➐✌➑✌❊✌➒✌●✌➓✌➔✌❚✌→✌➉✌❤✌➣, ✶✌↔✌↕ ●✄→✄➉✄➙✄❢✄➛✄●✄➓✄➔✄➜✄➝, ➞✄➟✄●✄➠✄→✄➉✄➡✄➢✄➤✄➛✄❅✄❍✄➉✄➊✄✩ ” ➥✁➦✮✁✯✁➧✁➨✁❚✁➋✁➩✁✸✁✹✄▼✁③✄❃✁❄✄●✁➫✄➭, ❖✁➯✁◆✁❝✁➲✁➳✁✼✁✽✁●✁▼✁③✰✁✱✄④❋✁✩➵❅✄❍ ➸➧✄➨➺❜❞➻✄➼✄➽✄✶✄➙✄◗✄❘✌●✌➓✄➔✌●✌➫✄➾✌▲✄❲✌✩✟✮✌✯✌▲✄❲✌➚✄❛✌➪✌➔✄♥✌➶✌✸✄✹➹❜❞●✌➓✌➔✄✷✌◗ ▲✄➋✄➘ “➴✄➷✄➬✄➮”✩➱➙✄✃ “➴✄➷✄➬✄➮”, ▼✄●✄❛✄⑦✄➓✄➔✄❐✄❒✄❊✄❋➺❜, ✷✄❮✄❭✄❈✄❰✄✷✄✼✄✽✄●✄❰ ✷✄➓✄➔, P✄Ï✄❊✄❋✄●✄Ð✄Ñ✄Ò✄Ò✄Ó✄→✄Ô✄✮✄✷✄❧✄Õ✄●✄➓✄➔, ➜✄Ö✄✮✄✷✄❧✄Õ✄P✄↔✄●✄➓✄➔✄❚✄→✄➉✄➐ ✲ ✩×❣ 1 ❜, Ø✄▲✄✻ 1 ✼✄✽✄●✄Ù✄✿✄➓✄➔✄❛ D2, Ú✄Û✄❵✄Ü✄↔✄↕ 3 ✯✄✼✄✽✄●✄→✄➉✄❤✄➣, ➏✄❵✄Ü Ý✼✌✽✌❛✌Þ✌❊✌ß✌Û✌➓✌➔✌➜✌❭✌❈ D2 ●, à✌❵✌á✌â✌✺✌➓✌➔ D2 ◆✌Ð✌●✌❅✌❍✌➉✌➊ (ã✌ä D2 å E ●✄æ✄ç)✩×❣ 2 ❜, ✻ 1 ✼✄✽, Ø✄▲✄è✄➞✄●✄é✄ê✄ë✄❙ 1, Ú✄Û✄✮ 1 ì✄í✄î✄➐✄➑✄❛➺ï A é✄ê 3 ï B é✄ê 0 è✄➟✄●, ♠✄❛➺ï A é✄ê 2 ï B é✄ê 1 è✄➟✄●, ð✄ñ, à✄❵✄á✄â✄⑦✄✮✄✷✄➓✄➔ ➟✌✶ C ●✌❅✌❍✌➉✌➊ (é✌ê 1 ì✌í✌î)ò✟✮✌✯✌➧✌❼✌❛✌✫✌✬✌➪✌➔✌♥✌➶✌ó✌ô✌●✌⑤✌õ✌▲✌❲, ö✌÷✌ø ▲✄ò✟❤✄ù✄♥✄◗✄●✄➓✄➔✄Ø✄✵✄ú✄❻✄❊✄❋✄➜✌❵✄➋✄➘✌➐✄Ï✌û✄➍, ➚✄❵✄❛✄➪✄➔✄♥✄➶✄ü✄❘✄➟✄●✄➓✄➔, ➏ ❵✄✵➦ P✄✫✄✬✄➪✄➔✄♥✄➶✄ó✄ô✄ò✟❣ 1, ❣ 2 ➓✄➔✄●✄➐✄Ï✄û✄➍✄❛✄ö✄÷➺ý✐ ●✄ò ✶✄✷✄✯✄þ✄ÿ✄✸✄✹✄✫✄✬✄➪✄➔✄♥✄➶✄ó✄ô, ❖✁✁✂✄❙✄P✄➟✁✄✄✯✁☎✁✆: