第
7
卷第
3
期
2012
年
6
月
智能系统学报
CAAI Transactions on Intelligent Systems
DOI:
10.
3969/j.
issn.
16734785.201109003
网络出版地址
:http://
飞仰
w.
cnki.
ne
t/
kcms/detai
Il
23.
1538.
TP.
20120510.1619.001.
html
最坏情况下
Min-2SAT
问题的上界
谷文祥
1
气姜蕴晖周俊萍殷明浩
l
Vo
l.
7
No.
3
Jun.2012
(1.东北师范大学计算机科学与信息技术学院，吉林长春
130117;
2.
长春建筑学院基础教学部，吉林长春
130607)
摘
要:最坏情况下
MaxSAT
问题上界的研究已成为二个热门的研究领域.与
MaxSAT
问题相对的是
MinSAT
问题，
在求解某些组合优化问题时，将其转化为
MinSAT
问题比转化为
MaxSAT
问题有着更快的速度，因此对
MinSAT
问题
进行研究.针对
Min-2SAT
问题提出算法
MinSATAlg
，该算法首先利用化简算法
Simplify
对公式进行化筒，然后通过分
支树的方法对不同情况的子句进行分支.从子句数目的角度分析算法的时间复杂度并证明
Min-2SAT
问题可在
0(
1.
1343
m
)
时间内求解，对于每个变量至多出现在
3
个
2-
子句中的情况，得到最坏情况下的上界为
0(
1.
122
5
勺，
其中
n
为变量的数目.
关键词:
MaxSAT;
MinSAT;
Min-2SAT;
MaxSAT
问题的上界;
Min-2SAT
问题的上界;子句数目;分支树
中图分类号
:T
P3
01
文献标志码
:A
文章编号:
16734785 (2012)
03
-0
241
-0
5
New worst-case
upper
bounds
for
Min-2SAT problems
GU
Wenxiang
,,2 ,
JIANG
Yunhui'
,
ZHOU
Junping'
,
YIN
Minghao'
(1.
School
of
Computer
Science
and
Information
Technology
,
Northeast
Normal
University
,
Changchun
130117
, China; 2.
Department
of
Basic
Subjects
Teaching ,
Changchun
Architecture &
Civil
Engineering
College
,
Changchun
130607
, China)
Abstract
:
The
rigorous theoretical analyses of algorithms for solving the
upper
bounds of maximum satisfiability
(MaxSAT)
problems have
been
proposed in research literature.
The
opposite problem
of
MaxSAT is
the
minimum
satisfiability
(MinSAT)
problem. Solving some combinatorial optimization problems by reducing them to MinSAT
form may
be
substantially faster than
reducing
them to MaxSAT fonn , so the MinSAT problem was
researched
in
this
pape
r. An algorithm (MinSATAIg) was presented for the minimum two-satisfiability
(Min-2SAT)
problem.
In
this
paper
, first , the simplification algorithm Simplify was
used
for simplification of fonnulas. Secondly, the
branching
tree method was
used
for
branching
on different kinds
of
clauses. It was proven that this algorithm
can
solve the Min-2SAT problem in 0 (1. 134 3
m
)
, regarding the
number
of clauses as parameters. The
upper
bound
in
the
worst
case
was derived as
O(
1.
122
sn) , where n is the
number
of variables
in
an
input
fonnula for a particu-
lar
case
of
Min-2SAT
in
which
each
variable appears in three
2-clauses
at most.
Keywords
: maximum satisfiability; minimum satisfiability; minimum two-satisfiability;
upper
bounds for maximum
satisfiability;
upper
bounds for minimum two-satisfiability;
number
of
clauses;
branching
tree
人工智能研究领域存在着很多计算困难的问
题，如
SAT(
satisfiability)
问题、
QBF(
quantified boole-
an
fonnula)
问题、智能规划问题、模型诊断问题等.
若
P
乒
NP
成立，人们将无法为这些问题找到多项式
收稿曰期
:20
Il-D
9
-D
6
网络出版日期
:2012
-D
5-
1O
基金项目:国家自然科学基金资助项目
(61070084)
;国家自然科学青
年基金资助项目(
60803102)
;中央高校基本科研业务费专
项资金资助项目
(11QNJJ006)
.
通信作者:姜蕴晖
E-mail:
jiangy
h2
15@nenu.edu.cn
时间的求解算法.这时从理论上分析这些问题在最
坏情况下的时间复杂性上界尤为重要，因为此时对
该上界的一个微小的改进，例如从
o
(C
k
)
改进为
。
((c-e)k)
，
就会使得问题求解的算法在效率上获
得指数级别的提高.以
SAT
问题为例，作为第一个
被证明是
NP
完全的问题，改进其在最坏情况下的
时间上界受到了研究人员的广泛关注.
MaxSAT
(maximum
satisfiabil
即)问题是
SAT
问题的扩展，它
资源评论
