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

作者：李丛丛; 刘惊雷^*

来源：陕西师范大学学报(自然科学版), 2020, 48(02): 43-51.

DOI：10.15983/j.cnki.jsnu.2020.01.007

• CP-nets图模型
• DAG编码
• Prüfer编码
• 随机性
• 占优查询
• 人工智能

根据图模型的结构特征和参数特征等要素设计生成随机的模型,根据顶点数与度的大小生成随机结构的CP-nets,其原理是通过改进Prüfer编码得到DAG编码,又建立DAG编码与图结构的一对一映射实现图模型的随机生成。通过设计的占优查询算法与典型的占优查询相结合验证了占优查询算法的时间消耗严重依赖于图拓扑结构的随机性和参数数量的随机性。