Штучний інтелект

Анотація: The article proposes new method for solving the assignment problem based on recursive obtaining an optimal solution. It consists in finding a minimum weighted matchings total weight in a bipartite graph, using concepts the shortest increasing path. The proposed method allows to obtain solutions of the assignment problem is significantly faster than existing methods.

Ключові слова: the assignment problem, matching, bipartite graph, increasing path

Посилання:

1. Papadimitriou C. Combinatorial Optimization: Algorithms and Complexity / C. Papadimitriou, K. Steiglitz. –M.: Mir, 1985. – 510 p.
2. Panishev А.V. Fast algorithm for solving the assignment problem for finding lower bounds on the cost of theroute of a Salesman / A.Y. Levchenko, A.V. Morozov, A.V. Panishev // Artificial intelligence The Institute ofArtificial Intelligence.– Donetsk, 2011 .– P. 406-416.
3. Levchenko A.Y. Acceleration mechanism in the Little’s method for solving problems in the class of aSalesman / A.Y. Levchenko, A.V. Morozov, A.V. Morozov // Artificial intelligence The Institute of ArtificialIntelligence.– Donetsk, 2012. – P. 95-110.