吉林大学学报(工学版) ›› 2011, Vol. 41 ›› Issue (增刊2): 264-268.

• paper • Previous Articles     Next Articles

Optimization of greedy singleton arc consistency

KONG Chui-liu1,2, XING Shi-mei3, ZHANG Hao3   

  1. 1. College of Transportation, Jilin Universtiy, Changchun 130022, China;
    2. Department of computer Science and Engineer, Jinlin Institue of Architeture and Civil Engineering, Changchun 130118, China;
    3. computer Science and Technologyon, Jilin University, Changchun, 130012, China
  • Received:2010-05-20 Online:2011-09-30 Published:2011-09-30

PDF (PC)

654

Abstract:

Storing useful information can avoid useless constraint propagation in the process of algorithm.According to that,Some improvements were made on Singleton Arc Consistency algorithm in the preprocessing step and propose a revised algorithm,denoted SAC3-Revised,which can decrease constraint propagation and time.In our experiments on random CSPs,the efficiency of our algorithm is 2 times of SAC-3 when p2 is in a certain scope and then reaches a steady behavior.Experiments on benchmark show that the efficiency of SAC3_Revised is better than that of SAC-3.

Key words: artificial intelligence, consistency technique, constraint satisfaction problem, arc consistency, Singleton arc consistency

CLC Number: 

  • TP18


[1] Bessiere C,Regin J C.MAC and combined heuristics:two reasons to for sake FC(and CBJ)on hard problems
[C]∥In Proceedings of CP′96,Cambridge,Massachu-setts,USA,Pages:61-75.

[2] Debruyne R,Bessière C.Some practicable filtering techniques for the constraint satisfaction problem
[C]∥In Processings of IJCAI′97:412-417.

[3] Lecoutre C,Cardon S.A greedy approach to establishsingleton arc consistency
[C]∥In Proceedings of IJCAI′ 05,2005:154-160.

[4] Bessiere C.Arc consistency and arc consistency again
[J].AI′2004:179-190.

[5] Bessiere C,Régin J C,Yap R H C.et al.An optimal coarse-grained Arc Consistency algorithm
[J].Artificial Intelligence(AI′2005),2005,165(2):165-185.

[6] BessièreC,Freuder E C,Régin JC.Using inference to reduce arc consistency computation
[C]∥In Proceedings of the IJCAI′95,M ontréal,Québec,Canada,1995: 592-598.

[7] Sun Ji-gui,Zhu Xing-jun,Zhang Yong-gang,et al.Fail first principle for constraint propagation.
[J].Journal of Chinese computer Systems,2008(4):679-681.

[8] Bessière C,Régin J C.Refining the basic constraint propagation algorithm
[C]∥In Proceedings of(IJCAI'2 001),Seattle,Washington,USA,2001:309-315.

[9] Wallace R J,Freuder E C.Ordering heuristics for arc consistency algorithms
[C]∥In AI/GI/VI′92,Vancouver,British Columbia,Canada,1992:163-169.

[10] Bessière C,Debruyne R.Optimal and suboptimal sin-gleton arc consistency algorithms
[C]∥In Proceedings of IJCAI′05,2005:420-428.
[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