Criteria of Similarity of Dynamic Problems of Combinatorial Optimization
In combinatorial optimization, you can cite many examples when the problems from different classes are solved according to the same computational scheme. This is due to the fact that the specified problems have similarities, due to which they are solved by one method or modification of the same algo...
Збережено в:
| Дата: | 2019 |
|---|---|
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Кам'янець-Подільський національний університет імені Івана Огієнка
2019
|
| Онлайн доступ: | http://mcm-math.kpnu.edu.ua/article/view/174240 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Mathematical and computer modelling. Series: Physical and mathematical sciences |
Репозитарії
Mathematical and computer modelling. Series: Physical and mathematical sciences| id |
mcm-mathkpnueduua-article-174240 |
|---|---|
| record_format |
ojs |
| institution |
Mathematical and computer modelling. Series: Physical and mathematical sciences |
| collection |
OJS |
| language |
Ukrainian |
| format |
Article |
| author |
Тимофієва, Надія Костянтинівна |
| spellingShingle |
Тимофієва, Надія Костянтинівна Criteria of Similarity of Dynamic Problems of Combinatorial Optimization |
| author_facet |
Тимофієва, Надія Костянтинівна |
| author_sort |
Тимофієва, Надія Костянтинівна |
| title |
Criteria of Similarity of Dynamic Problems of Combinatorial Optimization |
| title_short |
Criteria of Similarity of Dynamic Problems of Combinatorial Optimization |
| title_full |
Criteria of Similarity of Dynamic Problems of Combinatorial Optimization |
| title_fullStr |
Criteria of Similarity of Dynamic Problems of Combinatorial Optimization |
| title_full_unstemmed |
Criteria of Similarity of Dynamic Problems of Combinatorial Optimization |
| title_sort |
criteria of similarity of dynamic problems of combinatorial optimization |
| title_alt |
Критерії подібності динамічних задач комбінаторної оптимізації |
| description |
In combinatorial optimization, you can cite many examples when the problems from different classes are solved according to the same computational scheme. This is due to the fact that the specified problems have similarities, due to which they are solved by one method or modification of the same algorithm. It differs from geometric and described in the theory of similarity. For its establishment, an analysis of the problems of different classes is conducted in order to identify common features (criteria) that determine their similarity. Using this property allows you to develop the same methods and algorithms for their solution. The problems of combinatorial optimization, as a rule, are similar of the argument of the objective function, and the problems of combinatorics are similar on the creating and arranging of combinatorial configurations. Due to this property, their sets are generated by the same algorithm or it modification.The article describes the criterias by which the similarity of dynamic problems relating to different classes is established. The problems of combinatorial optimization, in which in the process of their solution, the current information by which the result is evaluated is generated, and the search for an optimal solution is carried out in stages with the calculation of partial amounts of the objective function, is called dynamic. The main criterias of similarity to them is the change in the result of the solution in time and for its current reference, the need to calculate the partial objective function.The process of their solution is described by a directed acyclic graph, and the partial values of the objective function change over time and are calculated according to the recurrent rules. When finding their optimal values, the Bellman principle is followed. The revealed properties of similarity, which are characteristic of the problems of this class, determine their universality, through which they are solved by the same method. Typically, dynamic programming is used to solve these problems. The study and use of this property in combinatorial optimization in the future will allow solving insoluble problems for solvable ones. Examples of some dynamic combinatorial optimization problems are given |
| publisher |
Кам'янець-Подільський національний університет імені Івана Огієнка |
| publishDate |
2019 |
| url |
http://mcm-math.kpnu.edu.ua/article/view/174240 |
| work_keys_str_mv |
AT timofíêvanadíâkostântinívna criteriaofsimilarityofdynamicproblemsofcombinatorialoptimization AT timofíêvanadíâkostântinívna kriteríípodíbnostídinamíčnihzadačkombínatornoíoptimízacíí |
| first_indexed |
2024-04-21T19:24:37Z |
| last_indexed |
2024-04-21T19:24:37Z |
| _version_ |
1796973503592792064 |
| spelling |
mcm-mathkpnueduua-article-1742402020-01-20T08:43:23Z Criteria of Similarity of Dynamic Problems of Combinatorial Optimization Критерії подібності динамічних задач комбінаторної оптимізації Тимофієва, Надія Костянтинівна In combinatorial optimization, you can cite many examples when the problems from different classes are solved according to the same computational scheme. This is due to the fact that the specified problems have similarities, due to which they are solved by one method or modification of the same algorithm. It differs from geometric and described in the theory of similarity. For its establishment, an analysis of the problems of different classes is conducted in order to identify common features (criteria) that determine their similarity. Using this property allows you to develop the same methods and algorithms for their solution. The problems of combinatorial optimization, as a rule, are similar of the argument of the objective function, and the problems of combinatorics are similar on the creating and arranging of combinatorial configurations. Due to this property, their sets are generated by the same algorithm or it modification.The article describes the criterias by which the similarity of dynamic problems relating to different classes is established. The problems of combinatorial optimization, in which in the process of their solution, the current information by which the result is evaluated is generated, and the search for an optimal solution is carried out in stages with the calculation of partial amounts of the objective function, is called dynamic. The main criterias of similarity to them is the change in the result of the solution in time and for its current reference, the need to calculate the partial objective function.The process of their solution is described by a directed acyclic graph, and the partial values of the objective function change over time and are calculated according to the recurrent rules. When finding their optimal values, the Bellman principle is followed. The revealed properties of similarity, which are characteristic of the problems of this class, determine their universality, through which they are solved by the same method. Typically, dynamic programming is used to solve these problems. The study and use of this property in combinatorial optimization in the future will allow solving insoluble problems for solvable ones. Examples of some dynamic combinatorial optimization problems are given У комбінаторній оптимізації можна навести багато прикладів, коли задачі з різних класів розв’язуються за однією і тією ж обчислювальною схемою. Це пов’язано з тим що оговореним задачам властива подібність, завдяки якій вони розв’язуються одним методом або модифікацією одного і того ж алгоритму. Вона відрізняється від геометричної та описаної в теорії подібності. Для її встановлення проводиться аналіз задач різних класів з метою виявлення спільних ознак (критеріїв), за якими визначається їхня подібність. Використання цієї властивості дозволяє розробляти однакові методи та алгоритми для їхнього розв’язання. Задачі комбінаторної оптимізації, як правило, подібні за аргументом цільової функції, а задачі з комбінаторики — за способом утворення та впорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією.У статті описано ознаки, за якими встановлюється подібність динамічних задач, що відносяться до різних класів. Задачі комбінаторної оптимізації, в яких у процесі їхнього розв'язання генерується поточна інформація, за якою оцінюється результат, а пошук оптимального розв'язку проводиться поетапно з обчисленням часткових сум цільової функції, названо динамічними. Основними ознаками подібності для них є зміна результату розв’язання в часі та для його поточного відліку необхідність обчислення часткової цільової функції. Процес їхнього розв’язання описується орієнтованим ациклічним графом, а часткові значення цільової функції змінюються в часі та обчислюються за рекурентними правилами. При знаходженні їхніх оптимальних значень виконується принцип Беллмана. Виявлені властивості подібності, які характерні для задач цього класу, визначають їхню універсальність, завдяки якій вони розв’язуються одним і тим же методом. Для розв’язання цих задач, як правило, використовують динамічне програмування. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити нерозв’язні задачі до розв’язних. Наведено приклади деяких динамічних задач комбінаторної оптимізації. Кам'янець-Подільський національний університет імені Івана Огієнка 2019-01-24 Article Article Рецензована Стаття application/pdf http://mcm-math.kpnu.edu.ua/article/view/174240 10.32626/2308-5878.2019-19.168-174 Mathematical and computer modelling. Series: Physical and mathematical sciences; 2019: Mathematical and computer modelling. Series: Physical and mathematical sciences. Issue 19; 168-174 Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки; 2019: Математичне та комп'ютерне моделювання. Серія: Фізико-математичні науки. Випуск 19; 168-174 2308-5878 10.32626/2308-5878.2019-19 uk http://mcm-math.kpnu.edu.ua/article/view/174240/174181 Авторське право (c) 2021 Надія Костянтинівна Тимофієва |