Journal of Software:2012.23(6):1531-1541

CP-nets 的完备性及一致性研究
(天津大学 计算机科学与技术学院,天津 300072;烟台大学 计算机科学与技术学院,山东 烟台 264005)
On the Completeness and Consistency for CP-nets
LIU Jing-Lei,LIAO Shi-Zhong,ZHANG Wei
(School of Computer Science and Technology, Tianjin University, Tianjin 300072, China;School of Computer Science and Technology, Yantai University, Yantai 264005, China)
Chart / table
Similar Articles
Article :Browse 3199   Download 2883
Received:July 27, 2010    Revised:July 04, 2011
> 中文摘要: 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 的基础理论研究.
Abstract: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.
文章编号:     中图分类号:    文献标志码:
基金项目:国家自然科学基金(61170019); 天津市自然科学基金(11JCYBJC00700) 国家自然科学基金(61170019); 天津市自然科学基金(11JCYBJC00700)
Foundation items:
Reference text:

刘惊雷,廖士中,张伟.CP-nets 的完备性及一致性研究.软件学报,2012,23(6):1531-1541

LIU Jing-Lei,LIAO Shi-Zhong,ZHANG Wei.On the Completeness and Consistency for CP-nets.Journal of Software,2012,23(6):1531-1541