电子学报
電子學報
전자학보
ACTA ELECTRONICA SINICA
2011年
8期
1932-1936
,共5页
占优查询%约束半环%约束满足问题%条件偏好表%动态约束%解的优劣
佔優查詢%約束半環%約束滿足問題%條件偏好錶%動態約束%解的優劣
점우사순%약속반배%약속만족문제%조건편호표%동태약속%해적우렬
用户的偏好在自动决策中起着重要的作用,作为一种表示多属性定性偏好断言的直观工具,CP-nets被许多学者研究.其上的占优查询算法的高复杂度还是一个难题,本文研究如何降低其复杂度.引入了一种求解约束满足问题的通用框架——SCSP(基于约束半环的满足问题),并指出CP-nets中的条件偏好表本质上是一种动态约束.给出了将CP-nets中的条件偏好表转化为SCSP中的约束,在SCSP中进行解的优劣判断的算法,并指出该算法具有多项式时间复杂度特性,从而基于约束半环解决了无环CP-nets上的占优查询问题.
用戶的偏好在自動決策中起著重要的作用,作為一種錶示多屬性定性偏好斷言的直觀工具,CP-nets被許多學者研究.其上的佔優查詢算法的高複雜度還是一箇難題,本文研究如何降低其複雜度.引入瞭一種求解約束滿足問題的通用框架——SCSP(基于約束半環的滿足問題),併指齣CP-nets中的條件偏好錶本質上是一種動態約束.給齣瞭將CP-nets中的條件偏好錶轉化為SCSP中的約束,在SCSP中進行解的優劣判斷的算法,併指齣該算法具有多項式時間複雜度特性,從而基于約束半環解決瞭無環CP-nets上的佔優查詢問題.
용호적편호재자동결책중기착중요적작용,작위일충표시다속성정성편호단언적직관공구,CP-nets피허다학자연구.기상적점우사순산법적고복잡도환시일개난제,본문연구여하강저기복잡도.인입료일충구해약속만족문제적통용광가——SCSP(기우약속반배적만족문제),병지출CP-nets중적조건편호표본질상시일충동태약속.급출료장CP-nets중적조건편호표전화위SCSP중적약속,재SCSP중진행해적우렬판단적산법,병지출해산법구유다항식시간복잡도특성,종이기우약속반배해결료무배CP-nets상적점우사순문제.