吉林大学学报(工学版) ›› 2016, Vol. 46 ›› Issue (5): 1622-1626.doi: 10.13229/j.cnki.jdxbgxb201605035

Previous Articles     Next Articles

Reasoning from successful backtracking in constraint programming

WANG Tao1, ZHANG Qian2,3, LI Zhan-shan2,3, ZHANG Liang2,3   

  1. 1.School of Computer Science and Engineering, Changchun University of Technology, Changchun 130012, China;
    2.College of Computer Science and Technology, Jilin University, Changchun 130012, China;
    3.Key Laboratory of Symbolic Computation and Knowledge Engineering, Ministry of Education, Jilin University, Changchun 130012, China
  • Received:2015-11-15 Online:2016-09-20 Published:2016-09-20

RICH HTML

0   

PDF (PC)

213

Abstract: A new reasoning method based on successful backtracking is proposed, and a new corresponding constraint solving algorithm, named MAC_BTS, is developed. It is proved that the worst-case time complexity is O(ned3) on a branch. A large number of experimental results show that the proposed algorithm, MAC_BTS, is more efficient, which can obtain the accelerations about 10% to 20% (even 50% in some problems) compared with the popular existing constraint solving algorithms MAC3rm and MAC_LC.

Key words: artificial intelligence, constraint satisfaction problem, constraint reasoning, successful backtracking

CLC Number: 

  • TP301
[1] Freuder E C, Mackworth A K. Constraint Satisfaction: an Emerging Paradigm[M]. Amsterdam: Elsevier, 2006: 13-27.
[2] Bessière C. Constraint Propagation[M]. Amsterdam: Elsevier, 2006: 29-84.
[3] Van Beek P. Backtracking Search Algorithms[M]. Amsterdam: Elsevier, 2006: 85-134.
[4] Schiex T, Verfaillie G. Nogood recording for static and dynamic constraint satisfaction problems[J]. Int Journal on Artificial Intelligence Tools, 1994, 3(2): 187-207.
[5] Lecoutre C, Sais L, Tabary S, et al. Transposition tables for constraint satisfaction[C]∥Proc of AAAI'07. Menlo Park, CA: AAAI Press, 2007: 243-248.
[6] Lecoutre C, Sais L, Tabary S, et al. Reasoning from last conflict(s) in constraint programming[J]. Artificial Intelligence, 2009, 173(18): 1592-1614.
[7] Mackworth A K. Consistency in networks of relations[J]. Artificial Intelligence, 1977, 8(1): 99-118.
[8] Sabin D, Freuder E C. Contradicting conventional wisdom in constraint satisfaction[C]∥Principles and Practice of Constraint Programming 1994. Berlin: Springer, 1994: 10-20.
[9] Lecoutre C, Hemery F. A study of residual supports in arc consistency[C]∥Proc of the 20th Int Joint Conf on Artificial Intelligence. San Francisco: Morgan Kaufmann, 2007: 125-130.
[10] Boussemart F, Hemery F, Lecoutre C, et al. Boosting systematic search by weighting constraints[C]∥Proc of the 16th European Conf on Artificial Intelligence. Hoboken, NJ: John Wiley & Sons, 2004: 146-150.
[11] Gent I P, Macintyre E, Prosser P, et al. Random constraint satisfaction: flaws and structure[J]. Constraints, 2001, 6(4): 345-372.
[12] Lecoutre C. Benchmarks of constraint satisfaction problem[EB/OL].[2012-04-16]. http://www.cril.univ-artois.fr/~lecoutre/benchmarks.html.
[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   
[1] LIU Song-shan, WANG Qing-nian, WANG Wei-hua, LIN Xin. Influence of inertial mass on damping and amplitude-frequency characteristic of regenerative suspension[J]. 吉林大学学报(工学版), 2013, 43(03): 557 -563 .
[2] CHU Liang, WANG Yan-bo, QI Fu-wei, ZHANG Yong-sheng. Control method of inlet valves for brake pressure fine regulation[J]. 吉林大学学报(工学版), 2013, 43(03): 564 -570 .
[3] LI Jing, WANG Zi-han, YU Chun-xian, HAN Zuo-yue, SUN Bo-hua. Design of control system to follow vehicle state with HIL test beach[J]. 吉林大学学报(工学版), 2013, 43(03): 577 -583 .
[4] HU Xing-jun, LI Teng-fei, WANG Jing-yu, YANG Bo, GUO Peng, LIAO Lei. Numerical simulation of the influence of rear-end panels on the wake flow field of a heavy-duty truck[J]. 吉林大学学报(工学版), 2013, 43(03): 595 -601 .
[5] WANG Tong-jian, CHEN Jin-shi, ZHAO Feng, ZHAO Qing-bo, LIU Xin-hui, YUAN Hua-shan. Mechanical-hydraulic co-simulation and experiment of full hydraulic steering systems[J]. 吉林大学学报(工学版), 2013, 43(03): 607 -612 .
[6] ZHANG Chun-qin, JIANG Gui-yan, WU Zheng-yan. Factors influencing motor vehicle travel departure time choice behavior[J]. 吉林大学学报(工学版), 2013, 43(03): 626 -632 .
[7] MA Wan-jing, XIE Han-zhou. Integrated control of main-signal and pre-signal on approach of intersection with double stop line[J]. 吉林大学学报(工学版), 2013, 43(03): 633 -639 .
[8] YU De-xin, TONG Qian, YANG Zhao-sheng, GAO Peng. Forecast model of emergency traffic evacuation time under major disaster[J]. 吉林大学学报(工学版), 2013, 43(03): 654 -658 .
[9] XIAO Yun, LEI Jun-qing, ZHANG Kun, LI Zhong-san. Fatigue stiffness degradation of prestressed concrete beam under multilevel amplitude cycle loading[J]. 吉林大学学报(工学版), 2013, 43(03): 665 -670 .
[10] XIAO Rui, DENG Zong-cai, LAN Ming-zhang, SHEN Chen-liang. Experiment research on proportions of reactive powder concrete without silica fume[J]. 吉林大学学报(工学版), 2013, 43(03): 671 -676 .
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