摘要
无向图G的生成树问题,在电气工程和计算机科学领域应用广泛;针对Mayeda生成树不易编码实现问题,提出易于编码实现的Mayeda生成树实用算法及基于矩阵环和操作的实现方法。提出Mayeda生成树实用算法,并证明该实用算法生成树的不重复性和完备性;进而提出基于矩阵环和操作的实用算法的实现方法,以命题的形式证明了该实现方法的有效性;相对于遍历方法,该实现方法具有更高的计算效率。算法复杂性分析及算例均证明了所提方法的有效性。Mayeda生成树实用算法的完备性、不重复性(即不同的树支交换必定生成不同的树)以及基于矩阵环和操作实现方法的快速性,为基于它编码的电力系统配网重构随机进化优化快速获得其最优解奠定了理论基础。因此具有很好的工程应用前景。
Spanning tree problem of undirected graph G is widely used in electrical engineering and computer science. Considering the uneasy-coded problem of Mayeda spanning tree method, a practical Mayeda spanning tree method and its implementation strategy based on matrix exclusive OR operation were proposed in the paper. The practical Mayeda spanning tree method was presented, and its unrepeatability and completeness in constructing new trees were proved;then the implementation strategy of the practical method whose computional efficiency is higher than the traversal method, was presented based on matrix exclusive OR operation. The complexity analysis result of the algorithm and the case study results verified the effectiveness of the method. The completeness and unrepeatability （means different branch exchanges consequentially generate different trees） of the practical Mayeda spanning tree method, and the capability of the implementation strategy to quickly construct a new tree, laid a theoretical foundation for quickly achieving optimal solutions of stochastic evolutionary optimization in power distribution network reconfiguration based on the proposed coding method, and thus is feasible.
出处
《中国电机工程学报》
EI
CSCD
北大核心
2014年第31期5659-5667,共9页
Proceedings of the CSEE
关键词
配网重构
Mayeda生成树
实用算法
矩阵环和操作
编码
distribution network reconfiguration
Mayeda spanning tree
practical method
matrix exclusive OR operation
encoding method
