Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера
Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН для полученной матрицы находится за время О(n²)....
Saved in:
| Date: | 2011 |
|---|---|
| Main Authors: | , , |
| Format: | Article |
| Language: | Russian |
| Published: |
Інститут проблем штучного інтелекту МОН України та НАН України
2011
|
| Series: | Штучний інтелект |
| Subjects: | |
| Online Access: | http://dspace.nbuv.gov.ua/handle/123456789/60487 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Journal Title: | Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| Cite this: | Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. |
Institution
Digital Library of Periodicals of National Academy of Sciences of Ukraine| id |
irk-123456789-60487 |
|---|---|
| record_format |
dspace |
| spelling |
irk-123456789-604872014-04-16T03:02:06Z Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера Левченко, А.Ю. Морозов, А.В. Панишев, А.В. Обучающие и экспертные системы Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка 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²). 2011 Article Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. 1561-5359 http://dspace.nbuv.gov.ua/handle/123456789/60487 519.161 ru Штучний інтелект Інститут проблем штучного інтелекту МОН України та НАН України |
| institution |
Digital Library of Periodicals of National Academy of Sciences of Ukraine |
| collection |
DSpace DC |
| language |
Russian |
| topic |
Обучающие и экспертные системы Обучающие и экспертные системы |
| spellingShingle |
Обучающие и экспертные системы Обучающие и экспертные системы Левченко, А.Ю. Морозов, А.В. Панишев, А.В. Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера Штучний інтелект |
| description |
Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка n заменить значение какого-либо элемента на бесконечно большое число, то оптимальное решение ЗН
для полученной матрицы находится за время О(n²). |
| format |
Article |
| author |
Левченко, А.Ю. Морозов, А.В. Панишев, А.В. |
| author_facet |
Левченко, А.Ю. Морозов, А.В. Панишев, А.В. |
| author_sort |
Левченко, А.Ю. |
| title |
Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_short |
Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_full |
Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_fullStr |
Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_full_unstemmed |
Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| title_sort |
быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера |
| publisher |
Інститут проблем штучного інтелекту МОН України та НАН України |
| publishDate |
2011 |
| topic_facet |
Обучающие и экспертные системы |
| url |
http://dspace.nbuv.gov.ua/handle/123456789/60487 |
| citation_txt |
Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера / А.Ю. Левченко, А.В. Морозов, А.В. Панишев // Штучний інтелект. — 2011. — № 4. — С. 406-416. — Бібліогр.: 4 назв. — рос. |
| series |
Штучний інтелект |
| work_keys_str_mv |
AT levčenkoaû bystryjalgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižnejgranicystoimostimaršrutakommivoâžera AT morozovav bystryjalgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižnejgranicystoimostimaršrutakommivoâžera AT paniševav bystryjalgoritmrešeniâzadačionaznačeniâhdlânahoždeniânižnejgranicystoimostimaršrutakommivoâžera |
| first_indexed |
2023-10-18T18:36:52Z |
| last_indexed |
2023-10-18T18:36:52Z |
| _version_ |
1796144689002315776 |