ISSN 1000-1239 CN 11-1777/TP

Journal of Computer Research and Development ›› 2014, Vol. 51 ›› Issue (11): 2573-2584.doi: 10.7544/issn1000-1239.2014.20130687

Previous Articles    

Quantum-Cooperative Method for Maximum Weight Perfect Matching Problem of Bipartite Graph

Yin Guisheng1, Cui Xiaohui1,2, Dong Hongbin1, Dong Yuxin1, Cui Xiang1,3   

  1. 1(College of Computer Science and Technology, Harbin Engineering University, Harbin 150001); 2(School of Information Science and Technology, Beijing Forestry University, Beijng 100083); 3(College of Software, Harbin University of Science and Technology, Harbin 150001)
  • Online:2014-11-01

Abstract: Most combinational optimization problems of information science can be abstracted into the maximum weight perfect matching problem of bipartite graph. Due to the growth in the amount of data, classical algorithms of solving the matching problem of bipartite graph are difficult to balance the contradiction between the efficiency of the algorithms and the precision of the solutions. Based on this point, an intelligent optimization method to solve the general maximum weight perfect matching problem is proposed. The method converts the matrix form of an original candidate matching solution into the evolution basis which the intelligent algorithm can handle, and adaptively chooses the effectively evolutionary strategies from the improved discrete particle swarm optimization and simulated annealing based on the off-spring selection and the quantum-cooperative process, and moreover, it maintains the steady evolution and promots the rapid convergence of the population. According to the experimental results of the test functions with the various types and the matching matrixes with the various dimensions, the proposed method outperforms other algorithms under the condition of the restricted iteration, and presents the higher convergence precision and the faster convergence speed, as well as the adaptability to various kinds of the classical optimization problems and the high dimensional matching problems.

Key words: bipartite graph, maximum weight, perfect matching, quantum-cooperative, conversion of the candidate matching solutions

CLC Number: