| 摘要: |
| 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 的基础理论研究. |
| 关键词: 强占优 偏好的完备性 偏好的一致性 翻转关系的传递闭包 可分离的条件偏好网 判定定理及算法 |
| DOI：10.3724/SP.J.1001.2012.04090 |
| 分类号: |
| 基金项目:国家自然科学基金(61170019); 天津市自然科学基金(11JCYBJC00700) |
|
| On the Completeness and Consistency for CP-nets |
|
LIU Jing-Lei1,2, LIAO Shi-Zhong1, ZHANG Wei2
|
|
1.School of Computer Science and Technology, Tianjin University, Tianjin 300072, China;2.School of Computer Science and Technology, Yantai University, Yantai 264005, China
|
| 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. |
| Key words: strong dominance preference completeness preference consistency transitivity closure of flip relation separeble condition preference network judgment theorem and algorithm |
