Про деякі властивості множини розв'язків задачі комівояжера
Для задачі комівояжера описано спосіб упорядкування маршрутів (відповідно і перестановок) підмножинами, який не залежить від структури вхідних даних певної задачі. Для одержаного упорядкування розроблено стратегію визначення тих підмножин, які містять глобальний розв’язок. Показано, що для подібних...
Збережено в:
| Опубліковано в: : | Управляющие системы и машины |
|---|---|
| Дата: | 2018 |
| Автор: | |
| Формат: | Стаття |
| Мова: | Ukrainian |
| Опубліковано: |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України
2018
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/161512 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Про деякі властивості множини розв'язків задачі комівояжера / Н.К. Тимофієва // Управляющие системы и машины. — 2018. — № 5. — С. 3–12. — Бібліогр.: 15 назв. — укр. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
nasplib_isofts_kiev_ua-123456789-161512 |
|---|---|
| record_format |
dspace |
| spelling |
Тимофієва, Н.К. 2019-12-12T21:09:41Z 2019-12-12T21:09:41Z 2018 Про деякі властивості множини розв'язків задачі комівояжера / Н.К. Тимофієва // Управляющие системы и машины. — 2018. — № 5. — С. 3–12. — Бібліогр.: 15 назв. — укр. DOI: https://doi.org/10.15407/usim.2018.05.003 0130-5395 https://nasplib.isofts.kiev.ua/handle/123456789/161512 519.816 Для задачі комівояжера описано спосіб упорядкування маршрутів (відповідно і перестановок) підмножинами, який не залежить від структури вхідних даних певної задачі. Для одержаного упорядкування розроблено стратегію визначення тих підмножин, які містять глобальний розв’язок. Показано, що для подібних структур глобальні мінімум та максимум знаходяться в одних і тих же підмножинах. Використання цієї властивості дозволяє звужувати область пошуку оптимального розв’язку. В данной статье разработана стратегия отсечения неэффективных решений, которая заключается в разбиении не множества значений целевой функции на подмножества, а в разбиении множества маршрутов задачи коммивояжера независимо от входной информации. Показано, что в зависимости от различных комбинаций элементов матрицы, которой задаются входные данные, множество маршрутов в задаче коммивояжера разделяется на одни и те же подмножества для различных индивидуальных задач с различной структурой входных данных. A strategy for eliminating ineffective solutions is developed, which consists on not splitting the objective function values into a subset, but the set of routes for the salesman problem independently of the input data. It is shown that the various combinations of the matrix elements, which is the input data, the set of routes for the salesman problem is divided into the same subset for different individual problems with different structure of input data. Accordingly, a similar set of subsets arranges a set of permutations. uk Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України Управляющие системы и машины Фундаментальные и прикладные проблемы Computer Science Про деякі властивості множини розв'язків задачі комівояжера О некоторых свойствах множества решений задачи коммивояжера On Some Properties of the Set of Solutions of the Salesman Problem Article published earlier |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| title |
Про деякі властивості множини розв'язків задачі комівояжера |
| spellingShingle |
Про деякі властивості множини розв'язків задачі комівояжера Тимофієва, Н.К. Фундаментальные и прикладные проблемы Computer Science |
| title_short |
Про деякі властивості множини розв'язків задачі комівояжера |
| title_full |
Про деякі властивості множини розв'язків задачі комівояжера |
| title_fullStr |
Про деякі властивості множини розв'язків задачі комівояжера |
| title_full_unstemmed |
Про деякі властивості множини розв'язків задачі комівояжера |
| title_sort |
про деякі властивості множини розв'язків задачі комівояжера |
| author |
Тимофієва, Н.К. |
| author_facet |
Тимофієва, Н.К. |
| topic |
Фундаментальные и прикладные проблемы Computer Science |
| topic_facet |
Фундаментальные и прикладные проблемы Computer Science |
| publishDate |
2018 |
| language |
Ukrainian |
| container_title |
Управляющие системы и машины |
| publisher |
Міжнародний науково-навчальний центр інформаційних технологій і систем НАН та МОН України |
| format |
Article |
| title_alt |
О некоторых свойствах множества решений задачи коммивояжера On Some Properties of the Set of Solutions of the Salesman Problem |
| description |
Для задачі комівояжера описано спосіб упорядкування маршрутів (відповідно і перестановок) підмножинами, який не залежить від структури вхідних даних певної задачі. Для одержаного упорядкування розроблено стратегію визначення тих підмножин, які містять глобальний розв’язок. Показано, що для подібних структур глобальні мінімум та максимум знаходяться в одних і тих же підмножинах. Використання цієї властивості дозволяє звужувати область пошуку оптимального розв’язку.
В данной статье разработана стратегия отсечения неэффективных решений, которая заключается в разбиении не множества значений целевой функции на подмножества, а в разбиении множества маршрутов задачи коммивояжера независимо от входной информации. Показано, что в зависимости от различных комбинаций элементов матрицы, которой задаются входные данные, множество маршрутов в задаче коммивояжера разделяется на одни и те же подмножества для различных индивидуальных задач с различной структурой входных данных.
A strategy for eliminating ineffective solutions is developed, which consists on not splitting the objective function values into a subset, but the set of routes for the salesman problem independently of the input data. It is shown that the various combinations of the matrix elements, which is the input data, the set of routes for the salesman problem is divided into the same subset for different individual problems with different structure of input data. Accordingly, a similar set of subsets arranges a set of permutations.
|
| isbn |
DOI: https://doi.org/10.15407/usim.2018.05.003 |
| issn |
0130-5395 |
| url |
https://nasplib.isofts.kiev.ua/handle/123456789/161512 |
| citation_txt |
Про деякі властивості множини розв'язків задачі комівояжера / Н.К. Тимофієва // Управляющие системы и машины. — 2018. — № 5. — С. 3–12. — Бібліогр.: 15 назв. — укр. |
| work_keys_str_mv |
AT timofíêvank prodeâkívlastivostímnožinirozvâzkívzadačíkomívoâžera AT timofíêvank onekotoryhsvoistvahmnožestvarešeniizadačikommivoâžera AT timofíêvank onsomepropertiesofthesetofsolutionsofthesalesmanproblem |
| first_indexed |
2025-12-01T11:32:45Z |
| last_indexed |
2025-12-01T11:32:45Z |
| _version_ |
1850860099427368960 |