1.4　找到金券

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

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

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

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