主页期刊介绍编委会编辑部服务介绍道德声明在线审稿编委办公编辑办公English
2018-2019年专刊出版计划 微信服务介绍 最新一期:2019年第10期
     
在线出版
各期目录
纸质出版
分辑系列
论文检索
论文排行
综述文章
专刊文章
美文分享
各期封面
E-mail Alerts
RSS
旧版入口
中国科学院软件研究所
  
投稿指南 问题解答 下载区 收费标准 在线投稿
刘惊雷,廖士中,张伟.CP-nets 的完备性及一致性研究.软件学报,2012,23(6):1531-1541
CP-nets 的完备性及一致性研究
On the Completeness and Consistency for CP-nets
投稿时间:2010-07-27  修订日期:2011-07-04
DOI:10.3724/SP.J.1001.2012.04090
中文关键词:  强占优  偏好的完备性  偏好的一致性  翻转关系的传递闭包  可分离的条件偏好网  判定定理及算法
英文关键词:strong dominance  preference completeness  preference consistency  transitivity closure of flip relation  separeble condition preference network  judgment theorem and algorithm
基金项目:国家自然科学基金(61170019); 天津市自然科学基金(11JCYBJC00700)
作者单位E-mail
刘惊雷 天津大学 计算机科学与技术学院,天津 300072
烟台大学 计算机科学与技术学院,山东 烟台 264005 
 
廖士中 天津大学 计算机科学与技术学院,天津 300072 szliao@tju.edu.cn 
张伟 烟台大学 计算机科学与技术学院,山东 烟台 264005  
摘要点击次数: 2811
全文下载次数: 2649
中文摘要:
      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 的基础理论研究.
英文摘要:
      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.
HTML  下载PDF全文  查看/发表评论  下载PDF阅读器
 

京公网安备 11040202500064号

主办单位:中国科学院软件研究所 中国计算机学会 京ICP备05046678号-4
编辑部电话:+86-10-62562563 E-mail: jos@iscas.ac.cn
Copyright 中国科学院软件研究所《软件学报》版权所有 All Rights Reserved
本刊全文数据库版权所有,未经许可,不得转载,本刊保留追究法律责任的权利