正文

为什么有些问题不能解决?

(2022-10-15 13:55:30) 下一个

为什么有些问题不能解决?(1) 一些问题没有解决的方法(算法);(2) 一些问题有解
决的方法(算法),但随着问题的尺度的增加,无法算下去。

第一类问题中典型的例子是图灵(TURING)停止问题:是否存在一个程序,它可以用
来判断另一个程序是死循环(不停地运行)或停止。一般来说,这样的程序是不存在
的。如果存在这样的程序H,它可以用来判断另一个程序P,H(P):H将P作为输入。
我们可以根据H(P)的判断结果来设计另一个程序G(H(P)):当H(P)认为P是死循环时,
G停止;当H(P)认为P是停止时,G死循环。SO FAR,SO GOOD。但当我们用G来代替P,
即用上述程序来判断程序G,G(H(G)),我们就进入悖论怪圈。里面的G是死循环,外
面的G是停止;里面的G是停止,外面的G是死循环。实际上里面的G和外面的G是同一
个G。所以,一般来说,程序H是不存在的。在计算机理论中,常有一些递归不能解
决问题。所谓“递归”是指“对自己”,即一些算法“对自己”不灵,“对别人”
可以。

这一类问题还有很多,比较著名的是贴砖(TILING)问题。给出一组有限种类的砖(数
量是无限),问是否存在一个算法,它能确定是否这些砖能铺满座标系的第一象限。
贴砖时,砖子不能旋转,砖子之间还得符合邻接条件。贴砖的程序可以转换为图灵
机程序。于是贴砖问题就转换为图灵停止问题。因此这样的算法是不存在。

第二类问题也有很多,现举一个旅行商问题。旅行商问题:有N个城市,一个推销员
要从某一个城市出发,走遍所有的城市(一个城市只能去一次),再回到他出发的城
市,求长度小于或等于K的路线。这个问题属于NP问题,即非确定性多项式时间问题。
所谓NP问题是指,有一个非确定型计算机,它可以得到问题的解,而且每一步程序
都是正确的;(实际上,世界上还没有这种计算机) 然后只需用多项式时间来证实这
个问题的解。对于旅行商问题,非确定型计算机已经得到它的解,证实这个解实际
上只需多项式时间。当然,用确定型计算机求解这个问题,就需要(N-1)阶乘时间,
因此当N很大时,无法算下去。对于旅行商问题,如果我们要证实没有长度小于或等
于K的路线,这就不是NP问题,因为我们要枚举所有的情况。这时,这个问题属于CO-NP问题。

在研究工作中,我们经常碰到这样的情况,当问题的尺度比较小时,理论很优美,
计算也简单;当问题的尺度比较大时,就无法搞下去。

[ 打印 ]
阅读 ()评论 (0)
评论
目前还没有任何评论
登录后才可评论.