基于Dandelion编码生成有界树宽CP-nets  

Generating CP-nets with bounded tree width based on Dandelion code

作　　者：李丛丛 刘惊雷 LI Congcong;LIU Jinglei(School of Computer and Control Engineering,Yantai University,Yantai Shandong 264005,China)

机构地区：[1]烟台大学计算机与控制工程学院,山东烟台264005

出　　处：《计算机应用》2021年第1期112-120,共9页journal of Computer Applications

基　　金：国家自然科学基金资助项目(61572419,61773331,61703360,61801414)。

摘　　要：针对条件偏好网络(CP-nets)图模型在进行推理运算时的高时间复杂度的问题,提出了一种基于Dandelion编码生成有界树宽的CP-nets(BTW-CP-nets Gen)算法。首先,通过Dandelion编码与树宽为k的树结构(ktree)之间的双向映射原理推导出Dandelion编码与k-tree之间的解码与编码算法,实现编码与树结构的一对一映射;其次,利用k-tree来约束CP-nets结构的树宽,并利用k-tree的特征树得到了CP-nets的有向无环图结构;最后,利用离散多值函数的双射计算出各CP-nets结构节点的条件偏好表,然后针对生成的有界树宽CP-nets进行占优查询检测。理论分析和实验数据表明,与Pruffer编码生成k-tree(Pruffer code)算法相比,BTW-CP-nets Gen算法的运行时间在生成简单结构和复杂结构时的下降幅度分别为21.1%和30.5%;而BTW-CP-nets Gen算法所生成的图模型在进行占优查询时的节点遍历比在简单结构和复杂结构上分别提高了18.48%和29.03%。BTW-CP-nets Gen算法在更短的时间内,占优查询时遍历的节点率更高。可见,BTW-CP-nets Gen算法在图模型的推理中能够有效提高算法效率。Aiming at the problem of high time complexity of Conditional Preference networks(CP-nets)graph model in reasoning computation,a Generating CP-nets with Bounded Tree Width based on Dandelion code(BTW-CP-nets Gen)algorithm was proposed.First,through the principle of bidirectional mapping between Dandelion code and tree structure with tree width k(k-tree),the decoding and encoding algorithms between Dandelion code and k-tree were derived to realize the one-to-one mapping between code and tree structure.Second,the k-tree was used to constrain the tree width of CP-nets structure,and the k-tree feature tree was used to obtain the directed acyclic graph structure of CP-nets.Finally,the bijection of discrete multi-valued functions was used to calculate the conditional preference table of each CP-nets node,and the dominant query test was executed to the generated bounded tree-width CP-nets.Theoretical analysis and experimental data show that,compared with the Pruffer code generating k-tree(Pruffer code)algorithm,BTW-CP-nets Gen algorithm has the running time on generating simple and complex structures reduced by 21.1%and 30.5%respectively,and the node traversal ratio of the graph model generated by BTW-CP-nets Gen in the dominant query is 18.48%and 29.03%higher on simple structure and complex structure respectively;the smaller the time consumed by BTW-CP-nets Gen algorithm,the higher the traversal node ratio of the dominant query.It can be seen that BTW-CP-nets Gen algorithm can effectively improve the algorithm efficiency in graph model reasoning.

关 键 词：有界树宽 K-TREE Dandelion编码 条件偏好网络 均匀性 

分 类 号：TP181[自动化与计算机技术—控制理论与控制工程]