%0 Journal Article
%T Research on CP-nets and Its Expressive Power<br>CP-nets及其表达能力研究
%A LIU Jing-Lei
%A <br>刘惊雷
%J 自动化学报
%D 2011
%I 
%X Preference handling is one of the important researching contents in artificial intelligence, whose four studying hotspots are preference representation, preference elicitation, preference aggregation and preference inference. The conditional preference networks (CP-nets) is a simple and intuitive graphical tool for representing conditional ceteris paribus preference statements over the values of a set of variables. But there are very few works that address the problem of expressive power of CP-nets. In this paper, the expressive power of CP-nets is studied, in particular, preference completeness, some operations complexity of CP-nets and situation to which the model is applicable are discussed detailedly. Firstly, some operations of CP-nets are discussed; by using the improved Warshall algorithm, we solve the problem of worst case complexity of strong dominance testing with respect to binary-valued CP-nets, and prove its complexity is O(4n). Secondly, by constructing induced graph of CP-nets and studying its properties, we draw a conclusion that CP-nets suit multiple attributes qualitative decision making under incomplete preference information situation especially. When handling complete preference information, it can be fulfilled by interactive communication with agent. Strong dominance testing is a tractable problem in theory, but it is a intractable problem in practice. In order to solve this exponential order complexity, at last, some reduction techniques from qualitative judging to quantitative judging with soft constraint satisfaction problem (SCSP) are given. Because qualitative judging on c-simiring is of linear complexity, it increases the expressive power of some CP-nets. All these can be seen as the improvement and refinement of Boutilier and Bistarelli's related works.
%K Conditional preference networks (CP-nets)
%K expressive power
%K strong dominance testing
%K preferences completeness
%K improved Warshall algorithm
%K multiple attribute qualitative decision under incomplete information
%K soft constraint satisfaction problem (SCSP)<br>条件偏好网
%K 表达能力
%K 强占优测试
%K 偏好的完备性
%K 改进的Warshall算法
%K 不完全信息下的多属性定性偏好决策
%K 带有软约束的满足问题
%U http://www.alljournals.cn/get_abstract_url.aspx?pcid=5B3AB970F71A803DEACDC0559115BFCF0A068CD97DD29835&cid=8240383F08CE46C8B05036380D75B607&jid=E76622685B64B2AA896A7F777B64EB3A&aid=ED54DF4FF85553F24C9CD5D352A63DDA&yid=9377ED8094509821&vid=42425781F0B1C26E&iid=38B194292C032A66&sid=211C7E02AC474301&eid=119B6C0AA09DE6B9&journal_id=0254-4156&journal_name=自动化学报&referenced_num=0&reference_num=0