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