Линейная задача о назначениях в узких местах

Идея использования метода пороговых значений принадлежит Гарфинкелю (Garfinkel)[3].

Присваиваем начальные значения ${\displaystyle t_{\min }=\min _{i,j}{c_{i,j}},t_{\max }=\max _{i,j}{c_{i,j}}}$.
Если ${\displaystyle t_{\min }=t_{\max }}$, то
  оптимальное значение = ${\displaystyle t_{\min }}$ и любая перестановка {1, 2, . . . , n} оптимальна.
В противном случае, 
  пока существуют ${\displaystyle c_{i,j}:t_{\min }<c_{i,j}<t_{\max }}$, выполнить
    Находим медиану, t чисел ${\displaystyle t_{\min }<c_{i,j}<t_{\max }}$
    Строим граф ${\displaystyle T}$
    Если ${\displaystyle T}$ содержит совершенное паросочетание, то принимаем 
      ${\displaystyle t_{\min }=t}$
    иначе принимаем 
      ${\displaystyle t_{\max }=t}$ 
    конец если
  конец цикла
  Если проверка существования совершенного паросочетания для  ${\displaystyle t_{\min }}$ не выполнялась, выполним её.
  Строим граф ${\displaystyle T}$ для ${\displaystyle t_{\min }}$
  Если ${\displaystyle T}$ содержит совершенное паросочетание, принимаем
    ${\displaystyle t_{\max }=t_{\min }}$
  конец если
конец если

Оптимальное значение будет равно ${\displaystyle t_{\max }}$, и оптимальное решение можно найти из соответствующего графа.

Как видим, на каждом шаге цикла 'пороговый алгоритм' проходит два этапа. На первом этапе выбирается 'пороговое значение' ${\displaystyle t}$ и 'пороговая матрица' ${\displaystyle T}$, которая определяется следующим образом:

${\displaystyle T_{i,j}=}$

1, если ${\displaystyle c_{ij}>t}$

0 в противном случае.

На втором этапе проверяется, существует ли назначение с нулевой ценой (для матрицы цен ${\displaystyle T}$). Для проверки этого конструируется двудольный граф G = (U, V; E) с |U| = |V| = n и дуги ${\displaystyle [i,j]\in E}$ тогда и только тогда, когда ${\displaystyle T_{i,j}=0}$. (Другими словами, мы должны проверить, содержит ли двудольный граф, соответствующий пороговой матрице, совершенное паросочетание или нет). Минимальное пороговое значение ${\displaystyle t}$, для которого соответствующий двудольный граф содержит совершенное паросочетание, является оптимальным значением задачи. Существует несколько путей реализации порогового алгоритма. Одна из возможностей — использовать двоичный поиск на первом этапе. Это приведёт к ${\displaystyle O(M(n)\log(n))}$ алгоритму, где ${\displaystyle M(n)}$ — временна́я сложность проверки существования совершенного паросочетания. Мы можем использовать матричный алгоритм Ибарра и Морана[4] для выяснения, существует ли совершенное паросочетание. Тогда оптимальное решение может быть найдено с битовой сложностью ${\displaystyle O(n^{\beta }\log ^{k}n)}$. Для умножения двух n × n матриц нужно ${\displaystyle O(n^{\beta })}$ арифметических операций и k — некоторое целое число, возникающее из действий над длинными целыми числами. Копперсмит (Coppersmith) и Виноград (Winograd)[5] показали, что умножение матриц можно сделать с ${\displaystyle \beta =2{,}376}$. Если мы хотим получить соответствующее оптимальное решение, мы можем использовать метод Альта, Блюма, Мелхорна и Паула (Alt, Blum, Mehlhorn, Paul)[6] и получим полную сложность ${\displaystyle O\left(n^{2{,}5}\left/{\sqrt {\log(n)}}\right.\right)}$ в случае плотной матрицы. Здесь плотность означает, что число ненулевых элементов ${\displaystyle T_{i,j}}$ матрицы равно ${\displaystyle O(n^{2})}$.

