Быстрый алгоритм решения задачи о назначениях для нахождения нижней границы стоимости маршрута коммивояжера

• Опубліковано в: : Штучний інтелект
• Дата: 2011
• Автори: Левченко, А.Ю., Морозов, А.В., Панишев, А.В.
• Формат: Стаття
• Мова: Russian
• Опубліковано: Інститут проблем штучного інтелекту МОН України та НАН України 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 назв. — рос.

Показано, что если в оптимальном решении задачи о назначениях (ЗН) и ее матрице стоимостей порядка 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²).