6.1.2最短路线问题 最短路线问题就是说给定了初始点及终点以及由始点到终点的各种可能途径,要求 寻找一条由始点到终点的最短路线。对于不同的实际问题也就是求距离(或时间、运输 费用)的最小值。 例6.1图6-2是一个示意图,表示由始点A到终点E的网络路线。图中A,B1, B2…表示各个地点,线段表示各个地点之间的交通路线,线段上的数字表示各个地点 之间的距离(或时间、费用)。要求选择一条从A到E距离最短的路线(或时间、费用 最少)。这是一个多阶段决策问题 求解这个问题可采用穷举法。就是列出 从A点到E点的所有路线,然后计算每 SC 条路线的距离(或时间、费用),再进行 比较,找出距离最短(或时间,费用最 少)的路线,则最优解便找到了。此法 称为枚举法或穷举法。本例从A点到E 1中23-|4-|点共有11条不同路线,比较它们的长 图6-2 度,最短路线为 A→B,→>C 其距离为14。但这样的计算相当冗繁,特别是网络路线比较复杂时,用穷举法计算 甚至无法实现。下面采用动态规划方法求解此例。该法是求解这类最短路线(或最长路 线)的最有效的方法之 用动态规划方法求解时,根据最优化原则导致最短路线问题应具有这种特性,就是: 如果最短路线通过点P,则这条最短路线从P点到终点的部分,对于从P点到终点的所 有路线(称为P的后部路线)而言,必然也是最短的线路(P的最短后部路线)。例如本例 中最短路线通过B2,C2,D2,则路线C2→D2→E就是C2到终点E所有路线中最短 的一条。最短路线所具有的这个特性不难理解,用反证法,若从P点至终点还有另一条 更短的路线存在,把这条更短的路线与原最短路线从起始点到P点的那部分路线连接起 来,就会形成一条比原来由始点到终点的最短路线还要短的路线,这是不可能的 现在我们利用这种特性把整个问题按空间关系,即把从A到E的网络路线划分为几 个阶段,然后接逆序从最后一段开始向最初阶段递推,做出各阶段中各点的最优决策即 寻找某阶段各点到终点E的最短路线上,在下一阶段应经过的点O则各点到终点E的最 短(后部)路线可同时确定,最后便得到起点A到终点E的最短路线。因此,动态规划方 法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下:6.1.2 最短路线问题 最短路线问题就是说给定了初始点及终点以及由始点到终点的各种可能途径，要求 寻找一条由始点到终点的最短路线。对于不同的实际问题也就是求距离（或时间、运输 费用）的最小值。 例 6.1 图 6-2 是一个示意图，表示由始点 A到终点 E 的网络路线。图中 ， ， ……表示各个地点，线段表示各个地点之间的交通路线，线段上的数字表示各个地点 之间的距离（或时间、费用）。要求选择一条从 到 A B1 B2 A E 距离最短的路线（或时间、费用 最少）。这是一个多阶段决策问题。 6 3 C1 A 4 2 6 6 7 5 8 9 1 3 2 5 1 3 B1 D1 E B2 C2 D2 C3 1 2 3 4 图 6-2 求解这个问题可采用穷举法。就是列出 从 A点到 E 点的所有路线，然后计算每 条路线的距离(或时间、费用)，再进行 比较，找出距离最短(或时间，费用最 少)的路线，则最优解便找到了。此法 称为枚举法或穷举法。本例从 A点到 E 点共有 11 条不同路线，比较它们的长 度，最短路线为： A → B2 → C2 → D2 → E 其距离为 14。但这样的计算相当冗繁，特别是网络路线比较复杂时，用穷举法计算 甚至无法实现。下面采用动态规划方法求解此例。该法是求解这类最短路线(或最长路 线)的最有效的方法之一。 用动态规划方法求解时，根据最优化原则导致最短路线问题应具有这种特性，就是： 如果最短路线通过点 P ，则这条最短路线从 P 点到终点的部分，对于从 P 点到终点的所 有路线(称为 P 的后部路线)而言，必然也是最短的线路( P 的最短后部路线)。例如本例 中最短路线通过 B2，C2 ， D2 ，则路线C2 → D2 → E 就是C2 到终点 E 所有路线中最短 的一条。最短路线所具有的这个特性不难理解，用反证法，若从 P 点至终点还有另一条 更短的路线存在，把这条更短的路线与原最短路线从起始点到 P 点的那部分路线连接起 来，就会形成一条比原来由始点到终点的最短路线还要短的路线，这是不可能的。 现在我们利用这种特性把整个问题按空间关系，即把从 A到 E 的网络路线划分为几 个阶段，然后接逆序从最后一段开始向最初阶段递推，做出各阶段中各点的最优决策即 寻找某阶段各点到终点 E 的最短路线上，在下一阶段应经过的点O则各点到终点 E 的最 短(后部)路线可同时确定，最后便得到起点 A到终点 E 的最短路线。因此，动态规划方 法就是从终点逐段向始点方向寻找最短路线的方法。解题步骤如下：