Шпортько, О. В. та Мушин, М. М. та Бомба, А. Я. (2023) ПРО ОБ’ЄКТНО-ОРІЄНТОВАНИЙ ПІДХІД В ПРОЦЕСІ ПРОГРАМУВАННЯ АЛГОРИТМІВ РОЗВ’ЯЗУВАННЯ ЗАДАЧ КОМБІНАТОРНОЇ ОПТИМІЗАЦІЇ. Вісник Національного університету водного господарства та природокористування (1(101)). с. 199-215.

Text Vt10117 (1).pdf Download(526kB)

Анотація

В роботі обґрунтовані переваги від застосування об’єктно-орієнтованого підходу при розв’язуванні типових задач комбінаторної оптимізації. Описано метод поступового формування множини значень цільової функції як альтернативного методам пошуку з поверненнями та врахування змін. Співставлено механізми дії алгоритмів, які застосовують ці методи для розв’язування задач комбінаторної оптимізації. Наведено фрагменти програм, які реалізують алгоритми мовою програмування C# та проаналізовано результати їх тестування у віддаленому обчислювальному середовищі. За результатами тестування показано, що реалізація методу поступового формування множини значень цільової функції кардинально зменшує час виконання програм, що вказує на доцільність його застосування при розв’язуванні типових задач комбінаторної оптимізації.

Title in English

ABOUT THE OBJECT-ORIENTED APPROACH IN THE PROCESS OF PROGRAMMING ALGORITHMS FOR SOLVING COMBINATOR OPTIMIZATION PROBLEMS

English abstract

The advantages of using an object-oriented approach for solving typical problems of combinatorial optimization are substantiated in the article. 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. Mechanisms of action of algorithms that use these methods to solve combinatorial optimization problems are compared. 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 gradual formation of the set of values of the objective function drastically reduces the execution time of programs, which indicates the expediency of using this method in solving typical problems of combinatorial optimization. Based on the results of the study, the following conclusions were made: 1. In the process of programming solving typical problems of combinatorial optimization, it is advisable to use an object-oriented approach. At the same time, the solution of each problem should be described in a separate class and the same names should be given to the same solution methods in different problems. 2. When determining the most efficient way to solve a combinatorial optimization problem, it is not enough to compare the execution time on known test sets, but it is advisable to try to analyze their computational complexity in advance. 3. In order to speed up the solution of combinatorial optimization problems, it is not enough to skip some variants of a complete search, but also to minimize the time of calculating the objective function for each variant, taking into account the constraints of the problem. 4. The method of gradually forming a set of 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 decision-making process can be divided into separate stages, as in the method of dynamic programming. 5. It is advisable to use logical or byte arrays to model sets of elements in programming. Then it is sufficient to reassign pointers to arrays and not to reassign their individual elements in order to reassign sets.

Перегляд елементу

Завантажень