数学模型 目标(指标)函数:衡量策略好坏的函数。 从Sk出发到终点的目标函数记为: kn(k,kg xn),k=1,2,…, 视Sk为确定状态,k,…n是变化的 ·从sk出发到终点的最优目标值: f(Sk)=opt vk,(sk,xk,,xn) k=1, 2,...,n (opt为min或max) 例中:f(4)为A到E的最短路程, 相应的策略为所求的最优策略—最短路。 f∫(Sk)对应的策略为Sk到终点最优子策略。 KAD
• 目标（指标）函数：衡量策略好坏的函数。 从 sk 出发到终点的目标函数记为： vkn(sk , xk , , xn ), k = 1,2, ,n 视 sk 为确定状态， xk , , xn 是变化的。 • 从 sk 出发到终点的最优目标值： ( ) ( , , , ) , , kn k k n x x f k sk opt v s x x k n = (opt 为 min 或 max) k = 1,2, ,n 例中： ( ) f1 A 为A 到E 的最短路程， 相应的策略为所求的最优策略— 最短路。 ( ) k k f s 对应的策略为 sk 到终点最优子策略。 2 6
(数学模型 2.最优化原理 例中:有最优策略 {x1(4)=B2,x2(B2)=C1,x3(C1)=D1,x4(D1)=E 即{A→B2→C1→>D1→B A到E的最短路,路长为f(A)=11 子策略:{B2→>C1→>D1→E} B2到E的最短路,路长为f2(B2)=7 {C1→D1→E} C1到E的最短路,路长为∫(C1)=4 # KAD
2. 最优化原理 例中：有最优策略 { ( ) , ( ) , ( ) , ( ) } x1 A = B2 x2 B2 = C1 x3 C1 = D1 x4 D1 = E 即 { } A → B2 → C1 → D1 → E 1 ( ) = 11 —A到E的最短路，路长为 f A 子策略： { } B2 → C1 → D1 → E — B2到E的最短路，路长为 2 ( 2 ) = 7 f B { } C1 → D1 → E — C1到E的最短路，路长为 3 ( 1 ) = 4 f C …… 7 2 #
(数学模型 最优策略有性质一最优化原理: 无论过去的状态和决策如何,对某确定的状态, 余下的决策必须构成最优子策略。 或,对某状态而言,该状态到终点的最优策略 只与后面的选择有关,与前面的选择无关。 或,已知现在,将来与过去无关。 即后部子问题的最优策略是父问题的最优子策略。 #
最优策略有性质—最优化原理： 无论过去的状态和决策如何，对某确定的状态， 余下的决策必须构成最优子策略。 或，对某状态而言，该状态到终点的最优策略 只与后面的选择有关，与前面的选择无关。 或，已知现在，将来与过去无关。 即后部子问题的最优策略是父问题的最优子策略。 8 2 #
(数学模型 利用该原理得寻优方法: 行进方向 问题:A E 寻伏方向 子问题: 将问题化成一系列相互有联系的子问题 先求出“最小子问题”中,各状态到E的最优子策略, 再求出“次小子问题”中(第3阶段),各状态到 E的最优子策略,如此向前推进,而每次都利用后 部子问题中已得到的最优子策略。 如:已得C1到E的最优子策略:C1→>D1→B 在求B2到E的最住走法时,如果该阶段取B2→C1 KAD
利用该原理得寻优方法： 问题： A E 子问题： 行进方向 寻优方向 先求出“最小子问题”中，各状态到E的最优子策略， 将问题化成一系列相互有联系的子问题， 再求出“次小子问题”中（第3阶段），各状态到 E的最优子策略，如此向前推进，而每次都利用后 部子问题中已得到的最优子策略。 如：已得C1到E的最优子策略： { } C1 → D1 → E 在求B2到E的最佳走法时，如果该阶段取 B2 → C1 9 2