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

• 作者: 刘惊雷 廖士中 张伟
• 来源期刊: 软件学报
• 学科: 工学
• 关键词: 强占优 偏好的完备性 偏好的一致性 翻转关系的传递闭包 可分离的条件偏好网 判定定理及算法
• 年，卷（期）: 2012,（6）
• 所属期刊栏目: 模式识别与人工智能
• 页码范围: 1531-1541
• 分类号: TP181
• 字数: 7883字
• 语种: 中文
• DOI: 10.3724/SP.J.1001.2012.04090

摘要

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的基础理论研究.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	刘惊雷	天津大学计算机科学与技术学院	63	262	8.0	13.0
3	廖士中	天津大学计算机科学与技术学院	40	162	9.0	10.0
4	张伟	烟台大学计算机科学与技术学院	40	377	12.0	18.0