부산대학교 도서관

One of the most common and well-known problems in combinatorial optimization is the minimum spanning tree. With the emergence of complex data structures, new, more complex, but asymptotically efficient algorithms have been proposed. In this research, we present a new evolutionary algorithm influenced by quantum mechanics, known as quantum-inspired evolutionary algorithm (QIEA) to find the minimum spanning tree of a complete weighted undirected graph as input and computational results to demonstrate the effectiveness of proposed algorithm. The proposed algorithm is named QIEA-MST and is based on concept and principle such as qubits and the superposition, coherence and the entanglement of different qubits of quantum state. The algorithm is simple and easy to understand and easy to implement. Some types of scientific and engineering problems will benefit from the proposed method.