基于寻找可满足2-SAT子问题的SAT算法

来源 :计算机应用研究 | 被引量 : 2次 | 上传用户:zcykf
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
可满足问题(SAT)是一个NP-Hard问题。提出了一种求解SAT的新算法(FFSAT)。该算法将SAT问题转换为寻找一个可满足的2-SAT子问题。SAT问题虽然是NP完全问题,但是当所有子句长度不大于2时,SAT问题可以在线性时间求解。使用2-SAT算法-BinSat求解2-SAT子问题,当它不满足时,根据赋值选择新的2-SAT子问题。实验结果表明,采用本算法的结果优于UnitWalk。
其他文献
国际上久赋盛名的虫媒病研究专家、《寄生虫与医学昆虫学报》外籍编委Chris Curtis教授于2008年5月13时与世长辞。我们痛失一位虫媒病研究大师,追思他在虫媒病遗传防治中首开
本文简要介绍了一种新型媒介生物采样系统的研制与应用情况。新型媒介生物采样箱突破了以往单一目标采样的局限,实现了多目标复合采样的目的。同时,针对流行病学侦检和生物入侵
本文报道采自福建省的埃蠓二新种:环纹埃蠓Allohelea annulata sp.nov.和闽西埃蠓Allohelea minxiasp.nov.
目前,生物医学的研究已集中在寻找新的干预措施来控制寄生虫性公共卫生问题.分子生物学和细胞生物学惊人的成就,提供了发现和评价药物分子靶的机会.DNA拓扑异构酶--"细胞内的
凭借光镜和电镜、切片和涂片技术相结合之手段,作者对斯氏艾美耳球虫(Eimeria stiedai)大配子发育及其超微结构进行了研究.大配子发育历经早、中、晚(成熟)3期.早期虫体以大
分别从长春小白鼠、徐州人和南京黄牛的粪便中分离纯化了3株微小隐孢子虫(C.parvum)卵囊,根据C.parvum 18S rRNA基因序列设计合成引物,用PCR扩增卵囊基因组DNA,其大小为586bp
文本分类是研究文本数据挖掘、信息检索的重要手段,文本特征项权重值的计算是文本分类算法的关键。针对经典的特征权重计算方法 TF-IDF中存在的不足,提出了一种动态自适应特征权重计算方法(DATW)。该算法不仅考虑了特征项在文本中出现的频率及该特征项所属文本在训练集中的数量,而且通过考查特征项的分散度和特征向量梯度差以自适应动态文本的分类。实验结果表明,采用DATW方法计算特征权重可以有效提高文本分类
通过刮取重症病犬蠕形螨发病部位的皮屑,用5%NaOH消化2h后进行虫体浓集,将浓集的虫体冻融、研磨、超声破碎,经8 000r/min离心20min,取上清为蠕形螨盐溶性粗抗原;将沉渣用尿素
根据家蝇拟除虫菊酯kdr(knockdown resistance)抗性的遗传标记L1014F突变,设计竞争特异性等位基因PCR扩增方法(cPASA,competitive PCR amplification of specific allele),用
为掌握广西登革热蚊媒动态,采用幼虫监测及诱卵器监测的方法,从2002年5月至9月分别对防城港市企沙镇、合浦县沙田镇、北海市区、东兴市口岸四处的居民区、企业、外来船只进行