A市到E市的公路网如图所示。现有一批货物需要从A市运到E市，图中的节点B1、B2、C1……、代表可以经过的县市站点，箭头表示两点间是连通的；线上的数字表示两点间的运输代价。运输代价可以是时间、距离或时间与距离的加权平均。现在要确定从A市到E市的最佳运输路线，使运输成本最低。
首先，根据网络结构特征将整个决策问题划分成4个阶段。决策过程按从终点到起点的逆序进行，因此决策阶段编号是按逆序进行的。
其次，按照逆序法对每个阶段的决策问题求解，依次从每个阶段的可选状态中选择一个到终点最短的状态。
具体决策过程如下。
1、第1阶段的决策：有两个可选状态D1和D2，到终点的距离分别是5和2。
2、第2阶段的决策，从C1、C2、C3三个备选状态中选择一个点，使其经过D1到达E的距离最短，决策结果是C1点，到E点的最短距离=8。再从中选择1个点，使其经过D2到达E的距离最短，这时的决策点是C2点，最短距离=7。
3、第3阶段的决策：分别从B1、B2、B3中选择一个点，使其经过C1、或C2、或C3到达E点的距离最短。可能的部分最短路径是B2—C1、B2—C2、B2—C3，对应的最短距离分别是14、17、16，即这一阶段的决策点都是B2。
4、第4阶段的决策：选择A点，使A经过B1、或B2点到达E的总距离最短，结果是A—B2，距离=5+14=19。
每个节点上面的数字（方框中）表示该点到终点E的最短距离，决策的过程可用表1说明。
表1
最后，按顺序从阶段4到阶段1，就可得到从结点A到结点E的最短路径，A—B2—C1—D1—E，最短距离为（5+6+3+5）=19。
应用动态规划法求解运输最短路径问题的基本条件是，必须能将一个具体的路径优化问题转化成多个决策阶段问题，且这种阶段划分必须明确、易识别且满足无后效应。
网友评论