基于变量传播的弧一致性算法  

Arc Consistency Algorithm Based on Variable Transmission

作　　者：谢坤武[1] 齐飞[2] 贺刚[1] 

机构地区：[1]湖北民族学院信息工程学院,湖北恩施445000 [2]华东理工大学信息科学与工程学院,上海200237

出　　处：《湖北民族学院学报（自然科学版）》2008年第1期61-64,共4页Journal of Hubei Minzu University(Natural Science Edition)

基　　金：湖北省科技攻关项目(2004AA210B01)

摘　　要：在AC-3算法的基础上,提出了采用面向变量的约束传播机制新的弧一致性算法(IAC3),算法(IAC3)引入了一个小型的附加数据结构,使得新算法的时间复杂度降低了一个幂次为O(ed2).以小的空间代价换取了显著时间效率.新算法对于通用弧一致性算法的改进效果是明显的,是对现有弧一致性算法的提高和完善,使其实用性更好,应用前景更宽.On the basis of AC -3 algorithm, the paper presents a new arc consistency algorithm （IAC3） using the variable - oriented constraint propagation mechanism. The algorithm （IAC3） introduces a somall additional data structure, making the time coonplexity of the new algorithm reduce a power as O（ed2）. The time efficiency is achieved at a cost small space. The new algorithm has greatly improved the effect of the generic arc consistency algorithm.

关 键 词：人工智能 约束满足问题 弧一致性算法 

分 类 号：TP311[自动化与计算机技术—计算机软件与理论]