计算机工程

作者：李晓, 司怀伟, 郭宗沂, 李东雨, 谭国真

单位：大连理工大学 电子信息与电气工程学部, 辽宁 大连 116024

关键词：人工智能,约束网络,弧相容,启发式传播,传播策略

基金：国家自然科学基金青年基金（61602084）；国家自然科学基金辽宁省联合基金重点支持项目（U1808206）；辽宁省博士科研启动基金（201601041）。

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

来源：2020年第4期

《计算机工程》期刊编辑部

查看计算机工程杂志2020年第4期