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

摘要：

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

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

所属期刊栏目：23

分类号：TP181(自动化基础理论)

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

在线出版日期：2012-07-31（万方平台首次上网日期，不代表论文的发表时间）

页数：共11页

页码：1531-1541