Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач
На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі комівояжера наближається...
Gespeichert in:
| Veröffentlicht in: | Управляющие системы и машины |
|---|---|
| Datum: | 2016 |
| 1. Verfasser: | |
| Format: | Artikel |
| Sprache: | Ukrainisch |
| Veröffentlicht: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2016
|
| Schlagworte: | |
| Online Zugang: | https://nasplib.isofts.kiev.ua/handle/123456789/113324 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Zitieren: | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач / Тимофієва Н.К. // Управляющие системы и машины. — 2016. — № 2. — С. 5-21, 27. — укр. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862546360475058176 |
|---|---|
| author | Тимофієва, Н.К. |
| author_facet | Тимофієва, Н.К. |
| citation_txt | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач / Тимофієва Н.К. // Управляющие системы и машины. — 2016. — № 2. — С. 5-21, 27. — укр. |
| collection | DSpace DC |
| container_title | Управляющие системы и машины |
| description | На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі комівояжера наближається до нуля, а збіжність методу найближчого сусіда та «жадібного» алгоритму залежить від структури вхідних даних.
На примере задачи коммивояжера с использованием подклассов разрешимых задач доказана сходимость методов, основанных на распознавании структуры входной информации. Показано, что сходимость последовательности решений, построенных методом структурно-алфавитного поиска для задачи коммивояжера приближается к нулю, а сходимость метода ближайшего соседа и «жадного» алгоритма зависит от структуры входных данных.
The proof of the approximate solutions convergence sequence to a global solution of the combinatorial optimization problem, which is based on a particular algorithm, is rather complicated problem. This is due to the fact that some classes of problems are unsolvable because of their computational complexity. A lot of researches are devoted to the problem of the methods and algorithms convergence within the mathematical programming. They enter the formal level features required and sufficient conditions for their convergence. The original way to prove some convergence combinatorial optimization methods, based on recognition of the structure of input data (structure-alphabetical search method nearest neighbor method, “greedy” algorithm) is presented. For this purpose, the subclasses of the traveling salesman problems is used. A sequence of the convergence solutions that are built specifically is proved. To assess the methods accuracy, which are decided on a set of permutations, the input data of combinatorial optimization problems defines the functions of the natural argument, one of which is combinatorial. This allows to define a set of values of the objective function for basic problem and to establish some error of interpretation algorithm. An solvable case for the traveling salesman problem is shown, in which the input data requires the linear combinatorial function for which analytically the global minimum and maximum are found. Using this case proves that the convergence of a solutions sequence built by the structural alphabet search for the traveling salesman problem is close to zero. The optimal solution for subclasses coincides with the global. The speed of the described method is polynomial of computational complexity. The convergence of the nearest neighbor method and of the “greedy” algorithm depends on the structure of input data. For some, the solution structures coincides with the global, while others may be far from optimal.
|
| first_indexed | 2025-11-25T10:01:28Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-113324 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 0130-5395 |
| language | Ukrainian |
| last_indexed | 2025-11-25T10:01:28Z |
| publishDate | 2016 |
| publisher | Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| record_format | dspace |
| spelling | Тимофієва, Н.К. 2017-02-06T15:04:11Z 2017-02-06T15:04:11Z 2016 Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач / Тимофієва Н.К. // Управляющие системы и машины. — 2016. — № 2. — С. 5-21, 27. — укр. 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/113324 519.816 На прикладі задачі комівояжера з використанням підкласів розв’язних задач доведено збіжність методів, які ґрунтуються на розпізнаванні структури вхідної інформації. Показано, що збіжність послідовності розв’язків, побудованих методом структурно-алфавітного пошуку для задачі комівояжера наближається до нуля, а збіжність методу найближчого сусіда та «жадібного» алгоритму залежить від структури вхідних даних. На примере задачи коммивояжера с использованием подклассов разрешимых задач доказана сходимость методов, основанных на распознавании структуры входной информации. Показано, что сходимость последовательности решений, построенных методом структурно-алфавитного поиска для задачи коммивояжера приближается к нулю, а сходимость метода ближайшего соседа и «жадного» алгоритма зависит от структуры входных данных. The proof of the approximate solutions convergence sequence to a global solution of the combinatorial optimization problem, which is based on a particular algorithm, is rather complicated problem. This is due to the fact that some classes of problems are unsolvable because of their computational complexity. A lot of researches are devoted to the problem of the methods and algorithms convergence within the mathematical programming. They enter the formal level features required and sufficient conditions for their convergence. The original way to prove some convergence combinatorial optimization methods, based on recognition of the structure of input data (structure-alphabetical search method nearest neighbor method, “greedy” algorithm) is presented. For this purpose, the subclasses of the traveling salesman problems is used. A sequence of the convergence solutions that are built specifically is proved. To assess the methods accuracy, which are decided on a set of permutations, the input data of combinatorial optimization problems defines the functions of the natural argument, one of which is combinatorial. This allows to define a set of values of the objective function for basic problem and to establish some error of interpretation algorithm. An solvable case for the traveling salesman problem is shown, in which the input data requires the linear combinatorial function for which analytically the global minimum and maximum are found. Using this case proves that the convergence of a solutions sequence built by the structural alphabet search for the traveling salesman problem is close to zero. The optimal solution for subclasses coincides with the global. The speed of the described method is polynomial of computational complexity. The convergence of the nearest neighbor method and of the “greedy” algorithm depends on the structure of input data. For some, the solution structures coincides with the global, while others may be far from optimal. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы информатики и информационных технологий Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач Доказательство сходимости алгоритмов комбинаторной оптимизации с использованием подклассов разрешаемых задач The Proof of the Algorithms Convergence for Combinatorial Optimization with the Using Subclasses of the Solved Problems Article published earlier |
| spellingShingle | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач Тимофієва, Н.К. Фундаментальные и прикладные проблемы информатики и информационных технологий |
| title | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач |
| title_alt | Доказательство сходимости алгоритмов комбинаторной оптимизации с использованием подклассов разрешаемых задач The Proof of the Algorithms Convergence for Combinatorial Optimization with the Using Subclasses of the Solved Problems |
| title_full | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач |
| title_fullStr | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач |
| title_full_unstemmed | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач |
| title_short | Доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач |
| title_sort | доведення збіжності алгоритмів комбінаторної оптимізації з використанням підкласів розв’язних задач |
| topic | Фундаментальные и прикладные проблемы информатики и информационных технологий |
| topic_facet | Фундаментальные и прикладные проблемы информатики и информационных технологий |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/113324 |
| work_keys_str_mv | AT timofíêvank dovedennâzbížnostíalgoritmívkombínatornoíoptimízacíízvikoristannâmpídklasívrozvâznihzadač AT timofíêvank dokazatelʹstvoshodimostialgoritmovkombinatornoioptimizaciisispolʹzovaniempodklassovrazrešaemyhzadač AT timofíêvank theproofofthealgorithmsconvergenceforcombinatorialoptimizationwiththeusingsubclassesofthesolvedproblems |