Computer Science ›› 2015, Vol. 42 ›› Issue (5): 270-273.doi: 10.11896/j.issn.1002-137X.2015.05.054

Previous Articles     Next Articles

Research on Algorithm of Satisfiability Ranking Generation for CP-nets

SUN Xue-jiao and LIU Jing-lei   

  • Online:2018-11-14 Published:2018-11-14

Abstract: CP-nets(condition preference networks) is a simple and intuitive graphical tool for representing conditional ceteris paribus preference statements over the values of a set of variables,and it has been a studying hotspot in artificial intelligence recently.The satisfiability ranking of CP-nets is studied.By constructing induced graph of CP-nets and solving the strong dominance testing with respect to binary-valued CP-nets,the number of satisfiability ranking was derived.And the algorithm of generating all satisfiability rankings was designed by analyzing the reachability matrix acquired from strong dominance testing.What’s more,the syntax,semantics and some definitions were collated and introduced.

Key words: Condition preference networks,Condition preference table,Induced graph of CP-nets,Strong dominance testing,Preferences satisfiability,Satisfiability ranking

[1] Pitkou J E,Schutze H,Cass TA,et al.Personalized search[J].Comm.ACM,2002,5(9):50-55
[2] Abbas A E,Bell D E.One-Switch Independence for Multiattribute Utility Functions[J].Operations Research,2011,9:764-771
[3] Bobadilla J,Hernamde A,Ortega F,et al.Preference Elicitation Techniques for Group Recommender Systems[J].Information Sciences,2012,9(1):155-175
[4] Kieβling W,Hafenrichter B,Fischer S,et al.PreferenceXPATH:A query language for E-commerce[C]∥Proceedings of the 5th International Conference Wirtschaftsinformatik.Augsburg,Germany,2001:43-62
[5] Boutilier C,Brafman R,Domshlak C,et al.CP-nets:a tool for representing and reasoning with conditional ceteris paribus statements[J].Journal of Artificial Intelligence Research,2004,1:135-191
[6] Goldsmith J,Lang J,Truszczynski M,et al.The computational complexity of dominance and consistency in CP-nets[J].Journal of Artificial Intelligence Research,2008,3(1):403-432
[7] Brafman R,Domshlak C,Shimony E.On graphical modeling of preference and importance[J].Journal of Artificial Intelligence Research,2006,5:389-424
[8] Bouveret S,Endriss U,Lang J.Conditional Importance Net-works:A Graphical Language for Representing Ordinal,Monotonic Preferences over Sets of Goods[C]∥Proceedings of the 21st Int Conf on Artificial Intelligence.San Francisco,USA:Morgan Kaufmann Publishers,2009:67-72
[9] Ciaccia P.Querying databases with incomplete CP-nets[C]∥Multidisciplinary Workshop on Advances in Preference Handling,2007:1-8
[10] Endres M,Kiebling W.Transformation of Tcp-net queries into preference database queries[C]∥Proceedings of the ECAI 2006 Multidisciplinary Workshop on Advances in Preference Handling.2006:23-30
[11] Bosc P,Hadjali A,Pivert O.On database queries involving competitive conditional preferences [J].International Journal of Intelligent Systems,2011,6(3):206-227
[12] 刘惊雷.CP-nets及其表达能力研究[J].自动化学报,2011,7(3):290-302
[13] 刘惊雷,廖士中,张伟.CP-nets的完备性及一致性研究[J].软件学报,2012,3(6):1531-1541
[14] 孙雪姣,刘惊雷.CP-nets的可满足性及一致性研究[J].计算机研究与发展,2012,49(4):754-762
[15] 孙雪姣,刘惊雷.CP-nets的定性偏好决策及一致性推理[J].计算机科学,2013,0(2):274-278

No related articles found!
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
No Suggested Reading articles found!