粒子群优化算法在赋权有向图最小生成树中的应用  

Application of Particle Swarm Optimization Algorithm to Minimal Spanning Tree of Weighted Directed Graph

作　　者：严坤妹 YAN Kunmei(The Foundation Department, Fujian Business University, Fuzhou Fujian 350012)

机构地区：[1]福建商学院基础部,福建福州350012

出　　处：《福建师大福清分校学报》2017年第5期16-21,共6页Journal of Fuqing Branch of Fujian Normal University

基　　金：福建省教育厅科技项目(JB10221)

摘　　要：经典的Prim和Kruskal算法不能求解赋权有向图最小生成树。针对有向图存在最小生成有向树的情形,给出了有向图最小生成树的数学模型。根据有向树顶点入度d(v)1-≤的特点,设计了以u为根的有向树的编码和解码,提出了应用粒子群优化算法求解赋权有向图最小生成树问题的策略,并在此基础上设计了相应的粒子群优化算法流程。The classical Prim and Kruskal algorithm cannot solve the problem of the minimum spanning tree.Aiming at the existence of minimum spanning tree in the directed graph,the mathematical model of the minimum spanning tree of directed graph is given.Based on the characteristics of a vertex to the tree into the degree,the encoding and decoding for root directed treeare designed and the particle swarm optimization algorithm was proposed to solve empowerment strategies in the directed graph minimum spanning tree problem and the corresponding particle swarm optimization algorithm flow is designed.

关 键 词：赋权有向图 最小生成树 粒子编码 启发式算法 

分 类 号：O29[理学—应用数学]