一种基于识别重复路径的动态决策策略

来源 :计算机学报 | 被引量 : 0次 | 上传用户:wind503
下载到本地 , 更方便阅读
声明 : 本文档内容版权归属内容提供方 , 如果您对本文有版权争议 , 可与客服联系进行内容授权或下架
论文部分内容阅读
在现有基于冲突学习子句的求解器中,频繁重启和变量相位存储技术的应用,导致重启之后产生大量重复变量赋值序列,在求解过程中对变量重复赋值会浪费求解资源。本文提出一种基于识别重复路径的动态决策策略。首先,检测搜索过程中产生的重复赋值变量序列,算法中参数依据子句数与变元数的比率而动态变化;其次,更新参与冲突次数最多的变量的活跃值,选择合适的分支决策变量,改变变量赋值序列。基于国际SAT竞赛中知名求解器Glucose3.0,MapleCOMSPS,Glucose4.1以及Lingeling,分别实现了改进算法—DDIDT。实验结果可得,改进求解器Glucose_DDIDT相比Glucose3.0降低决策数为11.2%~61.6%,且Glucose_DDIDT求解难度较大实例的个数提高了63.9%。针对求解2015年到2017年SAT竞赛的应用类型的实例,Glucose_DDIDT相比Glucose3.0的求解个数增长了6.0%;改进求解器MapleCOMSPS_DDIDT相比MapleCOMSPS求解个数提高了2.5%;相比Glucose4.1,改进求解器Glucose4.1_DDIDT的求解个数增长了3.1%;虽然Lingeling_DDIDT求解实例总数相比Lingeling增加1个,但求解时间有所减少。实验表明,所提策略可有效识别重复路径,适时选择合适的分支决策变量,改变搜索路径,减少计算时间。
其他文献
晚渐新世-中中新世,南海南部经历了重要的构造变革,北康盆地物源发生了重大变化,引起分散体系的变化,从而影响油气资源分布,因此物源研究具有重要意义。本文利用地震反射资料,开展地
钾是作物生长必须元素之一,我国南方水稻土中相当普遍地存在缺钾现象并在一定程度上限制了水稻生长,合理施用钾肥是解决这个问题的主要途径之一。在浙江省金华市,通过一系列田间
研究战争罪国内立法的理论与实践问题,对帮助国家领导者的正确决策,履行国家的国际承诺,震撼潜在的危及和平的争端和情势等方面具有不可抵挡的作用。适用国内惩治战争罪是我
从2001年秋季起,我国教育部积极推进小学开设英语课程,从而促使了我国小学英语教学飞速的发展。然而,目前口语教学时间的投入量少,口语教学方法单一,课后缺乏口语环境的创设,
语言作为文化的载体,与文化相互依赖、相互影响。高校外语教师应注重培养学生社会文化能力。教师通过介绍背景文化知识、文化对比学习、情景模拟和运用等文化导入的教学方法
按照美国《科学引文索引》(Science Citation Index,SCI)影响因子排序,对国际中医药和结合医学领域SCI收录期刊作简要介绍,主要包括国际中医药期刊创刊日期、主编、主办单位
文章试图建立语言文字规范体系的结构框架 ,并以此为据 ,阐释了辞书与语言文字规范的逻辑关系。语言文字的规范体系 ,有成文规范和不成文规范两种基本形式。不成文规范是成文
本文报道了在恒温条件下,采用pH滴定法对两个酞酰苯胺酸化合物:[2-COOC6H4CONHC6H5,2-COOC6H4CONH-(2-OCH3)C6H4]与三个马来酰苯胺酸化合物[COOCH2CH2CONHC6H5,COOCH2CH2CONH-(2-OCH
随着我国综合国力的进一步提升,我国旅游业进入了全球化时代。据世界旅游组织预测,到2020年,中国将成为世界第一大旅游目的地国和第四大旅游客源国。“红色旅游”是我国特有