怎样寻找最短路径

现实生活中，我们经常会碰到这样的问题，如图所示，从A点到E点，怎样走路线最短呢？图上各个结点表示地点，线段表示相应两点之间的道路，线上的数字表示相应的距离。

先考虑穷举法，即把所有的可能路线一一列出，分别算出距离，加以比较，从中选出最短路线。从A到E共有3×3×3×1=27条路线，每条路线要做3次加法，共需81次加法。另外还要作26次比较运算。最后得到最短路线：A→B₂→C₂→D₃→E，相应距离为15。

可以看出，穷举法想起来简单，但实现却很难，特别是当地点多、道路多时，计算量将十分庞大。

有没有其他的方法呢？

可以理解，如果某条路是从A到E的最短路线，则其子路也必是最短的。即如果例题中最短路线为A→B₂→C₂→D₃→E，那么C₂→D₃→E，必是从C₂到E的最短路线。否则用反证法，必可找到一条更短的路线，就与前面矛盾了。最短路线的上述特性，启发我们从终点开始，从后向前逐步递推，求出各点到E的最短子路，最后求出从A到E的最短路线。

第一步，从D到E的最短路线：

由D₁、D₂、D₃到E都只有一条路线，故易得f（D₁）=5，f（D₂）=8，f（D₃）=l。f（x_i）表示从x_i点到E点的最短距离。

第二步，从C到E的最短路线：

从C₁出发，有三个选择，到D₁、D₂或D₃，易求得

其中d（C₁，D₁）表示点C₁到D₁的距离。容易看出最短子路线是：C₁→D₃→E。

同理，从C₂出发，

最短路线是：C₂→D₃→E。

从C₃出发，最短子路线是C₃→D₃→E，f（C₃）=6。

同理，可得f（B₁）=12，子路线是B₁→C₂→D₃→E；f（B₂）=7，子路线是B₂→C₂→D₃→E；f（B₃）=13，子路线是B₁→C₁（或C₂）→D3→E。

最后，从A出发，

最短路线是:A→B₂→C₂→D₂→E，距离为15。

从计算过程可以看出，计算量大大减少，只需3×3+3×3+3=21次加法，3×2+3×2+2=14次比较。地点越多、路线越多，这一优点越是明显。同时，用这种方法不仅能够得到从起点A到终点E的最短路线，而且可以知道每个点到终点的最短路线。这种方法在数学上称为“动态规划解法”。

“动态规划”是解决多阶段决策过程最优化问题的一种方法，是由美国数学家R.Bellman等人1951年提出的解决这类问题的“最优化原理”发展形成的一个数学分支。动态规划的方法在工程技术、经济管理、工业生产和军事等方面都有着广泛的应用，并且日益受到重视，甚至还用在计算机程序中，因为有些复杂问题，如果用穷举法，即使是计算机，也难以承受其计算量。

关键词：穷举法 动态规划