复旦学报(自然科学版)
複旦學報(自然科學版)
복단학보(자연과학판)
JOURNAL OF FUDAN UNIVERSITY(NATURAL SCIENCE)
2008年
6期
786-790
,共5页
荆明娥%陈更生%赵长虹%唐璞山%周电
荊明娥%陳更生%趙長虹%唐璞山%週電
형명아%진경생%조장홍%당박산%주전
可满足性问题%卡诺图%正交子句%NP完全问题
可滿足性問題%卡諾圖%正交子句%NP完全問題
가만족성문제%잡낙도%정교자구%NP완전문제
提出了一种解决SAT问题的新算法.该算法首先定义了子句之间的正交关系;然后从消除子句之间的交叠信息出发,利用正交子句的特性,结合有效的简化技术,逐渐将问题简化为一组与原问题完全等价的正交子句组;最后,根据正交子句组对整个赋值空间的覆盖情况来判断SAT是否满足.该算法为SAT问题的解决提供了一个新的思路.
提齣瞭一種解決SAT問題的新算法.該算法首先定義瞭子句之間的正交關繫;然後從消除子句之間的交疊信息齣髮,利用正交子句的特性,結閤有效的簡化技術,逐漸將問題簡化為一組與原問題完全等價的正交子句組;最後,根據正交子句組對整箇賦值空間的覆蓋情況來判斷SAT是否滿足.該算法為SAT問題的解決提供瞭一箇新的思路.
제출료일충해결SAT문제적신산법.해산법수선정의료자구지간적정교관계;연후종소제자구지간적교첩신식출발,이용정교자구적특성,결합유효적간화기술,축점장문제간화위일조여원문제완전등개적정교자구조;최후,근거정교자구조대정개부치공간적복개정황래판단SAT시부만족.해산법위SAT문제적해결제공료일개신적사로.
