无环配置问题研究  

On Acycle Configuration Problems

作　　者：王红梅[1,2] 李宏博[2] 李占山[2] 

机构地区：[1]长春工业大学计算机科学与工程学院,长春130012 [2]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（理学版）》2010年第3期444-448,共5页Journal of Jilin University:Science Edition

基　　金：国家自然科学基金(批准号:60773097;60873148;60973089);吉林省科技发展计划项目基金(批准号:20071106)

摘　　要：基于约束的配置问题提出一种无回溯搜索算法,通过弧相容技术将所有不相容的值删除,指导用户进行产品配置,并对其正确性进行了证明.探讨了将目前两种主流计算冲突解释方法应用到无环配置问题的可行性.In view of constraint-based configuration problems solved by the classic algorithms which are used to solve constraint satisfaction problems,the authors proposed the notion of model correctness,then analysed the properties of acycle configuration,gave a backtrack-free search algorithm for solving configurations,used the arc consistency technologies to delete the redundant values from the domains of related variables so as to guide the users to configure products,and proved the correctness of the algorithm. Finally,the two popular algorithms to compute the explanations were applied to acycle configurations.

关 键 词：约束满足问题 配置问题 模型正确性 弧相容 解释 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]