CMP设计分享 http://blog.sciencenet.cn/u/accsys 没有逆向思维就没有科技原创。 不自信是科技创新的大敌。

博文

限位数——一个人们不曾研究的领域

已有 2659 次阅读 2016-12-19 09:03 |个人分类:离散数学|系统分类:科研笔记| 离散数学, 限位数, SAT问题


姜咏江


什么是限位数?就是数码位数一定的数。以往人们并没有注意对限位数的研究,是因为人们极少用到它。现在人们用电脑了,用电脑要解决问题,在设计上就不得不考虑位数一定的数,而且要考虑怎样用位数一定的数来表达实数。当然这个问题首先是计算机设计专家碰到的问题。在计算机中只有不带符号的二进制整数,而且是限定了位数的32位、64位或128位等。人们不可能造出位数无限长的计算机,因而用限位数来表示和运算来解决实数的运算问题,是首先要解决的问题。实际上这个问题已经基本上解决了。解决最彻底是我在十多年前完成的限位数理论和方法,在计算机算术运算器的设计中有着根本性的作用。不管人们是否认可,它就放在那里。

这两年多,我研究SAT问题多项式时间复杂度算法,对限位数的使用又有了新的发现。如果把过去研究限位数看作只是一维的研究方法,那么针对SAT问题,已经进入了二维空间的研究。毫无疑问,这种研究为破解难题SAT问题,找到了坚实的理论基础,为那些需要整体结构分析才能够解决的难题,打开了一扇大门。

关于限位数在数值计算当中的基本原理,我在《自己设计制作CPU与单片机》一书中已经介绍。对于限位数二维空间的特点,本文就做一点简单的介绍,目的是让人们能够理解SAT问题如何利用子句消去法完成计算求解。

为了简单,仅就二进制限位数的一些基本性质述说。

  1. k位二进制数最多有2k个,叫全块。

  2. k位二进制数全体,每位01都有2k-1个。

  3. 将数码01互换得到的数叫反码数。每一个限位数都有唯一反码数。

  4. 反码数之间每位数码都不同,非反码数之间至少有一位数码相同。


    限位数在子句消去法中的应用:

    SAT问题可以用01表示成一张表。表中的每一行就是一个限位数,叫子句。

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









https://blog.sciencenet.cn/blog-340399-1021656.html

上一篇:SAT问题基本定义和术语
下一篇:简单求3-SAT解DPLL方法与子句消去法比较
收藏 IP: 1.180.215.*| 热度|

0

该博文允许注册用户评论 请点击登录 评论 (1 个评论)

数据加载中...
扫一扫,分享此博文

Archiver|手机版|科学网 ( 京ICP备07017567号-12 )

GMT+8, 2024-11-14 13:51

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部