基于约束半环的CP-nets占优查询算法  

Dominance Query Algorithm for CP-nets Based on C-Semiring

作　　者：刘惊雷[1] 华臻[2] 武栓虎[1] 

机构地区：[1]烟台大学计算机学院,山东烟台264005 [2]山东工商学院信电学院,山东烟台264005

出　　处：《电子学报》2011年第8期1932-1936,共5页Acta Electronica Sinica

基　　金：国家自然科学基金(No.61070118;No.60970105)

摘　　要：用户的偏好在自动决策中起着重要的作用,作为一种表示多属性定性偏好断言的直观工具,CP-nets被许多学者研究.其上的占优查询算法的高复杂度还是一个难题,本文研究如何降低其复杂度.引入了一种求解约束满足问题的通用框架——SCSP(基于约束半环的满足问题),并指出CP-nets中的条件偏好表本质上是一种动态约束.给出了将CP-nets中的条件偏好表转化为SCSP中的约束,在SCSP中进行解的优劣判断的算法,并指出该算法具有多项式时间复杂度特性,从而基于约束半环解决了无环CP-nets上的占优查询问题.Information about user preferences plays a key role in automated decision making.As a intuitive graphical tool for representing statements over multiple attribute qualitative decision,CP-nets has attracted many researchers to study it.Its higher complexity of dominance query algorithm is a difficult problem to solve.We study how to reduce dominance query complexity.A general-purpose framework for solving constraint satisfaction problem is introduced,namely,SCSP（c-Semiring Constraint Satisfaction Problem）,and point out that conditional preference table of CP-nets just is a type of dynamic constraint.An algorithm transforming conditional preference table of CP-nets to constraint of SCSP is given,which can judge a solution is better or worse.Its polynomial time complexity property is given,so based on c-Semiring,dominance query for acyclic CP-nets is solved effectively.

关 键 词：占优查询 约束半环 约束满足问题 条件偏好表 动态约束 解的优劣 

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