Про подібність задач комбінаторної оптимизації та універсальність алгоритмів

Про подібність задач комбінаторної оптимизації та універсальність алгоритмів

A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of o...

Повний опис

Збережено в:
Бібліографічні деталі
Видавець:The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
Дата:2013
Автор: Timofeeva, N. K.
Формат: Стаття
Мова:Ukrainian
Опубліковано: The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013
Онлайн доступ:http://journal.iasa.kpi.ua/article/view/33639
Теги: Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!

Репозиторії

System research and information technologies
id journaliasakpiua-article-33639
record_format ojs
spelling journaliasakpiua-article-336392014-12-22T16:59:47Z On the similarity of combinatorial optimization and universality of the algorithms О подобии задач комбинаторной оптимизации и универсальности алгоритмов Про подібність задач комбінаторної оптимизації та універсальність алгоритмів Timofeeva, N. K. A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of objective function, and in combinatorics – by the method of formation and ordering of combinatorial configurations, are described. Due to this property their sets are generated by the same algorithm or its modification. It is shown that some combinatorial optimization problems, which belong to different classes are divided into similar subproblems that are solved by the same calculable scheme. The property of similarity, which is typical for this class of problems, determines their universality by which they are solved by the same method. A study and use of this property in the combinatorial optimization in the future will reduce the insoluble problems to the solvables. Рассмотрено свойство подобия, которое имеет место в комбинаторике и комбинаторной оптимизации. Выявлены различные признаки, по которым оно определяется для задач, относящихся к разным классам. Описаны задачи комбинаторной оптимизации, которые подобны по аргументу целевой функции, а в комбинаторике — по способу образования и упорядочения комбинаторных конфигураций. Благодаря этому свойству их множества генерируются одним и тем же алгоритмом или его модификацией. Показано, что некоторые задачи комбинаторной оптимизации, относящиеся к разным классам, разделяются на подобные подзадачи, решаемые по одной вычислительной схеме. Свойство подобия, которое характерно для задач этого класса, определяет их универсальность, благодаря которой они решаются одним и тем же методом. Изучение и использование этого свойства в комбинаторной оптимизации в дальнейшем позволит сводить неразрешимые задачи к разрешимым. Розглянуто властивість подібності, яка має місце в комбінаториці та комбінаторній оптимізації. Виявлено різноманітні ознаки, за якими вона визначається для задач, що відносяться до різних класів. Описано задачі комбінаторної оптимізації, які подібні за аргументом цільової функції, а в комбінаториці — за способом утворення та упорядкування комбінаторних конфігурацій. Завдяки цій властивості їхні множини генеруються одним і тим же алгоритмом або його модифікацією. Показано, що деякі задачі комбінаторної оптимізації, що відносяться до різних класів, розділяються на подібні підзадачі, які розв’язуються за однією обчислювальною схемою. Властивість подібності, яка характерна для задач цього класу, визначає їхню універсальність, завдяки якій вони розв’язуються за одним і тим же методом. Вивчення та використання цієї властивості в комбінаторній оптимізації в подальшому дозволить зводити нерозв’язні задачі до розв’язних. The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute" 2013-12-16 Article Article application/pdf http://journal.iasa.kpi.ua/article/view/33639 System research and information technologies; No. 4 (2013); 27-37 Системные исследования и информационные технологии; № 4 (2013); 27-37 Системні дослідження та інформаційні технології; № 4 (2013); 27-37 2308-8893 1681-6048 uk http://journal.iasa.kpi.ua/article/view/33639/30234 Copyright (c) 2021 System research and information technologies
institution System research and information technologies
collection OJS
language Ukrainian
format Article
author Timofeeva, N. K.
spellingShingle Timofeeva, N. K.
Про подібність задач комбінаторної оптимизації та універсальність алгоритмів
author_facet Timofeeva, N. K.
author_sort Timofeeva, N. K.
title Про подібність задач комбінаторної оптимизації та універсальність алгоритмів
title_short Про подібність задач комбінаторної оптимизації та універсальність алгоритмів
title_full Про подібність задач комбінаторної оптимизації та універсальність алгоритмів
title_fullStr Про подібність задач комбінаторної оптимизації та універсальність алгоритмів
title_full_unstemmed Про подібність задач комбінаторної оптимизації та універсальність алгоритмів
title_sort про подібність задач комбінаторної оптимизації та універсальність алгоритмів
title_alt On the similarity of combinatorial optimization and universality of the algorithms
О подобии задач комбинаторной оптимизации и универсальности алгоритмов
description A property of similarity which takes place in combinatorics and combinatorial optimization is examined. The various signs, after which it is determined for problems, which belong to the different classes, are defined. The problems of combinatorial optimization, which are similar by the argument of objective function, and in combinatorics – by the method of formation and ordering of combinatorial configurations, are described. Due to this property their sets are generated by the same algorithm or its modification. It is shown that some combinatorial optimization problems, which belong to different classes are divided into similar subproblems that are solved by the same calculable scheme. The property of similarity, which is typical for this class of problems, determines their universality by which they are solved by the same method. A study and use of this property in the combinatorial optimization in the future will reduce the insoluble problems to the solvables.
publisher The National Technical University of Ukraine "Igor Sikorsky Kyiv Polytechnic Institute"
publishDate 2013
url http://journal.iasa.kpi.ua/article/view/33639
work_keys_str_mv AT timofeevank onthesimilarityofcombinatorialoptimizationanduniversalityofthealgorithms
AT timofeevank opodobiizadačkombinatornojoptimizaciiiuniversalʹnostialgoritmov
AT timofeevank propodíbnístʹzadačkombínatornoíoptimizacíítauníversalʹnístʹalgoritmív
first_indexed 2024-04-08T15:03:53Z
last_indexed 2024-04-08T15:03:53Z
_version_ 1795779339601575936

Схожі ресурси