基于改进Prim算法的路径规划研究  

Research on path planning based on improved Prim algorithm

作　　者：李耀东 苗春艳 高健 刘辛垚 LI Yaodong;MIAO Chunyan;GAO Jian;LIU Xinyao(Hulunbeier Meteorological Bureau,Hulunbeier 021008,China;Hulunbeier Arong Banner Meteorological Bureau,Hulunbeier 162700,China;Ulanhot Meteorological Bureau,Ulanhot 137400,China)

机构地区：[1]呼伦贝尔市气象局,内蒙古呼伦贝尔021008 [2]呼伦贝尔市阿荣旗气象局,内蒙古呼伦贝尔162700 [3]乌兰浩特市气象局,内蒙古乌兰浩特137400

出　　处：《现代电子技术》2024年第4期176-181,共6页Modern Electronics Technique

摘　　要：文中提出一种基于聚类分析改进Prim(普里姆)最小生成树的路径规划算法,采用二分法将站网中的站点先聚类,分成多个微小的站点聚类中心,再以各聚类中心进行Prim最小生成树的路径规划,量化站网空间分布特征,通过聚类增强最小生成树,达到路径优化的目的。实践结果证明,改进的Prim算法适用于大型稠密的站网,在稠密的连通图中,只要调整指数进而控制聚类中心的数量,就能简化站网布局,降低算法的空间复杂度,达到更好的实际应用。A path planning algorithm based on clustering analysis to improve the Prim minimum spanning tree is proposed.The dichotomy is used to cluster the stations in the station network to divide them into several small cluster centers,and then the Prim minimum spanning tree path planning with each cluster center is conducted to quantify the spatial distribution characteristics of the station network.By clustering,the minimum spanning tree is enhanced to achieve the goal of the path optimization.The practical results show that the improved Prim algorithm is suitable for large and dense station networks.In dense connected graphs,adjusting the index to control the number of cluster centers can simplify the station network layout,reduce the spatial complexity of the algorithm,and achieve better practical applications.

关 键 词：路径规划 改进Prim算法 聚类分析 二分法 最小生成树 空间复杂度 

分 类 号：TN919-34[电子电信—通信与信息系统] TP311[电子电信—信息与通信工程]