Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации
На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных. A class of polynomially solvable prob...
Збережено в:
| Опубліковано в: : | Кибернетика и системный анализ |
|---|---|
| Дата: | 2014 |
| Автори: | , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут кібернетики ім. В.М. Глушкова НАН України
2014
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/115729 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации / Г.А. Донец, И.В. Сергиенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 3-10. — Бібліогр.: 8 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862579504768090112 |
|---|---|
| author | Донец, Г.А. Сергиенко, И.В. |
| author_facet | Донец, Г.А. Сергиенко, И.В. |
| citation_txt | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации / Г.А. Донец, И.В. Сергиенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 3-10. — Бібліогр.: 8 назв. — рос. |
| collection | DSpace DC |
| container_title | Кибернетика и системный анализ |
| description | На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных.
A class of polynomially solvable problems of combinatorial optimization is treated. It is shown that this class includes certain problems with specially structured initial data. The reasoning is illustrated with the NP-hard traveling salesman problem.
На прикладі задачі про комівояжера розглянуто клас важкорозв’язних задач, які мають поліноміальний алгоритм розв’язання. Доведено, що цьому класу належать задачі, в яких спеціальним чином змодельована структура вхідних даних.
|
| first_indexed | 2025-11-26T19:03:47Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-115729 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| language | Russian |
| last_indexed | 2025-11-26T19:03:47Z |
| publishDate | 2014 |
| publisher | Інститут кібернетики ім. В.М. Глушкова НАН України |
| record_format | dspace |
| spelling | Донец, Г.А. Сергиенко, И.В. 2017-04-11T18:37:34Z 2017-04-11T18:37:34Z 2014 Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации / Г.А. Донец, И.В. Сергиенко // Кибернетика и системный анализ. — 2014. — Т. 50, № 1. — С. 3-10. — Бібліогр.: 8 назв. — рос. https://nasplib.isofts.kiev.ua/handle/123456789/115729 519.1 На примере задачи о коммивояжере рассмотрен класс труднорешаемых задач комбинаторной оптимизации, которые имеют полиномиальный алгоритм решения. Доказано, что этому классу принадлежат задачи, у которых специальным образом смоделирована структура исходных данных. A class of polynomially solvable problems of combinatorial optimization is treated. It is shown that this class includes certain problems with specially structured initial data. The reasoning is illustrated with the NP-hard traveling salesman problem. На прикладі задачі про комівояжера розглянуто клас важкорозв’язних задач, які мають поліноміальний алгоритм розв’язання. Доведено, що цьому класу належать задачі, в яких спеціальним чином змодельована структура вхідних даних. ru Інститут кібернетики ім. В.М. Глушкова НАН України Кибернетика и системный анализ Кибернетика Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации Method of initial data structure modeling and subclasses of solvable combinatorial optimization problems Метод моделювання структури вхідних даних та підкласи розв’язних задач комбінаторної оптимізації Article published earlier |
| spellingShingle | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации Донец, Г.А. Сергиенко, И.В. Кибернетика |
| title | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_alt | Method of initial data structure modeling and subclasses of solvable combinatorial optimization problems Метод моделювання структури вхідних даних та підкласи розв’язних задач комбінаторної оптимізації |
| title_full | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_fullStr | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_full_unstemmed | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_short | Метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| title_sort | метод моделирования структуры исходных данных и подклассы разрешимых задач комбинаторной оптимизации |
| topic | Кибернетика |
| topic_facet | Кибернетика |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/115729 |
| work_keys_str_mv | AT donecga metodmodelirovaniâstrukturyishodnyhdannyhipodklassyrazrešimyhzadačkombinatornoioptimizacii AT sergienkoiv metodmodelirovaniâstrukturyishodnyhdannyhipodklassyrazrešimyhzadačkombinatornoioptimizacii AT donecga methodofinitialdatastructuremodelingandsubclassesofsolvablecombinatorialoptimizationproblems AT sergienkoiv methodofinitialdatastructuremodelingandsubclassesofsolvablecombinatorialoptimizationproblems AT donecga metodmodelûvannâstrukturivhídnihdanihtapídklasirozvâznihzadačkombínatornoíoptimízacíí AT sergienkoiv metodmodelûvannâstrukturivhídnihdanihtapídklasirozvâznihzadačkombínatornoíoptimízacíí |