吉林大学学报(工学版) ›› 2015, Vol. 45 ›› Issue (1): 229-235.doi: 10.13229/j.cnki.jdxbgxb201501034

• Orignal Article • Previous Articles     Next Articles

Max-restricted path consistency algorithm based on half range of domain

LI Zhan-shan1,2,JIA Xiang-hua1,2,XU Cang-zhu1,2,ZHANG Shu-juan1,2   

  1. 1.Key Laboratory of Symbolic Computation and Knowledge Engineering for Ministry of Education, Jilin University, Changchun 130012,China;
    2.College of Computer Science and Technology, Jilin University, Changchun 130012,China
  • Received:2014-01-13 Online:2015-02-01 Published:2015-02-01

RICH HTML

0   

PDF (PC)

260

Abstract: A new algorithm is proposed, which combines arc consistency algorithm and max-restricted path consistency algorithm. The new algorithm makes full use of the low computation cost of arc consistency and the strong ability to remove invalid values of the max-restricted path consistency, thus reducing the visited nodes when coping with unsatisfied problems. As a result, the efficiency can be improved. Experiment results show that the proposed max-restricted path consistency algorithm based on the half range of domain outperforms the traditional maintaining arc consistency algorithm by large margin when solving the unsatisfied problems.

Key words: artificial intelligence, half range of domain, arc consistency, max-restricted path consistency, unsatisfied problems

CLC Number: 

  • TP18
