资源描述：
《第2讲引例-最短行军路线问题》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第2讲引例：最短行军路线问题教学内容：1）用“标号法”求解最短行军路线问题；的动态规划模型和2）建立最短行军路线问题的动态规划模型的建模方法；3）动态规划的术语：阶段、状态、决策、状态转移、策略、报酬函数和口标两数；4）可逆动态规划的顺序解法，教学目的：1）掌握动态规划的基本术语；2）掌握求解动态规划问题的逆序方法；3）了解建立动态规划模型的一般过程；教学重人L1）掌握动态规划的基本术语；2）掌握求解动态规划问题的逆序方法；教学难点：1）动态规划问题的建模方法；2）求解动态规划问题的逆序方法；作业布置：P
2、51,3一最短行军路线问题1问题描述：图1.1」屮给出一个行
3、军路线网络，从A点要走到G点，屮间要经过B、C、D等很多站，各站间的距离如图小所示，今要求选择一条由A点到G点的最短行军路线。图1.1.12“标号法”求解：（1）先标第五段：因从耳或笃到G点,仅各有一条路线，因而也分别是它们的最短路线，于是将其最短距离值4和3分别标写在斤、厲的圆圈内，并划上路径片TG及&TGo（2）再标第四段:从目点出发有两种举措可供选择:一是从厶过片到G点,其距离值为3+4=7；另一•是从目过耳到G点，其距离值为5+3=8o这样，从Q出发过片到G点是授短路径，将其距离值7标写在Q的【员【圈内，并划上路径GtF。同样，从Eg出发，也有两种决策可供选
4、择，即E2TF1TG和E2T笃TG并划上路径E2^F2.同理，E.到G的最优路径为值为6+3=9,将9标写在耳的圆圈内，并划上路径耳―巧。依次类推,如图得到最佳路线：AtB
5、TC2tD
6、TE2t£tG二动态规划的术语:（1）阶段（Stage）：最短行军路线问题是一个多阶段决策过程。它共分为六哥相互联系的阶段。常用K表示阶段变量，K=0,1,…，50对有n个阶段的问题，K的值为：K=0,1,•••,n-1o（2）状态（State）：最短行军路线问题中，各阶段都有若干个站，这些站，它是该段以后某路径的出发点，也是前一•段路径的终点，这些站叫做状态（各阶段的站叫做该阶段的
7、状态）。如第二阶段有四个状态，即点集^{C,,C2,C3,C4）o其状态的描述，要求其满足无后效性。例如最短行军路线问题的第二阶段的状态集合可记为X?={兀；）,雋2）,・・・,兀『}={1,2,3,4}={C,,C2»C3,C4}（3）决策（Decision）：决策就是某阶段状态给定后，从该状态演变到下一阶段某状态的选择。描述决策的变量，称为决策变量。常川你（忑）表示第k阶段处于笫耳状态时采取的决策。显然/（忑）是状态兀的函数，它的取值范围称为允许决策集合，通常以Dk（xk）表示第k阶段处于状态无的允许决策集合，即檢（"疋Dg例如，在最短行军路线问题中,第一阶段的
8、状态集合是={B^B2]y则从B]站出发,它有可能三种决策，即无取值色时•，其决策集合为0（0）={CpC2,C3}rto选择从冋到G的路径,则络（BJ二C?;如选择从耳到C3的路径,则U｝（B｝）=C3.同理,Wi（B2）g0（（52）={C2,C3,C4}（4）状态转移：在最短行军路线问题中，当给定笫k段状态变量耳的值球°,如果决策变量姝Of）的值一经确定（如选取从第k阶段第i点到地k+1阶段第j点的路径），则第k+1阶段的状态变量耳+］的值也就完全确定，即xA+1=?y）,这时，人+1由此可见，，i般来说，耳有的值随耳和檢的值变化而变化，这种变化关系可用函数表
9、示为：（5）策略（Policy）：假设给定问题可分为n个阶段，k=O,l,...,n-l,那么由第0阶段开始到第n-1阶段终点为止的过程组成的决策序列，就称为全过程策略，简称策略，记为坨”。即如最短行军路线问题中决定最优路线的策略是:£）6（Xo）={B],C2，D],E2，^，G}（6）报酬函数:当过程处于状态耳，并采取决策绰而得到的报酬（或费用）。显然，它是定义在X,xDk±的函数，称为第k段的报酬函数，记为《（忑,你）。在最短线路问题中,它表示第k阶段由点忑到第k+1段点血间的距离，即vguAGj,其中无二i,你=j。（7）目标函数：在决策过程中，用来衡量所实
10、现过程的优劣，定义在全过程和所有后部了过程的确定的数量函数，叫做冃标函数（或称指标函数）。若我们考虑的过程是从第k段开始到过程终点的k子过程，则口标函数町表示为：=V"（母9Uk，WA+1“冷-1）二匕（％/儿（兀））其最优F1标函数值叮表示为:fk（xk）=opt/（%%如,…，如）（…）=opt匕”（耳必（无））阳（Xr三最短行军路线的数学模型若引用状态变量檢和决策变量绰的记号，则上述各式可合并成下列方程组，这就是最短路线问题的动态规划数学模型：fkW=min{*（忑，妆（忑））+力+
11、血（忑））};"543,2,1,0（”）uk（xk）EDk（xk）并规定