Этот метод теоретически является лучшим из известных методов решения задачи.

Тесно связан с пороговым методом следующий двойственный алгоритм.

Вычислим ${\displaystyle t=\max _{k=1,2,\dots ,n}(\min _{r=1,2,\dots ,n}c_{r,k},\min _{j=1,2,\dots ,n}c_{k,j})}$
Положим ${\displaystyle M=\varnothing }$  (пустое множество).
Пока |M| < n, выполнять
  Определим двудольный граф G, соответствующий пороговому значению t.
  Найдем максимальное паросочетание в G.
  Если |M| < n, то
    Пусть ${\displaystyle R\subseteq U}$ и ${\displaystyle J\subseteq V}$ — множества вершин в минимальном покрытии графа G.
    Положим ${\displaystyle t=\min _{r\in R,j\in J}c_{r,j}}$
  конец если
конец цикла

Алгоритм использует некоторую информацию о пороговом значении t, а именно — тот факт, что оптимальное значение не может быть меньше максимального значения из минимальных элементов в строках, а также максимального значения из минимальных элементов в столбцах матрицы C. Таким образом, в качестве первого порогового значения можно взять ${\displaystyle t=\max _{1\leqslant k\leqslant n}(\min _{1\leqslant r\leqslant n}c_{r,k},\min _{1\leqslant j\leqslant n}c_{k,j})}$

Двойтвенный метод начинает с этого значения t и создаёт минимальные наборы (индексов) столбцов ${\displaystyle J}$ и строк ${\displaystyle R}$, покрывающие все элементы матрицы ${\displaystyle c_{r,j}\leqslant t}$. Это можно сделать, найдя максимальный набор дуг в графе G, задающих паросочетание. Здесь граф G — это двудольный граф с дугами (r,j), для которых ${\displaystyle c_{r,j}\leqslant t}$. Если паросочетание не содержит все строки и столбцы, существуют элементы матрицы, определяющие оптимальное значение, и эти элементы больше t. Вследствие этого, мы можем принять новое значение ${\displaystyle t=\min _{r\in R,j\in J}c_{r,j}}$ и построить новый граф G. Этот граф содержит все рёбра предыдущего графа и как минимум одно новое ребро, так что мы можем начать поиск максимального паросочетания с уже найденного на предыдущем шаге. Продолжаем, пока не найдём совершенное паросочетание.

Ещё одним подходом к решению задачи может служить использование идей венгерского метода[7]. В России этот метод известен под названием 'Алгоритм Гросса'. Изложим метод в реализации Деригса и Циммермана[8].

Введём несколько определений.

Дополняющим путём паросочетания называется путь, содержащий дуги паросочетания, при этом из двух соседних дуг одна обязательно принадлежит паросочетанию (т.е. дуги перемежаются — за дугой из паросочетания идёт дуга, не принадлежащая ему, и наоборот).

Пусть ${\displaystyle P=([i_{1},j_{1}],[i_{2},j_{1}],[i_{2},j_{2}],\dots ,[i_{k},j_{k}])}$ — дополняющий путь для паросочетания M.

Размер узкого места ${\displaystyle \ell (P)}$ определяется как

${\displaystyle \ell (P)=\max(c([i_{1},j_{1}]),c([i_{2},j_{2}]),\dots ,c([i_{k},j_{k}]))}$.

Дополняющий путь называется b-кратчайшим путём, если размер узкого места минимален среди всех дополняющих путей M.

Пусть ${\displaystyle G=(U,V;E)}$ — двудольный граф с длинами дуг ${\displaystyle c_{i,j}}$ для дуг ${\displaystyle [i,j]\in E}$
Найдем нижнюю границу t для целевой функции
     (т.е. ${\displaystyle t=\max {(\max _{u\in U}\min _{v\in V}c_{u,v},\max _{v\in V}\min _{u\in U}c_{u},v)}}$)
