1.4 找到金券

有时候我们能够找到金券。比如我在芝加哥,想开车去纽约,往车载GPS里输入地址,一两分钟之内它就能给出一条从芝加哥到纽约的最快路线,然后我就可以踏上旅程了。几百万字节的内存便可容纳全部的美国街道地图,但地图中可能的路线远远超过几百万。从芝加哥到纽约所有可能的行车路线有多少条?不开错方向的情况下,保守计算可得出的路线数目大到了“不可思议”,即1后边跟63个0。GPS根本没有时间检查所有的可能性,但还是能找到最快的路线。

旅行时间有一个有趣的性质。随便选一个中间地点(比如匹兹堡),从芝加哥经过匹兹堡到纽约的最短路线,一定是芝加哥到匹兹堡的最短路线,再接上匹兹堡到纽约的最短路线。不走匹兹堡可能有更快的路线,但是芝加哥到纽约的最短路线,绝不会比从芝加哥经过匹兹堡到纽约的最短路线还要长。

GPS的计算机程序正是利用了这个性质,快速缩小搜索范围并找到了最佳路线。这可能仍需要检查上亿条路线,但是GPS的计算机处理器完全能胜任,毕竟这个数字比“不可思议”小多了。

找到最短路径并没有体现P/NP问题的全部力量。最短路径问题告诉我们,全部的可能性数量特别大,但这并不总意味着必须遍历所有的可能性才能找到答案。P/NP问题其实是问,是不是对于任意给定的搜索问题,我们都不必遍历所有的可能性就能找到答案?

目录