3.1.1　由算例看动态规划

3.1.1　由算例看动态规划

下面先通过一个例题来引出动态规划问题。

图3.1　由地下水库A到城市B可能的输水路线图

【例3.1】有一个地下水库A，需引水至B 城，供水管路要经过E、F、G 3个地点，且每个地点又有2个可供选择的方案，管路可能经过的线路及各路段的输水费用如图3.1 所示，试选择一条输水费用最小的线路。

该问题共8（23=8）个可选路线，采用枚举法可求解如图3.2所示。

图3.2　应用枚举法求解[例3.1]

枚举法也叫穷举法，就是把所有的方法列举出来，逐一计算比较，然后选出最优的方案。对于简单问题，枚举法比较有效。对于复杂问题，列出所有的可能方案本身就不容易，即便所有的方案数量已知，列举的过程中难免会有没注意到的重复方案，这样就可能遗漏也可能是最优的方案。

有了动态规划方法后，求解类似上面的问题，就变得比较简单科学。图3.3是采用动态规划标号法[《运筹学》教材编写组（钱颂迪等），2013]逆序求解[例3.1]的结果。(https://www.daowen.com)

标号法求解过程是逆序求解，从第四阶段逆向求解到第一阶段。

上图中，G1可以到达终点B，且只有这一条路线，最优值为5（G1到B的最小费用路线），将数值5 标记在G1点上（标号），数值5表示从G1到B的最小路线费用。同时将G1与B 连线加粗或标红，加粗或标红的这段线就表示从B到G1的局部最优路线。G2也类似求出并标记。

继续逆序求解，从F1可以到G1（G1到B 就不再考虑了），从F1也可以到G2（G2到B也不用再考虑了），比较前面的局部解，显然7是最小值，将数值7标在F1点上，同时局部路线F1到G1加粗或标红。数值7表示从F1到B的局部最优值，能连到B加粗或标红的线就是F1到B的局部最优路线。F2求解类似。

这样每一步求出的值就是从该点到末端的局部最优值，能连到末端的加粗或标红线就是局部最优路线。

图3.3　标号法求解[例3.1]结果

按此方法求解到起点，最后的标号值18就是全局最优值，能连到末端加粗或标红的路线就是全局最优路线（A-E2-F1-G1-B）。本题由于方向是自己规定的，可以逆向也可以正向求解。

标号法求解过程虽然简单，但求解过程体现的却是动态规划的基本方法——逆序逐步寻优。