ISSN 1000-1239 CN 11-1777/TP

• 人工智能 •

### 量子协同的二分图最大权完美匹配求解方法

1. 1(哈尔滨工程大学计算机科学与技术学院 哈尔滨 150001);2(北京林业大学信息学院 北京 100083);3(哈尔滨理工大学软件学院 哈尔滨 150001) (yinguisheng@hrbeu.edu.cn)
• 出版日期: 2014-11-01
• 基金资助:
基金项目：国家自然科学基金项目(61272186,61472095)；中央高校基本科研业务费专项基金项目(BLX2014-27)；黑龙江省自然科学基金项目(F201110)；黑龙江省博士后基金项目(LBH-Z12068)

### 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.