计算机应用

作者：李丛丛, 刘惊雷

单位：烟台大学 计算机与控制工程学院, 山东 烟台 264005

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

基金：国家自然科学基金资助项目（61572419，61773331，61703360，61801414）。

针对条件偏好网络（CP-nets）图模型在进行推理运算时的高时间复杂度的问题，提出了一种基于Dandelion编码生成有界树宽的CP-nets（BTW-CP-nets Gen）算法。首先，通过Dandelion编码与树宽为k的树结构（k-tree）之间的双向映射原理推导出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算法在图模型的推理中能够有效提高算法效率。

来源：2021年第1期

《计算机应用》期刊编辑部

查看计算机应用杂志2021年第1期