计算机导论中超越双曲函数问题的可解性

2023-11-18 理论教育版权反馈

【摘要】：在6.1节定义算法时指出，算法必须具备可终止性，算法的可终止性是指算法应能在有限的操作步骤后结束。图6-8 汉诺塔问题的求解示意图这样的问题求解算法可以设计成一个递归结构的算法。在算法分析中，把存在时间效率为多项式函数算法的问题称作可解的问题，把只存在时间效率等于或大于指数函数算法的问题称作难解的问题。寻求所有目前认为是难解的问题的多项式函数的算法，一直是计算机科学领域非常重要的研究课题。

在6.1节定义算法时指出，算法必须具备可终止性，算法的可终止性是指算法应能在有限的操作步骤后结束。有些算法虽然理论上可以在有限的操作步骤后结束，但实际上这样的“有限的操作步骤”是不能接受的。

【例6-5】设计汉诺塔问题的算法，并分析该算法的时间效率。汉诺塔问题的描述是：设有3根标号为A，B，C的柱子，在A柱上放着n个盘子，每一个都比下面的略小一点，要求把A柱上的盘子全部移到C柱上，移动的规则是：（1）一次只能移动一个盘子；（2）移动过程中大盘子不能放在小盘子上面；（3）在移动过程中盘子可以放在A，B，C的任意一个柱子上。

算法设计：当圆盘个数n等于1时，可以直接把该圆盘从A柱移到C柱；当n等于2时，可以先把上面的圆盘从A柱临时移到B柱，然后把下面的圆盘从A柱移到C柱，最后再把B柱上临时存放的圆盘移到C柱；当n等于3时，首先可以用类似n等于2时的方法，借助C柱，把上面的2个圆盘从A柱移到B柱，然后把最下面的一个圆盘从A柱移到C柱，最后再用类似n等于2时的方法，借助C柱，把B柱上临时存放的2个圆盘移到C柱；当n等于4时，首先可以用类似n等于3时的方法，借助C柱，把上面的3个圆盘从A柱移到B柱，然后把最下面的一个圆盘从A柱移到C柱，最后再用类似n等于3时的方法，借助C柱，把B柱上临时存放的3个圆盘移到C柱。

因此，对于个数为n的圆盘，可以先把上面的n－1个圆盘用类似前面的方法从A柱移到B柱，然后把最下面的一个圆盘从A柱移到C柱，最后再把B柱上临时存放的n－1个圆盘用类似前面的方法移到C柱。n个圆盘汉诺塔问题的求解示意图如图6-8所示。

图6-8 汉诺塔问题的求解示意图

这样的问题求解算法可以设计成一个递归结构的算法。如图6-8所示，求解n个圆盘的汉诺塔问题的算法为：

（1）递归调用n－1个圆盘的汉诺塔问题算法，把上面的n－1个圆盘从A柱移到B柱。

（2）把最下面的一个圆盘从A柱直接移到C柱。

（3）递归调用n－1个圆盘的汉诺塔问题算法，把B柱上临时存放的n－1个圆盘移到C柱。

算法分析：当圆盘个数n等于1时，只需移动一次圆盘；当n等于2时，需要移动3次圆盘；当n等于3时，需要移动7次圆盘；当n等于4时，需要移动15次圆盘；当n等于5时，需要移动31次圆盘；⋯⋯。可见，移动圆盘的次数和圆盘个数n的关系是：当n等于1时，移动圆盘的次数为21－1＝1；当n等于2时，移动圆盘的次数为22－1＝3；当n等于3时，移动圆盘的次数为23－1＝7；当n等于4时，移动圆盘的次数为24－1＝15；当n等于5时，移动圆盘的次数为25－1＝31；当圆盘个数为n时，移动圆盘的次数为2n－1。也就是说，该算法的时间效率为O（2n）。(www.chuimin.cn)

由于汉诺塔问题要求给出每次移动的过程，所以不可能再有其他的求解算法，其时间效率优于O（2n）。

上面我们设计了汉诺塔问题的算法，并分析了该算法的时间效率为O（2n）。现在我们来讨论一个算法的时间效率为O（2n）意味着什么。

对于汉诺塔问题，假设算法中每次移动圆盘（在计算机中用数值模拟移动）需要耗时10-4秒（万分之一秒），则当n等于100时，运行该算法需要耗时10﹣4×（2100－1）秒≈1.3×1026秒≈2.16×1024分≈3.56×1022时≈1.48×1021天≈4×1018年。我们知道，4×1018年是一个非常大的天文数字。可见，随着要处理的数据个数n的增大，函数2n以翻倍的方式迅速增大。因此，对于一个时间效率为O（2n）的算法来说，当数据个数n比较大时，虽然理论上它是可以计算出结果的，但实际上这个结果却是不可能得到的。

在算法分析中，把存在时间效率为多项式函数算法的问题称作可解的问题，把只存在时间效率等于或大于指数函数算法的问题称作难解的问题。

时间效率最好的算法是常数数量级的算法。常数数量级算法的运行时间是一个常数，其时间不随所处理的数据个数n增大而增长。或者说，常数数量级的算法和所处理的数据个数n无关。常数数量级的算法表示为O（c），其中c表示任意常数。

多项式函数的时间效率有O（n），O（n2），O（n3），O（n4）等等，以及数量级介于上述数量级之间的O（lb n），O（nlb n），O（n2lb n）等等。对大多数应用问题来说，时间效率为多项式函数的算法，即使所处理的数据个数n比较大，计算机运行所耗费的时间也是可以接受的。就是像时间效率为O（n5），O（n6）等的算法，当所处理的数据个数n比较大时，现在的计算机处理比较费时，但随着计算机运行速度的飞速提高，很快也就不存在太大的问题了。例如，当n等于1000000时，某个时间效率为O（n5）的复杂问题的求解算法运行耗时为10天，当计算机的运行速度在3年内提高了1个数量级后，同样的算法运行只需耗时1天。

但是，对时间效率为指数数量级的O（2n）算法，以及数量级等同于O（2n）的O（n！）算法，或数量级非常之高的O（nn）等算法来说，当所处理的数据个数n比较大时，用现在的计算机处理无法得到结果，即使计算机的运行速度提高了很多，仍然无法在可接受的时间内得到处理结果。例如，对于例6-5的时间效率为O（2n）的汉诺塔问题算法来说，当n等于30时，目前的计算机运行耗时为10﹣4×（230－1）秒≈10﹣4×108秒＝104秒。当计算机的运行速度在3年内提高了1个数量级后，在104秒的时间内所能处理的数据个数n也仅为33个左右，并没有较大的增长。

寻求所有目前认为是难解的问题的多项式函数的算法，一直是计算机科学领域非常重要的研究课题。虽然这方面的研究取得了许多进展，但突破性的重大进展仍然还只是计算机科学界的一种渴求。

计算机导论中超越双曲函数问题的可解性

相关推荐