|||
P与NP问题的研究进展
姜咏江
自从SAT问题的子句消去法成功之后,我又转向了哈密顿回路的求解研究。我发现图的路径问题,同样可以转化为SAT问题来研究。所谓的哈密顿回路只不过是其SAT表达方式的一组有序全1特解而已。
1. 用数码0和1表示图
在图的路径问题研究中,我发现将图的相邻顶点用数码0和1来表示,既简单,又明确。用1表示当前顶点,所有与之相邻的顶点用0表示。将每个顶点的这种表示做为一个子句,写到SAT表中(见表1和表2),这就是图的01表示法。
例如,将图1(1)和图1(2)用0和1表达,则得到表1和表2的SAT表达式,最上面留出的一行用来标识顶点选取顺序。这种顶点选取顺序清楚地表达出了顶点到顶点间的路径。
从表1和表2都可以看到,01表示的图所成SAT总有全为1的解。因而不难解释哈密顿回路问题是SAT问题解的条件特例。也就是说哈密顿回路的解一定是满足一定关联顺序条件的SAT全1解。
表1 图1(1)的SAT表示 表2 图1(2)的SAT表示
4 | 5 | 1 | 2 | 3 |
|
| 3 | 1 | 2 |
|
x1 | x2 | x3 | x4 | x5 | x1 | x2 | x3 | x4 | x5 | |
1 | 0 |
|
| 0 | 1 |
| 0 |
| 0 | |
0 | 1 | 0 |
|
|
| 1 | 0 | 0 |
| |
| 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 0 | |
|
| 0 | 1 | 0 |
| 0 | 0 | 1 |
| |
0 |
|
| 0 | 1 | 0 |
| 0 |
| 1 |
2. 求图路径的子句消去法
在图的01表示SAT路径问题中,选择某一个顶点,就是将变量的值定为1。因为每个选择的顶点都要设定值为1,选定变量的设定值就可以不写。我们不妨就用变量取值的位置来标注顶点选取的顺序。写上了顺序数,就代表选取了该顶点,没有顺序数的变量,就代表没有被选取。
为了清晰体现子句消去法来求解图的路径,依据子句消去法,我们规定:路径上后面一个顶点确定之后,就将前面顶点的子句消去。
以表1为例。我们选3号顶点为路径起始点。
(1)找到x3值为1的子句(行),通过0值找到与这个顶点相邻的有2、4号顶点。
(2)选择2、4号顶点的一个,并消去x3=1的子句(在此以底纹表示)。这里选的是4号顶点。
(3)依据前面选定的子句,通过子句的0和1关联关系,如(2)去选择关联的顶点,直至不能够再选择为止或到达认定的终点。
不难想象,如果全部顶点都能够被这种依据相邻的关系选中,并且可以确定最后选中的顶点与起始点相邻,那么该图就是一个哈密顿图,所选的闭合路径就是哈密顿回路。在得到哈密顿回路的时侯,SAT的全部子句都会被消去(参考表1和图1(1))。不然,没有哈密顿回路,SAT的子句也不会全部消去(参考表2和图1(2))。
3. 路径边消去法
在图的路径问题研究中,我们可以从某点开始,除去起始点和终点之外,只将前面选择的顶点和关联边留下,其余的边都消去,这样就可以得到需要的路径(见图2和图3)。如果我们要求解的是一条回路,那么起始点也是终点,最后要消去起始点所有未选中的边(见图4)。
很明显,图路径的边消去法,就是图01表示的子句消去法。
4. 求哈密顿回路
依据子句消去法,并依据一定的规则就可以求出哈密顿回路。自然,当一个图不是哈密顿图时,也就求不出哈密顿回路。在客观上,这种方法找到了鉴别一个图是否是哈密顿图的方法。
SAT的子句消去法是一种多项式时间复杂度的算法。图的边消去法求解哈密顿回路,也是一种多项式时间复杂度的算法。
目前,本人对任意给出的图都能够求出是否有哈密顿回路,即可鉴别是否是哈密顿图。只是在理论证明上尚未完成。如有人愿意与本人一同合作研究,可以与我直接联系。
邮箱:accsys@126.com
2016-02-24
Archiver|手机版|科学网 ( 京ICP备07017567号-12 )
GMT+8, 2024-10-19 22:24
Powered by ScienceNet.cn
Copyright © 2007- 中国科学报社