为什么会产生信息“组合爆炸”?
不知你听说过没有,信息急剧增加会产生“爆炸”。这到底 是怎么回事呢?看了下面一个简单的例子,你就会明白了。有一张城市图,售货员必须走遍每一个城市,并且恰好只 走过一次。图中每两个城市之间有一条道路,上面标有两地 间的距离。 现要求为售货员设计一条行走路线,使得从这些城市中任一城市出发,然后回到出发城市,所走的路线最短。这就是有名的“货郎担问题”。要求解该问题似乎是不难的,只要找出图中各种可能的 路径,再进行比较,取最短的那条即可。 如果城市数目少,这个 方法是切实可行的。但城市数目一多,这种方法也就失败了。如城市数为N,则城市间的不同路径为N! (N! = 1 x 2 x 3 x… x...全部
不知你听说过没有,信息急剧增加会产生“爆炸”。这到底 是怎么回事呢?看了下面一个简单的例子,你就会明白了。有一张城市图,售货员必须走遍每一个城市,并且恰好只 走过一次。图中每两个城市之间有一条道路,上面标有两地 间的距离。
现要求为售货员设计一条行走路线,使得从这些城市中任一城市出发,然后回到出发城市,所走的路线最短。这就是有名的“货郎担问题”。要求解该问题似乎是不难的,只要找出图中各种可能的 路径,再进行比较,取最短的那条即可。
如果城市数目少,这个 方法是切实可行的。但城市数目一多,这种方法也就失败了。如城市数为N,则城市间的不同路径为N! (N! = 1 x 2 x 3 x… x N)条。如果计算一条路径的长度花去的时间总量为0。
1微 秒(10-7秒),则计算出所有路径的长度花去的时间总量为N! x 0。 1微秒。在现实事务中,要求售货员访问24个城市也不 算什么稀奇的事,但24!已经大得出奇了。计算出24个城市 之间的所有路径长度花去的时间总量为24! x0。
1微秒(即 6。 204484017 x 1022微秒,约19。 6亿年)。此时,如N增加1,即 24加1变成25,则所花的时间就扩大了 25倍,即为25! x 0。 1微秒(约490。 5亿年)。
N增加1,则所花时间总量就扩大(N +1)倍,这种增长速度之快是令人难以想象的。这种现象就是所谓的“组合爆炸”问题。还有一类问题叫博弈问题。如人和计算机下棋,为了保证最后取胜,计算机可以将所有可能的走法都试一下,然后选择取胜的走法。
每试一步走法就有一种棋局,而棋局的数目是非 常大的。例如,国际象棋不同的棋局数为101'围棋不同的棋 局数为10761。找到所有可能的走法都试一下,然后选择“最佳方案”是 可以做得到的,但这样做所花费的时间和存储空间是十分惊人的。
以目前计算机的能力来解上述“难”题是不可能的,因为任何一台计算机的存储器容量总是有限的,不可能有无限大的容量。任何一台计算机的每一个动作,都需要一定的时间来完成。为了便于理解,我们就从计算机下棋的时间耗费来考虑“组合爆炸”问题。
目前计算机的运算速度可达每秒1亿条指令,用最优方法设计程序,每走一步需执行10条指令,这样,每走一步需要 的时间是0。1微秒。计算机实际可达到的速度估计为2毫 秒/步(1毫秒=10_3秒)。串行计算机理论速度极限为10-12 毫秒/步,而并行计算机理论速度极限为KT11毫秒/步或 10-104 年/步。
即使用并行计算机的理论极限速度计算,求解国际象棋的完备算法也要1亿亿(1016)年才可以算完。可我们已知的宇宙史才150亿年。收起