为什么会产生信息“组合爆炸”

不知你听说过没有，信息急剧增加会产生“爆炸”。这到底是怎么回事呢？看了下面一个简单的例子，你就会明白了。

有一张城市图，售货员必须走遍每一个城市，并且恰好只走过一次。图中每两个城市之间有一条道路，上面标有两地之间的距离。现要求为售货员设计一条行走路线，使得从这些城市中任一城市出发，然后回到出发城市，所走的路线最短。这就是有名的“货郎担问题”。

要求解该问题似乎是不难的，只要找出图中各种可能的路径，再进行比较，取最短的那条即可。如果城市数目少，这个方法是切实可行的。但城市数目一多，这种方法也就失败了。如城市数为N，则城市间的不同路径为N！（N！=l×2×3×…×N）条。如果计算一条路径的长度花去的时间总量为0.1微秒（10^-7秒），则计算出所有路径的长度花去的时间总量为N！×0.l微秒。在现实事务中，要求售货员访问24个城市也不算什么稀奇的事，但24！已经大得出奇了。计算出24个城市之间的所有路径长度花去的时间总量为24！×0.1微秒（即6.204484017×10²²微秒，约19.6亿年）。此时，如N增加1，即24加1变成25，则所花的时间就扩大了25倍，即为25！×0.1微秒（约490.5亿年）。N增加1，则所花时间总量就扩大（N+1）倍，这种增长速度之快是令人难以想象的。这种现象就是所谓的“组合爆炸”问题。

还有一类问题叫博弈问题。如人和计算机下棋，为了保证最后取胜，计算机可以将所有可能的走法都试一下，然后选择取胜的走法。每试一步走法就有一种棋局，而棋局的数目是非常大的。例如，国际象棋不同的棋局数为10¹²⁰，围棋不同的棋局数为10⁷⁶¹。

找到所有可能的走法都试一下，然后选择“最佳方案”是可以做得到的，但这样做所花费的时间和存储空间是十分惊人的。以目前计算机的能力来解上述“难”题是不可能的，因为任何一台计算机的存储器容量总是有限的，不可能有无限大的容量。任何一台计算机的每一个动作，都需要一定的时间来完成。

为了便于理解，我们就从计算机下棋的时间耗费来考虑“组合爆炸”问题。

目前计算机的运算速度可达每秒1亿条指令，用最优方法设计程序，每走一步需执行10条指令，这样，每走一步需要的时间是0.1微秒。计算机实际可达到的速度估计为2毫秒/步（1毫秒=10^-3秒）。串行计算机理论速度极限为10^-12毫秒/步，而并行计算机理论速度极限为10^-11毫秒/步或10^-104年/步。

即使用并行计算机的理论极限速度计算，求解国际象棋的完备算法也要1亿亿（10¹⁶）年才可以算完。可我们已知的宇宙史才150亿年。

关键词：信息组合爆炸 货郎担问题 时间耗费