Аннотация:
Рассматривается трёхиндексная планарная $m$-слойная задача о назначениях на одноциклических подстановках, являющаяся в общем случае задачей $m$ коммивояжёров с различными весовыми функциями их маршрутов. Задача NP-трудна при $m\ge1$. Представлен приближённый полиномиальный алгоритм решения задачи при $1<m<n/4$. Алгоритм имеет временну́ю сложность $O(mn^2)$. Получены оценки качества его работы в случае, когда входные данные (элементы $(m\times n\times n)$-матрицы) являются независимыми случайными величинами с общей функцией равномерного распределения на отрезке $[a_n,b_n]$, где $0<a_n<b_n$. Получены условия асимптотической точности алгоритма, верные также в случае функции распределения мажорирующего типа. Ил. 1, библиогр. 26.
Ключевые слова:трёхиндексная планарная задача о назначениях, $m$-слойная задача на одноциклических подстановках, $m$-PSP с различными весовыми функциями, полиномиальный алгоритм, асимптотическая точность.
УДК:519.8
Статья поступила: 19.12.2012 Переработанный вариант: 29.03.2013