基于DPCNN的无向赋权图的最小生成树的求解  

The solution-based DPCNN to the minimum spanning tree of undirected weighted graph

作　　者：杨丽云[1] 周冬明[1] 赵东风[1] 张绍堂[1] 

机构地区：[1]云南大学信息学院通信工程系,云南昆明650091

出　　处：《云南大学学报（自然科学版）》2008年第2期142-147,共6页Journal of Yunnan University(Natural Sciences Edition)

基　　金：云南省自然科学基金资助项目(2005F0010M);云南大学重点资助项目(2004Z007C)

摘　　要：利用脉冲耦合神经网络(PCNN,Pulse Coupled Neural Network)的脉冲波并行传播特性,在其时延脉冲耦合神经网络(DPCNN,Delay PCNN)的基础上提出了一种求解无向赋权图最小生成树的新算法.算法针对最小生成树的权值总和最小且连通的性质,结合时延脉冲耦合神经网络脉冲波的并行传播,通过求解无向赋权图的最短路径并对其连通性进行判断,采用迭代的方法,成功地求解了无向赋权图的最小生成树.最后给出了仿真实验,证明了该方法的有效性,与传统算法比较有一定的优势.It is presented a new algorithm to find the minimum spanning tree on the basis of the pulse parallel transmission characteristic of DPCNN（Delay Pulse Coupled Neural Network）. According to the character of the minimum spanning tree, the minimal weight summation and connectivity, algorithm combines DPCNN together and finds the shortest path of undirected weighted graph, then judges the connectivity. By the iterative method, this algorithm can be used to find the minimum spanning tree of undirected weighted graph. Finally, it is given the simulation experiment to show its availability. Therefore, it is clear that it is more advantageous than the traditional ways.

关 键 词：时延脉冲耦合神经网络(DPCNN) 最小生成树 无向赋权图 

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