CP-nets的完备性及一致性研究  

On the Completeness and Consistency for CP-nets

作　　者：刘惊雷[1,2] 廖士中[1] 张伟[2] 

机构地区：[1]天津大学计算机科学与技术学院,天津300072 [2]烟台大学计算机科学与技术学院,山东烟台264005

出　　处：《软件学报》2012年第6期1531-1541,共11页Journal of Software

基　　金：国家自然科学基金(61170019);天津市自然科学基金(11JCYBJC00700)

摘　　要：CP-nets是一种简单而又直观的图形化偏好表示工具,成为近几年人工智能的一个研究热点.然而,任意二值CP-nets上的强占优算法还没有给出,CP-nets可表示的偏好的完备性还无人研究,CP-nets所能表示的偏好是否一致也还未彻底解决.基于CP-nets上的强占优运算研究CP-nets的完备性和一致性.首先,通过构造CP-nets导出图及其性质的研究,得出强占优的本质是求取翻转关系的传递闭包,从而利用Warshall算法求出可判断任意CP-nets的强占优;其次,通过求取3种不同结构(可分离的、链表结构和树形结构)的CP-nets的偏好个数,给出了CP-nets可表达的偏好的不完备性定理,并给出了可分离的CP-nets中偏好的计数公式;最后,研究CP-nets的一致性,给出了CP-nets的一致性判定定理及其算法.所做工作不仅解决了Boutilier和Goldsmith提出的一些难题,还深化了CP-nets的基础理论研究.CP-nets （conditional preference networks） is a simple and intuitive graphical tool for representing conditional preference statements over the values of a set of variables. It has been a studying hotspot in artificial intelligence recently. The algorithm of strong dominance with respect to any binary-valued CP-nets has not been given; preferences completeness of CP-nets have not been studied by anyone, This paper makes a study of completeness and consistency of CP-nets by designing a strong dominance algorithm. First, by constructing induced graph of CP-nets and studying its properties, the study solves the problem of strong dominance with respect to any binary-valued CP-nets by Warshall algorithm to get the transitive closure of flip relation. Second, by solving the preference number of three kinds of CP-nets （separeble-structured, chain-structured, tree-structured）, the study gives preferences incompleteness theorem and counting number formula of separeble condition preference networks. Finally, the study deals with consistency problem, and consistency judgment theorem and algorithm are given. The method not only solves some difficult problems proposed by Boutilier and Goldsmith, but also deepens the basic theory researching of CP-nets.

关 键 词：强占优 偏好的完备性 偏好的一致性 翻转关系的传递闭包 可分离的条件偏好网 判定定理及算法 

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