Находим максимальное паросочетание M в графе G, имеющего дуги [i, j] если ${\displaystyle c_{i,j}\leqslant t}$
если |M| = |U|, то мы получили оптимальное решение t с оптимальным отношением M, и завершаем работу.
конец если
Пусть L — множество элементов U, для которых нет паросочетания.
пока L не пусто, выполнить
  Выберем вершину ${\displaystyle i\in L}$
  Положим ${\displaystyle L=L\backslash \{i\}}$
  P = Dijkstra(i)
  Комментарий: Функция Dijkstra(i) возвращает дополняющий путь, начинающийся в вершине i
  Если путь не найден, то
    Положим ${\displaystyle M=M\ominus P}$
    Положим ${\displaystyle t=\max(t,\ell (P))}$
  конец если
конец пока
Комментарий: M — максимальное паросочетание с минимальной ценой t.

B-кратчайший дополняющий путь находится функцией Dijkstra().

Во время поиска b-кратчайшего пути помечаем вершину ${\displaystyle x\in U}$ значением ${\displaystyle ({\overline {\alpha }}(x),{\overline {\beta }}(x))}$, где ${\displaystyle {\overline {\alpha }}(x)}$ является размером узкого места b-кратчайшего пути из ${\displaystyle i_{1}}$ в эту вершину, а ${\displaystyle {\overline {\beta }}(x)}$ означает непосредственного предшественника в b-кратчайшем пути из ${\displaystyle i_{1}}$ в вершину ${\displaystyle x}$.

Аналогичным образом помечаем вершину ${\displaystyle x\in V}$ значением ${\displaystyle (\alpha (x),\beta (x))}$, где ${\displaystyle \alpha (x)}$ является размером узкого места b-кратчайшего пути из ${\displaystyle i_{1}}$ в эту вершину, а ${\displaystyle \beta (x)}$ означает непосредственного предшественника в b-кратчайшем пути из ${\displaystyle i_{1}}$ в вершину ${\displaystyle x}$.

Функция Dijkstra(i)
Комментарий: Модифицированный алгоритм Дейкстры для задачи о назначениях для узких мест.
Помечаем все вершины ${\displaystyle j\in V}$, положив ${\displaystyle (\alpha (j),\beta (j))=(\infty ,\varnothing )}$.
Положим R = V Комментарий: R содержит непросмотренные вершины V
α(i) = t, P = пусто
Для всех соседей ${\displaystyle j\in R}$ вершины i выполнить
  Если ${\displaystyle \alpha (j)>\max({\overline {\alpha }}(i),c_{i,j})}$, то
    Положим ${\displaystyle \alpha (j)=\max({\overline {\alpha }}(i),c_{i,j})}$
    ${\displaystyle \beta (j)=i}$
  конец если
конец цикла
пока R пусто, выполнять
  Найдём вершину ${\displaystyle r\in R}$ с минимальным ${\displaystyle \alpha (r)}$;
  Если ${\displaystyle \alpha (r)=\infty }$, то 
    Положим ${\displaystyle R=\varnothing }$
  иначе
    если r не входит в паросочетание, то
      Находим путь P, образованный последовательностью вершин ${\displaystyle (i,\dots ,{\overline {\beta }}(\beta (r)),\beta (r),r)}$
      Положим ${\displaystyle \ell (P)=\alpha (r)}$
      ${\displaystyle R=\varnothing }$
    Иначе
      Пусть [s, r] — ребро паросочетания
      Помечаем s: ${\displaystyle ({\overline {\alpha }}(s),{\overline {\beta }}(s))=(\alpha (r),r)}$
      Положим ${\displaystyle R=R\backslash \{r\}}$
      Для всех соседей ${\displaystyle j\in R}$ вершины s выполнить
        Если ${\displaystyle \alpha (j)>\max({\overline {\alpha }}(s),c_{s,j})}$, то
          Положим ${\displaystyle \alpha (j)=\max({\overline {\alpha }}(s),c_{s,j})}$
          ${\displaystyle \beta (j)=s}$
        конец если
      конец цикла
    конец если
  конец если
конец пока