﻿ 维持弧的唯一性优化粗粒度弧相容算法
«上一篇
 文章快速检索 高级检索

 哈尔滨工程大学学报  2018, Vol. 39 Issue (4): 744-750  DOI: 10.11990/jheu.201610104 0

### 引用本文

LI Ying, YANG Gang, LI Zhanshan. Optimized coarse-grained arc-consistency algorithm for maintaining the uniqueness of arc[J]. Journal of Harbin Engineering University, 2018, 39(4), 744-750. DOI: 10.11990/jheu.201610104.

### 文章历史

Optimized coarse-grained arc-consistency algorithm for maintaining the uniqueness of arc
LI Ying, YANG Gang, LI Zhanshan
College of Computer Science and Technology, Jilin University, Changchun 130012, China
Abstract: To address the widely encountered problem of constraint satisfaction in artificial intelligence, this paper analyzed the putback operation of the coarseness maintenance arc-consistency algorithm to avoid the drawbacks of redundant checks for arcs while implementing the AC algorithm and verified that these checks are redundant. An improved algorithm, AC_AO, was proposed to avoid the drawbacks of these redundant checks to ensure the uniqueness of the arc and improve coarse-grained arc-consistency algorithms. The experimental results reveal that AC_AO can reduce the arc checking quantity by 77% and reduce the CPU computation time up to 30%. This improvement will greatly reduce the frequency of modifications and significantly increase the efficiency of AC algorithm execution.
Key words: artificial intelligence    constraint satisfaction problem    maintaining arc consistency    coarseness algorithm    hashing algorithm    uniqueness    preprocessing    consistency    redundancy    backtracking

1 约束背景知识

2 AC框架 2.1 AC算法

Algorithm1: AC_frame

begin

initialize Q;

while Q is not empty do

select and remove the arc(xi, c) from Q;

if revise(xi, c) then

if Di= Ø then return fail;

else for each c′ such that xi, xjX(c′)

if c′≠c then

QQ∪(xj, c′);

return success;

End

Algorithm2: procedure revise3(x, c)

begin

change←false

for each v belong to D[x], do

if v has no support on c then

remove v from D[i]

change=true;

return  change

end

Algorithm3: procedure  revise2001(x, c)

begin

change←false

for each v belong to D[x], do

if (last[c][x][v]is valid)

continue

if v has no support on c then

remove v from D[i]

change=true

update last[c][x][v]

return  change

end

Algorithm4: procedure revise3rm(x, c)

begin

change←false

for each v belong to D[x], do

if (last[c][x][v]is valid)

continue

if v has no support on c then

remove v from D[i]

change=true

update last[c][x][v] and last[c][y][b]

return  change

end

2.2 AC_AO算法

3 改进后的AC框架AC_AO

Algorithm5: AC_AO frame

begin

initialize Q

initialize q;

while q is not empty do

select and remove the arc_id from q

select and remove the arc(xi, c) from Q

if Revise(xi, c) then

if Di= Ø then return fail

else for each c′ such that xi, xjX(c′)

if c′≠c then

if arc(xj, c′)_id not in q

qq∪arc(xj, c′)_id

QQ∪(xj, c′)

return success

end

AC_AO在AC基础框架上，通过鸽巢原理可知，当队列中弧的数目大于弧的序列号总数，必然产生弧的重复，由不放回队列中已经存在弧的正确性证明可知冗余的弧可以唯一，并且不影响正确求解。由此，保持弧的唯一性，可以减少检查弧的条数，提高算法效率。

4 AC_AO算法与AC系列算法的Benchmark测试用例对比

5 结论

1) AC系列算法应用AC_AO框架在复杂度高的约束满足问题上执行效率更高。

2) AC_AO框架在规模大的约束满足问题上执行效率更高。

