|||
姜咏江
什么是限位数?就是数码位数一定的数。以往人们并没有注意对限位数的研究,是因为人们极少用到它。现在人们用电脑了,用电脑要解决问题,在设计上就不得不考虑位数一定的数,而且要考虑怎样用位数一定的数来表达实数。当然这个问题首先是计算机设计专家碰到的问题。在计算机中只有不带符号的二进制整数,而且是限定了位数的32位、64位或128位等。人们不可能造出位数无限长的计算机,因而用限位数来表示和运算来解决实数的运算问题,是首先要解决的问题。实际上这个问题已经基本上解决了。解决最彻底是我在十多年前完成的限位数理论和方法,在计算机算术运算器的设计中有着根本性的作用。不管人们是否认可,它就放在那里。
这两年多,我研究SAT问题多项式时间复杂度算法,对限位数的使用又有了新的发现。如果把过去研究限位数看作只是一维的研究方法,那么针对SAT问题,已经进入了二维空间的研究。毫无疑问,这种研究为破解难题SAT问题,找到了坚实的理论基础,为那些需要整体结构分析才能够解决的难题,打开了一扇大门。
关于限位数在数值计算当中的基本原理,我在《自己设计制作CPU与单片机》一书中已经介绍。对于限位数二维空间的特点,本文就做一点简单的介绍,目的是让人们能够理解SAT问题如何利用子句消去法完成计算求解。
为了简单,仅就二进制限位数的一些基本性质述说。
k位二进制数最多有2k个,叫全块。
k位二进制数全体,每位0和1都有2k-1个。
将数码0和1互换得到的数叫反码数。每一个限位数都有唯一反码数。
反码数之间每位数码都不同,非反码数之间至少有一位数码相同。
限位数在子句消去法中的应用:
SAT问题可以用0和1表示成一张表。表中的每一行就是一个限位数,叫子句。
x1 | x2 | x3 |
0 | 0 | 0 |
0 | 0 | 1 |
0 | 1 | 0 |
0 | 1 | 1 |
1 | 0 | 0 |
1 | 0 | 1 |
1 | 1 | 1 |
1 | 1 | 1 |
如果我们将变量的值设定为0,那么这一列每个为0的子句的值就是1。按照逻辑运算的法则,就不影响对其余子句是否值为1的判断,因而可以消去。上表是全块,不论如何设定变量的值,都不可能让全部子句值为1,一定会有子句剩下。显然,不是全块,就可能设定变量值将全部子句消去。只要非全块中有一个变量有2k-1个0或1,那么这个变量就有唯一解。用这种全局结构的判断就可以逐步地求出SAT的解,而无需考虑多次猜测性的重来。
当变量同时在不同的子句块中出现时,要比单一子句块复杂,但用上面限位数的性质,就可以找到那些只有唯一值的变量,通过这些变量的值确定,最终可达到求出SAT的解。当然,如果SAT本身就无解,子句消去法在求解的过程中,可发现无解的全块和有唯一解的矛盾的情况。
二维的限位数值得我们深入地进行研究。目前在解决SAT问题满足解中只是露出了头角而已。
2016-12-19
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-11-14 13:51
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社