一种维持约束网络相容性的双向传播策略

发布时间：2021-06-07 11:54

　　约束满足问题是经典NP-hard问题,其基本算法是递归形式的回溯算法和弧一致性算法。将弧相容与回溯搜索结合,可以有效降低解空间大小。针对弧相容的维持问题,提出一种新的基于时序计数的传播方案,用于增量更新约束子网。将accumulateRevision和pushRevison作为双向修订的主要方法,以减少修订次数和域过滤变量的数量。实验结果表明,与经典的基于关系的方案和基于变量的传播方案相比,该方案的整体求解速度明显提高,且具有较少的修订时间。 

【文章来源】：计算机工程. 2020,46(04)北大核心CSCD

【文章页数】：7 页

【部分图文】：

二元约束CSP的一个子网络

本文实验是在3.20 GHz Intel 8th core i5处理器上运行,内存为8 GB。图2为使用基于约束关系、基于混合变量关系和基于变量的双向传播策略,这3种策略应用queue在不同测试集的修订次数的平均对比结果。图3为3种传播策略使用dom/ddeg在不同测试集的修订次数。图4给出3种传播策略使用queue在不同测试集的修订时间。图5给出3种传播策略使用dom/ddeg在不同测试集的修订时间。本文测试了超过1 600个实例,并在有限的600 s时间内区分是否超时,有关测试实例的详细信息可以在C.lecoutre的主页上找到。图3 3种传播策略使用dom/ddeg在不同测试集上修订次数的对比结果

3种传播策略使用dom/ddeg在不同测试集上修订次数的对比结果

【参考文献】：
期刊论文
[1]一种基于时间戳的简单表缩减算法[J]. 杨明奇,李占山,张家晨.  软件学报. 2019(11)
[2]基于启发式的约束满足问题AC系列算法改进研究[J]. 蒋李鸣,吕佳宇,何哲华,冯泽斌.  软件工程. 2018(02)
[3]Dom/ddeg自主分支辅助决策约束求解[J]. 王海燕,李闯,张良,董延华.  吉林大学学报(理学版). 2014(06)
[4]时间约束优化问题的解空间压缩方法研究[J]. 张博洋,朱延广,杨峰.  计算机工程. 2012(14)
[5]改进求解约束满足问题粗粒度弧相容算法[J]. 李宏博,李占山,王涛.  软件学报. 2012(07)
[6]基于约束理论的工作流适应性改进[J]. 刘俊莉,欧阳松.  计算机工程. 2010(11)

硕士论文
[1]CSP中的约束传播策略及启发式的研究[D]. 杨微.吉林大学 2018



本文编号：3216526