[1] Sabin Daniel, Freuder Eugene C. Contradicting conventional wisdom in constraint satisfaction[C]∥Proceedings of CP, Rosario, Orcas Island, Was- hington, 1994: 10-20.
[2] Likitvivatanavong Chavalit,Zhang Yuan-lin, Bowen James,et al.Arc consistency during search[C]∥Proceedings of IJCAI, India: Morgan Kaufmann, 2007: 137-142.
[3] Mackworth Alan K.Consistency in networks of relations[J]. Artificial Intelligence, 1977,8(1): 99-118.
[4] Christophe Lecoutre, Fred Hemery. A study of residual supports in arc consistency[C]∥Proceeding of IJCAI, 2007:125-130.
[5] Christophe Lecoutre, Julien Vion. Enforcing arc consistency using bitwise operations[J]. Const- raint Programming Letters,2008(2): 21-35.
[6] Romuald Debruyne, Christian Bessiere. Some practical filtering techniques for the constraint satisfaction problem[C]∥Proceedings of IJCAI, 1997: 412-417.
[7] Romuald Debruyne, Christian Bessiere. From restricted path consistency to max-restricted path consistency[C]∥Proceedings of CP, 1997: 312-326.
[8] Thanasis Balafoutis, Anastasia Paparrizou, Kostas Stergiou, et al. New algorithms for max restricted path consistency[J]. Constraints, 2011,16(4): 372-406.
[9] Christophe Lecoutre, Patrick Prosser. Maintaining singleton arc consistency[C]∥Proceedings of CPAI, 2006: 47-61.
[10] Julien Vion, Romuald Debruyne. Light algorithms for maintaining max-RPC during search[C]∥Proceedings of SARA,2009.
[11] Possi Francesca, Van Beek Peter, Walsh Toby. Handbook of Constraint Programming[M] .New York: Elsevier, 2006:13-29.
[12] Frédéric Boussemart, Fred Hemery, Christophe Lecoutre, et al. Boosting systematic search by weighting constraints[C]∥Proceedings of ECAI, 2004: 146-150.
[13] 李占山,张良,郭劲松,等.基于问题结构的边界启发式方法[J].吉林大学学报:工学版,2013,43(5):1045-1051.
Li Zhan-shan, Zhang Liang, Guo Jin-song, et al. Boundary heuristic based on problem structure[J]. Journal of Jilin University (Engineering and Technology Edition), 2013, 43(4):1045-1051.
[1] DONG Sa, LIU Da-you, OUYANG Ruo-chuan, ZHU Yun-gang, LI Li-na. Logistic regression classification in networked data with heterophily based on second-order Markov assumption [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1571-1577.
[2] GU Hai-jun, TIAN Ya-qian, CUI Ying. Intelligent interactive agent for home service [J]. Journal of Jilin University(Engineering and Technology Edition), 2018, 48(5): 1578-1585.
[3] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Measurement of graph similarity based on vertical dimension sequence dynamic time warping method [J]. 吉林大学学报(工学版), 2018, 48(4): 1199-1205.
[4] ZHANG Hao, ZHAN Meng-ping, GUO Liu-xiang, LI Zhi, LIU Yuan-ning, ZHANG Chun-he, CHANG Hao-wu, WANG Zhi-qiang. Human exogenous plant miRNA cross-kingdom regulatory modeling based on high-throughout data [J]. 吉林大学学报(工学版), 2018, 48(4): 1206-1213.
[5] HUANG Lan, JI Lin-ying, YAO Gang, ZHAI Rui-feng, BAI Tian. Construction of disease-symptom semantic net for misdiagnosis prompt [J]. 吉林大学学报(工学版), 2018, 48(3): 859-865.
[6] LI Xiong-fei, FENG Ting-ting, LUO Shi, ZHANG Xiao-li. Automatic music composition algorithm based on recurrent neural network [J]. 吉林大学学报(工学版), 2018, 48(3): 866-873.
[7] LIU Jie, ZHANG Ping, GAO Wan-fu. Feature selection method based on conditional relevance [J]. 吉林大学学报(工学版), 2018, 48(3): 874-881.
[8] WANG Xu, OUYANG Ji-hong, CHEN Gui-fen. Heuristic algorithm of all common subsequences of multiple sequences for measuring multiple graphs similarity [J]. 吉林大学学报(工学版), 2018, 48(2): 526-532.
[9] YANG Xin, XIA Si-jun, LIU Dong-xue, FEI Shu-min, HU Yin-ji. Target tracking based on improved accelerated gradient under tracking-learning-detection framework [J]. 吉林大学学报(工学版), 2018, 48(2): 533-538.
[10] LIU Xue-juan, YUAN Jia-bin, XU Juan, DUAN Bo-jia. Quantum k-means algorithm [J]. 吉林大学学报(工学版), 2018, 48(2): 539-544.
[11] QU Hui-yan, ZHAO Wei, QIN Ai-hong. A fast collision detection algorithm based on optimization operator [J]. 吉林大学学报(工学版), 2017, 47(5): 1598-1603.
[12] LI Jia-fei, SUN Xiao-yu. Clustering method for uncertain data based on spectral decomposition [J]. 吉林大学学报(工学版), 2017, 47(5): 1604-1611.
[13] SHAO Ke-yong, CHEN Feng, WANG Ting-ting, WANG Ji-chi, ZHOU Li-peng. Full state based adaptive control of fractional order chaotic system without equilibrium point [J]. 吉林大学学报(工学版), 2017, 47(4): 1225-1230.
[14] WANG Sheng-sheng, WANG Chuang-feng, GU Fang-ming. Spatio-temporal reasoning for OPRA direction relation network [J]. 吉林大学学报(工学版), 2017, 47(4): 1238-1243.
[15] MA Miao, LI Yi-bin. Multi-level image sequences and convolutional neural networks based human action recognition method [J]. 吉林大学学报(工学版), 2017, 47(4): 1244-1252.
Viewed
Full text


Abstract

Cited
  Shared   
  Discussed   
No Suggested Reading articles found!
Copyright © Journal of Jilin University(Engineering and Technology Edition), All Rights Reserved.
Tel: +86-431-85095297　Fax: +86-431-85094074　E-mail: xbgxb@jlu.edu.cn
Powered by Beijing Magtech Co. Ltd