基于问题结构的边界启发式方法  

Boundary heuristic based on problem structure

作　　者：李占山[1,2] 张良[1,2] 郭劲松[1,2] 张乾[1,2] 

机构地区：[1]吉林大学符号计算与知识工程教育部重点实验室,长春130012 [2]吉林大学计算机科学与技术学院,长春130012

出　　处：《吉林大学学报（工学版）》2013年第4期1045-1051,共7页Journal of Jilin University:Engineering and Technology Edition

基　　金：国家自然科学基金项目(60873148;60973089;61170314);吉林省自然科学基金项目(201101039;20071106;20080107);高等学校博士学科点专项科研基金项目(20100061110031)

摘　　要：现有启发式方法在处理Composed问题时会生成过多节点,造成求解效率下降。基于此类问题结构特性,设计并实现了一种新的变量排序启发式方法——边界启发式。针对问题结构,提出了边界变量的概念,在Composed问题上实现了对边界变量的筛选,检索过程中,同普通变量相比边界变量被赋予更高的实例化优先级,文中给出了新启发式方法的两种实现策略。实验结果表明,新启发式方法在求解效率上明显优于原有启发式方法。Composed problems are one kind of random Constraint Satisfaction Problems （CSPs）. When solving such problems, existing heuristics always bring out excessive nodes, thus seriously affecting the solving efficiency. Based on the structural property of the Composed problems, we develop a new variable ordering heuristic, named boundary heuristic. First, we compose the concept of boundary variables. Then we present the method to recognize boundary variables in Composed problems. During search process, boundary variables have higher priorities to be instantiated than common variables. We propose two strategies to enforce the new heuristic when it is used to solve problems. Experimental results show that the efficiency of the boundary heuristic outperforms the existing ones by large margins.

关 键 词：人工智能 边界启发式 约束满足问题 Composed问题 

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