| Abstrakt: |
The article substantiates the feasibility of using the capabilities of testing programs on remote servers to compare the effectiveness of implementations of various methods of solving the selected combinatorial optimization problem. The method of gradually forming a set of values of the objective function as an alternative to the methods of search with returns and taking into account changes is described. The mechanism of action of the algorithms that use these methods to solve a simplified version of the classical problem of packing a backpack is explained. Fragments of programs that implement these algorithms in the C# programming language are presented, and the results of their testing in a remote computing environment are analyzed. According to the test results, it is shown that the implementation of the method of gradually forming a set of admissible values drastically reduces the execution time of programs in comparison with the implementation of other methods, which indicates its effectiveness. Based on the results of the research, the main conclusions were made. Firstly, to speed up the solution of combinatorial optimization problems, it is not enough to bypass some variants of a complete search, and it is also necessary to minimize the time of calculating the objective function for each variant, taking into account the limitations of the problem. Secondly, the method of gradually forming a set of admissible values of the objective function is an effective alternative to the methods of search with returns and taking into account changes when solving combinatorial optimization problems, if the range of values is discrete and the solution process is similar to the method of dynamic programming. And, thirdly, to determine the most effective way of solving the combinatorial optimization problem, it is not enough to compare the execution time on known test sets, but also to try to analyze their computational complexity in advance. [ABSTRACT FROM AUTHOR] |
