软件学报
軟件學報
연건학보
JOURNAL OF SOFTWARE
2012年
6期
1531-1541
,共11页
强占优%偏好的完备性%偏好的一致性%翻转关系的传递闭包%可分离的条件偏好网%判定定理及算法
彊佔優%偏好的完備性%偏好的一緻性%翻轉關繫的傳遞閉包%可分離的條件偏好網%判定定理及算法
강점우%편호적완비성%편호적일치성%번전관계적전체폐포%가분리적조건편호망%판정정리급산법
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是一種簡單而又直觀的圖形化偏好錶示工具,成為近幾年人工智能的一箇研究熱點.然而,任意二值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시일충간단이우직관적도형화편호표시공구,성위근궤년인공지능적일개연구열점.연이,임의이치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적기출이론연구.