Based on the graphic theory and improved genetic algorithm,an improved genetic algorithm to search the minimum spanning trees is given . The algorithm uses binary code to represent the problem of minimum spanning tree...Based on the graphic theory and improved genetic algorithm,an improved genetic algorithm to search the minimum spanning trees is given . The algorithm uses binary code to represent the problem of minimum spanning trees. It designs the corresponding fitness function,operator and few controlling strategies to improve its speed and evolutionary efficiency.Only one solution can be gotten with running traditional al-gorithem atone time.The new algorithm can get a set of the solutions with higher probability in a shorter time.The experiment shows that it has a better performance than traditional methods.展开更多
It’s a very popular issue regarding the minimum cost spanning tree which is of great practical and economical significance to solve it in a concise and accelerated way. In this paper, the basic ideas of Kruskal algor...It’s a very popular issue regarding the minimum cost spanning tree which is of great practical and economical significance to solve it in a concise and accelerated way. In this paper, the basic ideas of Kruskal algorithm were discussed and then presented a new improved algorithm—two branch Kruskal algorithm, which is improved to choose a middle value. Finally, because the time complexity is reduced, and the process is more convenient, it is concluded that the improved Kruskal algorithm is more effective in most cases compared with the Kruskal algorithm.展开更多
The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is int...The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is introduced. Compared with other evolutionary algorithms on MST problem, it is more advanced: firstly, very simple and easy to realize; then, efficient and accurate; finally general on other combination optimization problems.展开更多
The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recent...The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.展开更多
文摘Based on the graphic theory and improved genetic algorithm,an improved genetic algorithm to search the minimum spanning trees is given . The algorithm uses binary code to represent the problem of minimum spanning trees. It designs the corresponding fitness function,operator and few controlling strategies to improve its speed and evolutionary efficiency.Only one solution can be gotten with running traditional al-gorithem atone time.The new algorithm can get a set of the solutions with higher probability in a shorter time.The experiment shows that it has a better performance than traditional methods.
文摘It’s a very popular issue regarding the minimum cost spanning tree which is of great practical and economical significance to solve it in a concise and accelerated way. In this paper, the basic ideas of Kruskal algorithm were discussed and then presented a new improved algorithm—two branch Kruskal algorithm, which is improved to choose a middle value. Finally, because the time complexity is reduced, and the process is more convenient, it is concluded that the improved Kruskal algorithm is more effective in most cases compared with the Kruskal algorithm.
文摘The extension of Minimum Spanning Tree(MST) problem is an NP hard problem which does not exit a polynomial time algorithm. In this paper, a fast optimization method on MST problem——the Gradient Gene Algorithm is introduced. Compared with other evolutionary algorithms on MST problem, it is more advanced: firstly, very simple and easy to realize; then, efficient and accurate; finally general on other combination optimization problems.
基金Ph.D.foundation of Sate Education Commission of China
文摘The reconfigurable mesh consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns among the processors. Recently, this model has attracted a lot of attention. In this paper, two efficient algorithms are proposed for computing the minimum spanning tree of an n-vertex undirected graph. One runs on an n×n reconfigurable mesh with time complexity of O(log^2 n). The other runs with time complexity of O(log n) on an n^(1+E)×n reconfigurable mesh, where < E < 1 is a constant. All these improve the previously known results on the reconfigurable mesh.
