怎样找一条去姥姥家的捷径

放暑假了，赵霞想到姥姥家去度假。赵霞住在赵村，姥姥家在李村，好长一段路呢。从赵村到李村可走的路还真不少，像图1上画出的那样，其中的数字表示以公里为单位的路程。怎样才能找到一条去姥姥家的最短路线呢？

许多人会采取这样的办法：计算出每条路线的路程，加以比较，找出一条距离最短的路线。这种方法称为“穷举法”。

总共有多少条路线呢？到姥姥家去的路，大体上可分成四段，如图2所示。由此可算出不同的路线总共有2×3×3=18条。要找到最短的路线，在计算机上需要进行比较运算17次，加法运算42次。

图1

图2

有没有其他的办法呢？

设想已经找到了一条去姥姥家的最短路线，并且这条路线经过某个村庄，那么从这个村庄继续走下去，也应该是该村庄到姥姥家的最短路线。例如，如果“赵村→孙庄→魏村→周庄→李村”是赵霞去姥姥家的一条最短路线，其中经过魏村，那么这条最短路线自魏村的以后部分“魏村→周庄→李村”也应该是魏村到李村的最短路线。根据这个道理，我们可以得到另一种寻找捷径的方法。

从终点李村开始分析。如果赵霞已到达韩庄，接下去她应怎样走才能使到姥姥家的路程最短？由图1可以看出，从韩庄到李村只有一条路，所以它也是去姥姥家最短的路线，长6公里。同样道理，从杨庄到姥姥家最短的路线长5公里；从周庄到姥姥家最短的路线长3公里。总结一下，即：

韩庄→李村，6公里；

杨庄→李村，5公里；

周庄→李村，3公里。

接下来对第三段路进行分析。如果赵霞已经走到陈村，怎样继续走才能使到达姥姥家的路程最短呢？动手计算一下，陈村→韩庄→李村，8公里；陈村→杨庄→李村，12公里；陈村→周庄→李村，7公里。因此最佳路线是“陈村→周庄→李村”，共7公里。同样道理，从魏村到姥姥家的最短路线是“魏村→周庄→李村”，长6公里。从宋村到姥姥家的最短路线是“宋村→周庄→李村”，长7公里。也列表总结一下，得：

陈村→周庄→李村，7公里；

魏村→周庄→李村，6公里；

宋村→周庄→李村，7公里。

按照上述同样的方法对第二段路进行分析，可得各村到姥姥家的最短路线为：

孙庄→魏村→周庄→李村，9公里；

冯庄→陈村→周庄→李村，9公里。

最后看第一段路。由于从孙庄→李村、冯庄→李村的最短路线都长9公里，因此只要看从赵村到孙庄或冯庄哪条路比较短就行了。经比较，可知赵露去姥姥家的最短路线应是：

赵村→孙庄→魏村→周庄→李村，

总长14公里。

后一种找捷径的方法，在数学中称为“动态规划解法”。“动态规划”是本世纪50年代初形成的一个数学分支，有广泛应用。用这种方法求上例的最短路线，在计算机上需进行比较运算11次，加法运算17次，计算量比穷举法少。

在数学中，图1可看作是一幅交通网络图。在这个交通网络图中，顶点和边的数目比较少，动态规划解法的优越性还不是很明显。如果一幅交通网络图顶点和边的数目都比较大，动态规划解法的优越性就充分显露出来了，而开头介绍的那种解法，将会因计算量过大，有时连大型电子计算机都无法承受，而变得毫无实际意义。

图1可以表示赵霞去探望姥姥的路线图，也可以用来研究从赵村到李村铺设的管道怎样才能最短的问题。在不同问题中，图中的数字可以被赋予时间、费用或其他种种不同的含义。在经济建设中出现的大量的网络图内，一般说来，顶点与边的数目比图1中的要大得多。按动态规划解法编制的求最短路线的计算机程序，至今仍在使用着。