模式识别与人工智能
模式識彆與人工智能
모식식별여인공지능
Moshi Shibie yu Rengong Zhineng
2014年
7期
591-598
,共8页
条件偏好网%正则化路径查询%语法解析二叉树%动态规划法%组合复杂度
條件偏好網%正則化路徑查詢%語法解析二扠樹%動態規劃法%組閤複雜度
조건편호망%정칙화로경사순%어법해석이차수%동태규화법%조합복잡도
Conditional Preference Networks%Regular Path Query%Syntax Parse Binary Tree%Dynamic Programming%Combined Complexity
从表示偏好知识的条件偏好网( CP-nets)模型出发，研究该模型上的正则化路径查询问题。首先从数据库的观点给出偏好数据库的两类查询(顶点查询和路径查询)，并证明偏好数据库的表达能力强于关系数据库。其次，通过构造正则表达式的语法解析二叉树，求出各自原子表达式诱导的可达关系，从而利用动态规划法求解出CP-nets上正则表达式所诱导的可达关系，并证明算法的正确性，分析其组合复杂度。最后，给出正则化路径查询的可能应用，即可在偏好操作序列的规划中使用。
從錶示偏好知識的條件偏好網( CP-nets)模型齣髮，研究該模型上的正則化路徑查詢問題。首先從數據庫的觀點給齣偏好數據庫的兩類查詢(頂點查詢和路徑查詢)，併證明偏好數據庫的錶達能力彊于關繫數據庫。其次，通過構造正則錶達式的語法解析二扠樹，求齣各自原子錶達式誘導的可達關繫，從而利用動態規劃法求解齣CP-nets上正則錶達式所誘導的可達關繫，併證明算法的正確性，分析其組閤複雜度。最後，給齣正則化路徑查詢的可能應用，即可在偏好操作序列的規劃中使用。
종표시편호지식적조건편호망( CP-nets)모형출발，연구해모형상적정칙화로경사순문제。수선종수거고적관점급출편호수거고적량류사순(정점사순화로경사순)，병증명편호수거고적표체능력강우관계수거고。기차，통과구조정칙표체식적어법해석이차수，구출각자원자표체식유도적가체관계，종이이용동태규화법구해출CP-nets상정칙표체식소유도적가체관계，병증명산법적정학성，분석기조합복잡도。최후，급출정칙화로경사순적가능응용，즉가재편호조작서렬적규화중사용。
A formal preference knowledge representation framework, conditional preference networks ( CP-nets) , is introduced, and regular path query on the model is studied. Firstly, two kinds of queries, vertex query and path query,are given from the point of view of the database theory,and the expressive ability of preference database is proved to be stronger than that of relational database. Then, the induced reach ability relations of each atom expressions are obtained by constructing the syntax parse binary tree of regular expression, thereafter, the reach ability relation induced by regular expression of root vertex is obtained by means of dynamic programming. Moreover, the correctness and combined complexity of this algorithm are proved. Finally, a possible application scenario of regular path query is given, which demonstrates it can be applied in the preference planning sequence.