3) 可以将本文提出的保持弧的唯一性以避免大量的冗余检查的思想应用在其他粗粒度求解约束满足问题的算法系列中，以减少冗余检查，提高效率。

 [1] ROSSI F, VAN BEEK P, WALSH T. Handbook of constraint programming[M]. Amsterdam, Netherlands: Elsevier Science, 2006: 26-49. (0) [2] ZHOU Jianwei. Improved optimal conditions and iterative parameters for the optimal control problems with an integral constraint in square[J]. Journal of computational and applied mathematics, 2016, 307: 367-373. DOI:10.1016/j.cam.2015.12.014 (0) [3] HAN Jiangfeng, MIGÍRSKI S. A quasistatic viscoelastic frictional contact problem with multivalued normal compliance, unilateral constraint and material damage[J]. Journal of mathematical analysis and applications, 2016, 443(1): 57-80. DOI:10.1016/j.jmaa.2016.05.012 (0) [4] MACKWORTH A K. Consistency in networks of relations[J]. Artificial intelligence, 1977, 8(1): 99-118. DOI:10.1016/0004-3702(77)90007-8 (0) [5] CAI Shaowei, SU Kaile. Local search for Boolean Satisfiability with configuration checking and subscore[J]. Artificial intelligence, 2013, 204: 75-98. DOI:10.1016/j.artint.2013.09.001 (0) [6] CHOI C W, LEE J H M, STUCKEY P J. Removing propagation redundant constraints in redundant modeling[J]. ACM transactions on computational logic, 2007, 8(4): 23. DOI:10.1145/1276920 (0) [7] BOUSSEMART F, HEMERY F, LECOUTRE C. Revision ordering heuristics for the Constraint Satisfaction Problem[C]//Proceedings of the 1st International Workshop on Constraint Propagation and Implementation held with CP'04(CPAI'04). Toronto, Canada, 2004: 9-43. (0) [8] LEE J H M, ZHU Zichen. Boosting SBDS for partial symmetry breaking in constraint programming[C]//Proceedings of the 28th AAAI Conference on Artificial Intelligence (AAAI 2014). Québec City, Québec, Canada, 2014: 2695-2702. http://dl.acm.org/citation.cfm?id=2892925 (0) [9] MEHTA D, VAN DONGEN M R C. Reducing checks and revisions in coarse-grained MAC algorithms[C]//Proceedings of the 19th International Joint Conference on Artificial Intelligence. Edinburgh, UK, 2005: 236-241. http://dl.acm.org/citation.cfm?id=1642331 (0) [10] LEE J H M, LEUNG K L. A stronger consistency for soft global constraints in weighted constraint satisfaction[C]//Proceedings of the 24th AAAI Conference on Artificial Intelligence (AAAI-2010). Atlanta, USA, 2010: 121-127. https://www.researchgate.net/publication/221604924_A_Stronger_Consistency_for_Soft_Global_Constraints_in_Weighted_Constraint_Satisfaction (0) [11] LECOUTRE C. Constraint networks:techniques and algorithms[M]. Great Britain, Narendra Jussien, United States: Wiley, 2009: 185-236. (0) [12] JAVED K, GOURIVEAU R, ZERHOUNI N, et al. Prognostics of proton exchange membrane fuel cells stack using an ensemble of constraints based connectionist networks[J]. Journal of power sources, 2016, 324: 745-757. DOI:10.1016/j.jpowsour.2016.05.092 (0) [13] 王瑞伟, 李占山, 李宏博. 求解约束可满足问题的eSTR算法优化[J]. 计算机研究与发展, 2016, 53(7): 1586-1595. WANG Ruiwei, LI Zhanshan, LI Hongbo. Optimizing eSTR algorithm for solving constraint satisfaction problems[J]. Journal of computer research and development, 2016, 53(7): 1586-1595. DOI:10.7544/issn1000-1239.2016.20150284 (0) [14] 王涛, 张乾, 李占山, 等. 基于成功回溯的约束推理技术[J]. 吉林大学学报(工学版), 2016, 46(5): 1622-1626. WANG Tao, ZHANG Qian, LI Zhanshan, et al. Reasoning from successful backtracking in constraint programming[J]. Journal of Jilin University (engineering and technology edition), 2016, 46(5): 1622-1626. (0) [15] 李宏博, 梁艳春, 李占山. 概率最大受限路径相容算法[J]. 软件学报, 2015, 26(12): 3140-3150. LI Hongbo, LIANG Yanchun, LI Zhanshan. Probabilistic max restricted path consistency[J]. Journal of software, 2015, 26(12): 3140-3150. (0) [16] 李宏博, 李占山, 王涛. 改进求解约束满足问题粗粒度弧相容算法[J]. 软件学报, 2012, 23(7): 1816-1823. LI Hongbo, LI Zhanshan, WANG Tao. Improving coarse-grained arc consistency algorithms in solving constraint satisfaction problems[J]. Journal of software, 2012, 23(7): 1816-1823. (0)