目录
1.最小生成树MST
最小生成树（Minimum Spanning Tree, MST）是在给定的加权无向图中寻找一个边的子集，使得这些边构成的树包含图中的所有顶点，并且边的总权重尽可能小。
如果图 G = ( V , E ) G=(V,E) G=(V,E)是加权无向图，其中 V V V是顶点集， E E E是边集，每条边 e ∈ E e\in E e∈E有权重 w ( e ) w(e) w(e)，MST需要找到一个边的子集 T ⊆ E T\subseteq E T⊆E，满足:
- T T T包含所有顶点
- T T T不含环
- T T T中边权重之和最小
MST在实际应用中有广泛用途，比如WSN拓扑，交通规划、电路布局等。
常用求解算法包括：Kruskal算法，Prim算法，这两种算法是贪心算法，因此加权无向图的MST不止一种情况。
2.算法原理
3.算法过程
基础粒子群算法PSO是处理连续空间问题，MST问题则是离散问题，因此这里采用二进制粒子群优化算法，简单处理方式就是解向量每个维度进行判断，大于或等于0.5的元素被认为是1，其余为0。
a.构建解向量的邻接矩阵A
b.计算图的连通性，这里用一点矩阵知识 L = logical ( ( eye ( n ) + A ) n ) L=\text{logical}((\text{eye}(n)+A)^n) L=logical((eye(n)+A)n)，这里可以处理为惩罚
c.目标函数可以定义为 min ∑ e ∈ T w ( e ) \min\sum_{e\in T}w(e) min∑e∈Tw(e)
4.结果展示
5.参考文献
[1] Zhang Y H, Lin Y, Gong Y J, et al. Particle swarm optimization with minimum spanning tree topology for multimodal optimization[C]//2015 IEEE Symposium Series on Computational Intelligence. IEEE, 2015: 234-241.
[2] Guo W, Zhang B, Chen G, et al. A PSO-optimized minimum spanning tree-based topology control scheme for wireless sensor networks[J]. International Journal of Distributed Sensor Networks, 2013, 9(4): 985410.