基于Prüfer编码的随机图模型生成算法  

Random graphic model generation algorithm based on Prüfer code

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

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

出　　处：《陕西师范大学学报（自然科学版）》2020年第2期43-51,共9页Journal of Shaanxi Normal University：Natural Science Edition

基　　金：国家自然科学基金(61572419,61773331,61703360)。

摘　　要：根据图模型的结构特征和参数特征等要素设计生成随机的模型,根据顶点数与度的大小生成随机结构的CP-nets,其原理是通过改进Prufer编码得到DAG编码,又建立DAG编码与图结构的一对一映射实现图模型的随机生成。通过设计的占优查询算法与典型的占优查询相结合验证了占优查询算法的时间消耗严重依赖于图拓扑结构的随机性和参数数量的随机性。Graph model reasoning is an important work in graph model research. How to verify the designed reasoning algorithm needs to be tested based on a large number of experimental samples. In order to verify the effectiveness and solution time of the optimal query algorithm, the experimental data designed is critical. In this paper, the random graph model is designed according to the structural characteristics and parameter characteristics of the graph model. The algorithm designed in this paper generates CP-nets of random structure according to the number and degree of vertices. The principle is getting DAG code by improving Prüfer code, furthermore, the one-to-one mapping between DAG code and graph structure is established to realize the random generation of graph model. Then, by combining the designed dominant query algorithm with the typical dominant query. It is proved that the graph model generated by the designed graph model generation algorithm has the randomness of corresponding characteristics. The time consumption of the dominant detection algorithm is heavily dependent on the randomness of topological structure of the graph and the number of parameters.

关 键 词：CP-nets图模型 DAG编码 Prufer编码 随机性 占优查询 人工智能 

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