Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН 
 для полученной матрицы находится за время О(n²). Показано, що якщо в оптимальному розв’язку за...
Збережено в:
| Опубліковано в: : | Штучний інтелект |
|---|---|
| Дата: | 2011 |
| Автори: | , , |
| Формат: | Стаття |
| Мова: | Російська |
| Опубліковано: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Теми: | |
| Онлайн доступ: | https://nasplib.isofts.kiev.ua/handle/123456789/60487 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Цитувати: | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. |
Репозитарії
Digital Library of Periodicals of National Academy of Sciences of Ukraine| _version_ | 1862545967746646016 |
|---|---|
| author | Левченко, А.Ю. Морозов, А.В. Панишев, А.В. |
| author_facet | Левченко, А.Ю. Морозов, А.В. Панишев, А.В. |
| citation_txt | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. |
| collection | DSpace DC |
| container_title | Штучний інтелект |
| description | Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН 
для полученной матрицы находится за время О(n²).
Показано, що якщо в оптимальному розв’язку задачі про призначення (ЗП) та її матриці вартостей порядку n замінити значення якого-небудь елемента на нескінченно велике число, то оптимальний розв’язок 
ЗП для отриманої матриці знаходиться за час О(n²).
It is shown that if to replace the value of any element by infinitely large number in the optimal solution for the problem of allocations and for its matrix of weights with size n, then the optimal solution of the problem 
of allocation for resulting matrix is found in a time О(n²).
|
| first_indexed | 2025-11-25T09:05:17Z |
| format | Article |
| fulltext | |
| id | nasplib_isofts_kiev_ua-123456789-60487 |
| institution | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| issn | 1561-5359 |
| language | Russian |
| last_indexed | 2025-11-25T09:05:17Z |
| publishDate | 2011 |
| publisher | Інститут проблем штучного інтелекту МОН України та НАН України |
| record_format | dspace |
| spelling | Левченко, А.Ю. Морозов, А.В. Панишев, А.В. 2014-04-15T18:26:39Z 2014-04-15T18:26:39Z 2011 Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. 1561-5359 https://nasplib.isofts.kiev.ua/handle/123456789/60487 519.161 Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН 
 для полученной матрицы находится за время О(n²). Показано, що якщо в оптимальному розв’язку задачі про призначення (ЗП) та її матриці вартостей порядку n замінити значення якого-небудь елемента на нескінченно велике число, то оптимальний розв’язок 
 ЗП для отриманої матриці знаходиться за час О(n²). It is shown that if to replace the value of any element by infinitely large number in the optimal solution for the problem of allocations and for its matrix of weights with size n, then the optimal solution of the problem 
 of allocation for resulting matrix is found in a time О(n²). ru Інститут проблем штучного інтелекту МОН України та НАН України Штучний інтелект Обучающие и экспертные системы Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера Швидкий алгоритм розв’язання задачі про призначення для знаходження нижньої межі вартості маршруту комівояжера Algorithm for Fast Solution of the Problem of Allocation for Lower Limit Weight of Salesman Route Article published earlier |
| spellingShingle | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера Левченко, А.Ю. Морозов, А.В. Панишев, А.В. Обучающие и экспертные системы |
| title | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_alt | Швидкий алгоритм розв’язання задачі про призначення для знаходження нижньої межі вартості маршруту комівояжера Algorithm for Fast Solution of the Problem of Allocation for Lower Limit Weight of Salesman Route |
| title_full | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_fullStr | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_full_unstemmed | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_short | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_sort | быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| topic | Обучающие и экспертные системы |
| topic_facet | Обучающие и экспертные системы |
| url | https://nasplib.isofts.kiev.ua/handle/123456789/60487 |
| work_keys_str_mv | AT levčenkoaû bystryialgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižneigranicystoimostimaršrutakommivoâžera AT morozovav bystryialgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižneigranicystoimostimaršrutakommivoâžera AT paniševav bystryialgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižneigranicystoimostimaršrutakommivoâžera AT levčenkoaû švidkiialgoritmrozvâzannâzadačípropriznačennâdlâznahodžennânižnʹoímežívartostímaršrutukomívoâžera AT morozovav švidkiialgoritmrozvâzannâzadačípropriznačennâdlâznahodžennânižnʹoímežívartostímaršrutukomívoâžera AT paniševav švidkiialgoritmrozvâzannâzadačípropriznačennâdlâznahodžennânižnʹoímežívartostímaršrutukomívoâžera AT levčenkoaû algorithmforfastsolutionoftheproblemofallocationforlowerlimitweightofsalesmanroute AT morozovav algorithmforfastsolutionoftheproblemofallocationforlowerlimitweightofsalesmanroute AT paniševav algorithmforfastsolutionoftheproblemofallocationforlowerlimitweightofsalesmanroute |