Венгерский алгоритм

Венгерский метод — это комбинаторной оптимизации алгоритм , который решает задачу назначения за полиномиальное время и который предвосхитил более поздние методы просто-двойственности . Он был разработан и опубликован в 1955 году Гарольдом Куном , который дал ему название «Венгерский метод», поскольку алгоритм во многом основывался на более ранних работах двух венгерских математиков, Денеша Кенига и Йене Эгервари . Однако в 2006 году было обнаружено, что Карл Густав Якоби решил проблему назначения в 19 веке, и это решение было опубликовано посмертно в 1890 году на латыни.

Джеймс Манкрес рассмотрел алгоритм в 1957 году и заметил, что он (строго) полиномиален . С тех пор этот алгоритм известен также как алгоритм Куна-Мункреса или алгоритм назначения Манкреса . Временная сложность исходного алгоритма составляла $O(n^{4})$, однако Эдмондс , Карп и независимо Томизава заметили, что его можно модифицировать для достижения $O(n^{3})$ время бега. Форд и Фулкерсон распространили этот метод на общие задачи максимального потока в форме алгоритма Форда – Фулкерсона .

Проблема

Основная статья: Задача о назначениях

Пример

В этом простом примере есть три работника: Алиса, Боб и Кэрол. Один из них должен мыть ванную, другой подметать полы, а третий моет окна, но каждый из них требует разной оплаты за разные задачи. Проблема состоит в том, чтобы найти наименее затратный способ распределения заданий. Проблему можно представить в виде матрицы затрат работников, выполняющих работу. Например:

Задача Рабочий	Чистый ванная комната	Мести полы	Стирать окна
Алиса	$8	$4	$7
Боб	$5	$2	$3
Кэрол	$9	$4	$8

Венгерский метод, примененный к приведенной выше таблице, даст минимальные затраты: это 15 долларов, которые достигаются за счет того, что Алиса убирает ванную, Кэрол подметает полы, а Боб моет окна. Это можно подтвердить с помощью грубой силы:

Чистый Мести	Алиса	Боб	Кэрол
Алиса	—	$17	$16
Боб	$18	—	$18
Кэрол	$15	$16	—

(неназначенный человек моет окна)

Формулировка матрицы

В матричной формулировке нам дана размера n × n матрица , где элемент в i -й строке и j -м столбце представляет стоимость назначения j -го задания i -му работнику. Нам нужно найти распределение работ между работниками так, чтобы каждая работа была назначена одному работнику, а каждому работнику была назначена одна работа, так, чтобы общая стоимость назначения была минимальной.

Это можно выразить как перестановку строк матрицы стоимости C для минимизации следа матрицы:

$\min _{P}\operatorname {Tr} (PC)\;,$

где P — матрица перестановок . (Точно так же столбцы можно переставлять с помощью CP .)

Если цель состоит в том, чтобы найти назначение, которое дает максимальную стоимость, проблему можно решить путем отрицания матрицы стоимости C .

Формулировка двудольного графа

Алгоритм эквивалентно можно описать, сформулировав задачу с использованием двудольного графа. Имеем полный двудольный граф $G=(S,T;E)$ с n рабочими вершинами ( S ) и n рабочими вершинами ( T ), и каждое ребро ( E ) имеет стоимость $c(i,j)$. Мы хотим найти идеальное сочетание с минимальной общей стоимостью.

Алгоритм в терминах двудольных графов

Давайте вызовем функцию $y:(S\cup T)\to \mathbb {R}$ потенциал , если $y(i)+y(j)\leq c(i,j)$ для каждого $i\in S,j\in T$. Значение представляет собой потенциала y сумму потенциала по всем вершинам: $\sum _{v\in S\cup T}y(v)$.

Стоимость каждого идеального паросочетания равна, по крайней мере, значению каждого потенциала: общая стоимость паросочетания равна сумме стоимостей всех ребер; стоимость каждого ребра равна как минимум сумме потенциалов его концов; поскольку сопоставление идеальное, каждая вершина является конечной точкой ровно одного ребра; следовательно, общая стоимость равна, по крайней мере, общему потенциалу.

Венгерский метод находит идеальное совпадение и потенциал, при котором стоимость сопоставления равна потенциальному значению. Это доказывает, что оба они оптимальны. Фактически, венгерский метод находит идеальное совпадение узких ребер : ребро $ij$ называется тесным для потенциала y, если $y(i)+y(j)=c(i,j)$. Обозначим подграф узких через ребер $G_{y}$. Стоимость идеального соответствия в $G_{y}$ (если он есть) равен значению y .

В ходе алгоритма мы поддерживаем y и ориентацию потенциал $G_{y}$ (обозначается ${\overrightarrow {G_{y}}}$), которое обладает тем свойством, что ребра, ориентированные от к S , образуют паросочетание M. T Изначально y везде равен 0, и все ребра ориентированы от S к T (поэтому M пусто). На каждом шаге мы либо изменяем y , чтобы его значение увеличивалось, либо изменяем ориентацию, чтобы получить паросочетание с большим количеством ребер. Мы сохраняем инвариант, что все ребра M узкие. Мы закончили, если M — идеальное паросочетание.

На общем этапе пусть $R_{S}\subseteq S$ и $R_{T}\subseteq T$ — вершины, не покрытые M (так что $R_{S}$ состоит из вершин в S без входящего ребра и $R_{T}$ состоит из вершин из T без выходящего ребра). Пусть Z — множество вершин, достижимых в ${\overrightarrow {G_{y}}}$ от $R_{S}$ по направленному пути. Это можно вычислить с помощью поиска в ширину .

Если $R_{T}\cap Z$ непусто, то измените ориентацию всех ребер вдоль направленного пути в ${\overrightarrow {G_{y}}}$ от $R_{S}$ к $R_{T}$. Таким образом, размер соответствующего паросочетания увеличивается на 1.

Если $R_{T}\cap Z$ пусто, то пусть

$\Delta :=\min\{c(i,j)-y(i)-y(j):i\in Z\cap S,j\in T\setminus Z\}.$

Δ корректно определен, поскольку хотя бы одно такое ребро $ij$ должно существовать всякий раз, когда соответствие еще не достигло максимально возможного размера (см. следующий раздел); оно положительно, потому что между ними нет резких границ. $Z\cap S$ и $T\setminus Z$. Увеличить y на Δ в вершинах $Z\cap S$ и уменьшим y на Δ в вершинах $Z\cap T$. Полученный y по-прежнему является потенциалом, и хотя график $G_{y}$ изменяется, он по-прежнему содержит M (см. следующие подразделы). Ориентируем новые ребра S к T. от По определению ∆ множество Z вершин, достижимых из $R_{S}$ увеличивается (обратите внимание, что количество узких ребер не обязательно увеличивается).

Мы повторяем эти шаги до тех пор, пока M не станет идеальным паросочетанием, и в этом случае оно дает назначение минимальной стоимости. Время работы этой версии метода $O(n^{4})$: M увеличивается n раз, и в фазе, где M остается неизменным, происходит не более n потенциальных изменений (поскольку Z увеличивается каждый раз). Время, достаточное для потенциального изменения, равно $O(n^{2})$.

Доказательство того, что алгоритм прогрессирует

Мы должны показать, что до тех пор, пока размер совпадения не достигает максимально возможного, алгоритм всегда способен добиться прогресса — то есть либо увеличить количество совпадающих ребер, либо сузить хотя бы одно ребро. Достаточно показать, что на каждом шаге выполняется хотя бы одно из следующих утверждений:

• M имеет максимально возможный размер.
• $G_{y}$ содержит дополняющий путь.
• G содержит путь со свободным хвостом : путь из некоторой вершины в $R_{S}$ в вершину в $T\setminus Z$ который состоит из любого количества (возможно, нуля) узких ребер, за которыми следует одно свободное ребро. Таким образом, задний свободный край пути со свободным хвостом исходит из $Z\cap S$, гарантируя, что ∆ корректно определена.

Если M имеет максимально возможный размер, мы, конечно, закончили. В противном случае, по лемме Бержа должен существовать дополняющий путь P относительно M в базовом графе G. , Однако этот путь может не существовать в $G_{y}$: Хотя каждое ребро с четным номером в P является плотным по определению M , ребра с нечетными номерами могут быть свободными и, следовательно, отсутствовать в $G_{y}$. Одна конечная точка P находится в $R_{S}$, другой в $R_{T}$; wlog, предположим, что он начинается в $R_{S}$. Если каждое ребро на P узкое, то оно остается увеличивающим путем в $G_{y}$ и мы закончили. В противном случае, пусть $uv$ быть первым свободным ребром на P . Если $v\notin Z$ тогда мы нашли свободный путь и все готово. В противном случае v достижима по некоторому другому пути Q с узкими ребрами из вершины в $R_{S}$. Позволять $P_{v}$ — подпуть P , начинающийся с v и продолжающийся до конца, и пусть $P'$ — путь, образованный путешествием по Q до вершины на $P_{v}$ достигается, а затем продолжается до конца $P_{v}$. Обратите внимание, что $P'$ — расширяющий путь в G по крайней мере, на одно свободное ребро меньше, чем у P. , П можно заменить на $P'$ и этот процесс рассуждений повторялся (формально, с использованием индукции по числу свободных ребер) до тех пор, пока не возникнет увеличивающий путь в $G_{y}$ путь со свободным хвостом в G. или найден

Доказательство того, что корректировка потенциала y оставляет M неизменным.

Чтобы показать, что каждое ребро в M остается после корректировки y , достаточно показать, что для произвольного ребра в либо обе его конечные точки, либо ни одна из них не находятся в Z. M С этой целью пусть $vu$ быть ребром в M от T до S . Легко понять, что если v находится в Z, то и u тоже должно быть, поскольку каждое ребро в M узкое. Теперь предположим, в сторону противоречия, что $u\in Z$ но $v\notin Z$. ты сам не можешь быть внутри $R_{S}$ потому что это конечная точка совмещенного ребра, поэтому должен существовать некоторый направленный путь узких ребер из вершины в $R_{S}$ тебе ​ . Этот путь должен избегать v , поскольку по предположению он не находится в Z , поэтому вершина, непосредственно предшествующая u на этом пути, является какой-то другой вершиной. $v'\in T$. $v'u$ является плотным ребром из T в S и, таким образом, находится в M . Но тогда M содержит два ребра, которые имеют общую вершину u , что противоречит тому факту, что M является паросочетанием. каждое ребро в M имеет либо оба конца, либо ни одного конца в Z. Таким образом ,

Доказательство того, что y остается потенциальным

Чтобы показать, что y остается потенциалом после корректировки, достаточно показать, что ни у одного ребра общий потенциал не увеличился за пределы его стоимости. это уже установлено Для ребер в M в предыдущем абзаце, поэтому рассмотрим произвольное uv из S в T. ребро Если $y(u)$ увеличивается на Δ , то либо $v\in Z\cap T$, в этом случае $y(v)$ уменьшается на Δ , оставляя общий потенциал края неизменным, или $v\in T\setminus Z$, и в этом случае определение ∆ гарантирует, что $y(u)+y(v)+\Delta \leq c(u,v)$. Таким образом, y остается потенциалом.

Алгоритм за O ( n ³ ) время

Предположим, есть $J$ рабочие места и $W$ рабочие ( $J\leq W$). Мы описываем, как вычислить для каждого префикса заданий минимальную общую стоимость назначения каждого из этих заданий отдельным работникам. В частности, мы добавляем $j$задание и своевременно обновлять общую стоимость $O(jW)$, что дает общую временную сложность $O\left(\sum _{j=1}^{J}jW\right)=O(J^{2}W)$. Обратите внимание, что это лучше, чем $O(W^{3})$ когда количество рабочих мест невелико по сравнению с числом рабочих.

Добавление j-го задания за время O ( jW )

Мы используем те же обозначения, что и в предыдущем разделе, хотя при необходимости модифицируем их определения. Позволять $S_{j}$ обозначим множество первых $j$ рабочие места и $T$ обозначаем множество всех рабочих.

Перед $j$На шаге алгоритма мы предполагаем, что у нас есть паросочетание на $S_{j-1}\cup T$ который соответствует всем вакансиям в $S_{j-1}$ и потенциалы $y$ удовлетворяющее следующему условию: согласование строго по потенциалам, потенциалы всех несовпадающих рабочих равны нулю, а потенциалы всех согласованных рабочих неположительны. Заметим, что такие потенциалы свидетельствуют об оптимальности согласования.

Во время $j$шаге, мы добавляем $j$эта работа $S_{j-1}$ формировать $S_{j}$ и инициализировать $Z=\{j\}$. Всегда каждая вершина в $Z$ будет доступен из $j$эта работа в $G_{y}$. Пока $Z$ не содержит работника, которому не назначена работа, пусть

$\Delta :=\min\{c(j,w)-y(j)-y(w):j\in Z\cap S_{j},w\in T\setminus Z\}$

и $w_{\text{next}}$ обозначать любой $w$ при котором достигается минимум. После регулировки потенциалов способом, описанным в предыдущем разделе, теперь имеется узкая граница $Z$ к $w_{\text{next}}$.

• Если $w_{\text{next}}$ не имеет сопоставления, то мы имеем дополняющий путь в подграфе узких ребер из $j$ к $w_{\text{next}}$. После переключения сопоставления по этому пути мы теперь сопоставили первый $j$ рабочих мест, и эта процедура завершается.
• В противном случае мы добавляем $w_{\text{next}}$ и работа, соответствующая этому, чтобы $Z$.

Корректировка потенциалов занимает $O(W)$ время. Пересчет $\Delta$ и $w_{\text{next}}$ после изменения потенциалов и $Z$ также можно сделать в $O(W)$ время. Случай 1 может произойти не более $j-1$ раз до того, как произойдет случай 2, и процедура завершится, что дает общую временную сложность $O(jW)$.

Реализация на C++

Для удобства реализации в коде ниже добавлен дополнительный рабочий $w_{W}$ такой, что $y(w_{W})$ хранит отрицание суммы всех $\Delta$ вычислено до сих пор. После $j$добавлено задание и обновлено сопоставление, стоимость текущего сопоставления равна сумме всех $\Delta$ вычислено на данный момент, или $-y(w_{W})$.

Этот код адаптирован из e-maxx::algo.

/**
 * Solution to https://open.kattis.com/problems/cordonbleu using Hungarian
 * algorithm.
 */

#include <cassert>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;

/**
 * Sets a = min(a, b)
 * @return true if b < a
 */
template <class T> bool ckmin(T &a, const T &b) { return b < a ? a = b, 1 : 0; }

/**
 * Given J jobs and W workers (J <= W), computes the minimum cost to assign each
 * prefix of jobs to distinct workers.
 *
 * @tparam T a type large enough to represent integers on the order of J *
 * max(|C|)
 * @param C a matrix of dimensions JxW such that C[j][w] = cost to assign j-th
 * job to w-th worker (possibly negative)
 *
 * @return a vector of length J, with the j-th entry equaling the minimum cost
 * to assign the first (j+1) jobs to distinct workers
 */
template <class T> vector<T> hungarian(const vector<vector<T>> &C) {
    const int J = (int)size(C), W = (int)size(C[0]);
    assert(J <= W);
    // job[w] = job assigned to w-th worker, or -1 if no job assigned
    // note: a W-th worker was added for convenience
    vector<int> job(W + 1, -1);
    vector<T> ys(J), yt(W + 1);  // potentials
    // -yt[W] will equal the sum of all deltas
    vector<T> answers;
    const T inf = numeric_limits<T>::max();
    for (int j_cur = 0; j_cur < J; ++j_cur) {  // assign j_cur-th job
        int w_cur = W;
        job[w_cur] = j_cur;
        // min reduced cost over edges from Z to worker w
        vector<T> min_to(W + 1, inf);
        vector<int> prv(W + 1, -1);  // previous worker on alternating path
        vector<bool> in_Z(W + 1);    // whether worker is in Z
        while (job[w_cur] != -1) {   // runs at most j_cur + 1 times
            in_Z[w_cur] = true;
            const int j = job[w_cur];
            T delta = inf;
            int w_next;
            for (int w = 0; w < W; ++w) {
                if (!in_Z[w]) {
                    if (ckmin(min_to[w], C[j][w] - ys[j] - yt[w]))
                        prv[w] = w_cur;
                    if (ckmin(delta, min_to[w])) w_next = w;
                }
            }
            // delta will always be nonnegative,
            // except possibly during the first time this loop runs
            // if any entries of C[j_cur] are negative
            for (int w = 0; w <= W; ++w) {
                if (in_Z[w]) ys[job[w]] += delta, yt[w] -= delta;
                else min_to[w] -= delta;
            }
            w_cur = w_next;
        }
        // update assignments along alternating path
        for (int w; w_cur != W; w_cur = w) job[w_cur] = job[w = prv[w_cur]];
        answers.push_back(-yt[W]);
    }
    return answers;
}

/**
 * Sanity check: https://en.wikipedia.org/wiki/Hungarian_algorithm#Example
 * First job (5):
 *   clean bathroom: Bob -> 5
 * First + second jobs (9):
 *   clean bathroom: Bob -> 5
 *   sweep floors: Alice -> 4
 * First + second + third jobs (15):
 *   clean bathroom: Alice -> 8
 *   sweep floors: Carol -> 4
 *   wash windows: Bob -> 3
 */
void sanity_check_hungarian() {
    vector<vector<int>> costs{{8, 5, 9}, {4, 2, 4}, {7, 3, 8}};
    assert((hungarian(costs) == vector<int>{5, 9, 15}));
    cerr << "Sanity check passed.\n";
}

// solves https://open.kattis.com/problems/cordonbleu
void cordon_bleu() {
    int N, M;
    cin >> N >> M;
    vector<pair<int, int>> B(N), C(M);
    vector<pair<int, int>> bottles(N), couriers(M);
    for (auto &b : bottles) cin >> b.first >> b.second;
    for (auto &c : couriers) cin >> c.first >> c.second;
    pair<int, int> rest;
    cin >> rest.first >> rest.second;
    vector<vector<int>> costs(N, vector<int>(N + M - 1));
    auto dist = [&](pair<int, int> x, pair<int, int> y) {
        return abs(x.first - y.first) + abs(x.second - y.second);
    };
    for (int b = 0; b < N; ++b) {
        for (int c = 0; c < M; ++c) {  // courier -> bottle -> restaurant
            costs[b][c] =
                dist(couriers[c], bottles[b]) + dist(bottles[b], rest);
        }
        for (int _ = 0; _ < N - 1; ++_) {  // restaurant -> bottle -> restaurant
            costs[b][_ + M] = 2 * dist(bottles[b], rest);
        }
    }
    cout << hungarian(costs).back() << "\n";
}

int main() {
    sanity_check_hungarian();
    cordon_bleu();
}

Соединение с последовательными кратчайшими путями

Венгерский алгоритм можно рассматривать как эквивалент последовательного алгоритма кратчайшего пути для потока с минимальной стоимостью: метод повторного взвешивания из алгоритма Джонсона где для поиска кратчайших путей используется . Реализация из предыдущего раздела ниже переписана таким образом, чтобы подчеркнуть это. связь; можно проверить, что потенциалы $h$ для рабочих $0\dots W-1$ равны потенциалам $y$ от предыдущего решения до постоянного смещения. Когда граф разреженный (есть только $M$ разрешенная работа, рабочие пары), возможно оптимизировать этот алгоритм для запуска $O(JM+J^{2}\log W)$ время, используя кучу Фибоначчи для определения $w_{\text{next}}$ вместо того, чтобы перебирать все $W$ работники должны найти тот, который находится на минимальном расстоянии (упоминается здесь ).

template <class T> vector<T> hungarian(const vector<vector<T>> &C) {
    const int J = (int)size(C), W = (int)size(C[0]);
    assert(J <= W);
    // job[w] = job assigned to w-th worker, or -1 if no job assigned
    // note: a W-th worker was added for convenience
    vector<int> job(W + 1, -1);
    vector<T> h(W);  // Johnson potentials
    vector<T> answers;
    T ans_cur = 0;
    const T inf = numeric_limits<T>::max();
    // assign j_cur-th job using Dijkstra with potentials
    for (int j_cur = 0; j_cur < J; ++j_cur) {
        int w_cur = W;  // unvisited worker with minimum distance
        job[w_cur] = j_cur;
        vector<T> dist(W + 1, inf);  // Johnson-reduced distances
        dist[W] = 0;
        vector<bool> vis(W + 1);     // whether visited yet
        vector<int> prv(W + 1, -1);  // previous worker on shortest path
        while (job[w_cur] != -1) {   // Dijkstra step: pop min worker from heap
            T min_dist = inf;
            vis[w_cur] = true;
            int w_next = -1;  // next unvisited worker with minimum distance
            // consider extending shortest path by w_cur -> job[w_cur] -> w
            for (int w = 0; w < W; ++w) {
                if (!vis[w]) {
                    // sum of reduced edge weights w_cur -> job[w_cur] -> w
                    T edge = C[job[w_cur]][w] - h[w];
                    if (w_cur != W) {
                        edge -= C[job[w_cur]][w_cur] - h[w_cur];
                        assert(edge >= 0);  // consequence of Johnson potentials
                    }
                    if (ckmin(dist[w], dist[w_cur] + edge)) prv[w] = w_cur;
                    if (ckmin(min_dist, dist[w])) w_next = w;
                }
            }
            w_cur = w_next;
        }
        for (int w = 0; w < W; ++w) {  // update potentials
            ckmin(dist[w], dist[w_cur]);
            h[w] += dist[w];
        }
        ans_cur += h[w_cur];
        for (int w; w_cur != W; w_cur = w) job[w_cur] = job[w = prv[w_cur]];
        answers.push_back(ans_cur);
    }
    return answers;
}

Матричная интерпретация

Этот вариант алгоритма соответствует формулировке Флуда: и позже описан более подробно Мункресом, который доказал, что это происходит в ${\mathcal {O}}(n^{4})$ время. Вместо отслеживания потенциалов вершин алгоритм работает только с матрицей:

$a_{ij}:=c(i,j)-y(i)-y(j)$

где $c(i,j)$ - исходная матрица затрат и $y(i),y(j)$ – потенциалы из интерпретации графа. Изменение потенциалов соответствует добавлению или вычитанию строк или столбцов этой матрицы. Алгоритм начинается с $a_{ij}=c(i,j)$. Таким образом, это можно рассматривать как взятие исходной матрицы затрат и ее модификацию.

Для заданных n работников и задач задача записывается в виде n × n. матрицы затрат размера

1 ​	a а2	a а3	a 4
б 1	б 2	б 3	б 4
с 1	с 2	с 3	с 4
д 1	д 2	д 3	д 4

где a, b, c и d — рабочие, которые должны выполнять задачи 1, 2, 3 и 4. a ₁ , a ₂ , a ₃ и a ₄ обозначают штрафы, понесенные, когда работник «a» выполняет задачи 1, 2, 3 и 4 соответственно.

Проблема эквивалентна назначению каждому работнику уникальной задачи, при которой общий штраф минимизируется. Обратите внимание, что над каждой задачей может работать только один работник.

Шаг 1

Для каждой строки ее минимальный элемент вычитается из каждого элемента в этой строке. Это приводит к тому, что все элементы имеют неотрицательные значения. Следовательно, задание с общим штрафом 0 по определению является минимальным заданием.

Это также приводит к появлению хотя бы одного нуля в каждой строке. Таким образом, наивный жадный алгоритм может попытаться назначить всем работникам задачу с нулевым штрафом. Это показано ниже.

0	a а2	a а3	a 4
б 1	б 2	б 3	0
с 1	0	с 3	с 4
д 1	д 2	0	д 4

Нули выше будут назначенными задачами.

В худшем случае их n ! комбинации, которые стоит попробовать, поскольку несколько нулей могут появиться в строке, если несколько элементов являются минимальными. Так что в какой-то момент этот наивный алгоритм должен разрушиться.

Шаг 2

Иногда может оказаться, что матрица на этом этапе не может быть использована для присвоения, как в случае с матрицей ниже.

0	a а2	0	a 4
б 1	0	б 3	0
0	с 2	с 3	с 4
0	д 2	д 3	д 4

Чтобы преодолеть эту проблему, мы повторяем описанную выше процедуру для всех столбцов (т. е. минимальный элемент в каждом столбце вычитается из всех элементов в этом столбце ), а затем проверяем, возможно ли присвоение со штрафом 0.

В большинстве ситуаций это даст результат, но если это все же невозможно, то нужно продолжать.

Шаг 3

Все нули в матрице должны быть закрыты путем выделения как можно меньшего количества строк и/или столбцов. Шаги 3 и 4 представляют собой один из способов достижения этой цели.

Для каждой строки попробуйте присвоить произвольный ноль. Назначенные задачи обозначаются нулем, отмеченным звездочкой. Обратите внимание, что назначения не могут находиться в одной строке или столбце.

• Мы присваиваем первый ноль строки 1. Второй ноль строки 1 не может быть присвоен.
• Мы присваиваем первый ноль строки 2. Второй ноль строки 2 не может быть присвоен.
• Нули в строке 3 и строке 4 назначить невозможно, поскольку они находятся в том же столбце, что и ноль, назначенный в строке 1.

Мы могли бы закончить другим заданием, если выберем другой порядок строк и столбцов.

0*	a а2	0	a 4
б 1	0*	б 3	0
0	с 2	с 3	с 4
0	д 2	д 3	д 4

Шаг 4

Закройте все столбцы, содержащие ноль (помеченный звездочкой).

×	×
0*	aа2	0	a 4
б 1	0*	б 3	0
0	с 2	с 3	с 4
0	д 2	д 3	д 4

Найдите непокрытый ноль и заштрихуйте его (отметьте его символом штриха ). Если такой ноль не найден, то есть все нули покрыты, перейдите к шагу 5.

• Если ноль находится в той же строке, что и ноль со звездочкой, закройте соответствующую строку и откройте столбец нуля со звездочкой.
• Затем ПЕРЕЙДИТЕ к «Найдите непокрытый ноль и заштрихуйте его».
  • Здесь раскрыт второй ноль строки 1. Поскольку в строке 1 отмечен еще один ноль, мы закрываем строку 1 и открываем столбец 1.
  • Затем открывается второй ноль второй строки. Закрываем вторую строку и раскрываем второй столбец.

	×
0*	aа2	0'	a 4	×
б 1	0*	б 3	0
0	с 2	с 3	с 4
0	д 2	д 3	д 4

0*	aа2	0'	a 4	×
б 1	0*	б 3	0'	×
0	с 2	с 3	с 4
0	д 2	д 3	д 4

• В противном случае непокрытый ноль не имеет назначенного нуля в своей строке. Мы прокладываем путь, начиная с нуля, выполнив следующие шаги:
  1. Подэтап 1: Найдите ноль со звездочкой в ​​соответствующем столбце. Если он есть, перейдите к подэтапу 2, иначе остановитесь.
  2. Подшаг 2: Найдите нуль со штрихом в соответствующей строке (один всегда должен быть). Перейдите к подэтапу 1.

Ноль в строке 3 открыт. Добавляем к пути первый ноль строки 1, затем второй ноль строки 1, и все готово.

0*	aа2	0'	a 4	×
б 1	0*	б 3	0'	×
0'	с 2	с 3	с 4
0	д 2	д 3	д 4

• (Продолжение другой ветки) Для всех нулей, встречающихся на пути, нули со звездочкой и нули со звездочкой.
  • Поскольку путь начинается и заканчивается нулем со штрихом при замене нулей со звездочкой, мы присваиваем еще один ноль.

0	aа2	0*	a 4
б 1	0*	б 3	0
0*	с 2	с 3	с 4
0	д 2	д 3	д 4

• (Продолжение остальной ветки) Снимите все штриховые нули и откройте все строки.
• Повторите предыдущие шаги (продолжайте цикл до тех пор, пока не будет достигнут вышеуказанный «перейти к шагу 5»).
  • Закрываем столбцы 1, 2 и 3. Второй ноль в строке 2 открыт, поэтому закрываем строку 2 и раскрываем столбец 2:

×		×
0	aа2	0*	a 4
б 1	0*	б 3	0'	×
0*	с 2	с 3	с 4
0	д 2	д 3	д 4

Все нули теперь покрываются минимальным количеством строк и столбцов.

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

Шаг 5

Если количество звездчатых нулей равно n (или в общем случае $min(n,m)$, где n — количество людей, а m — количество рабочих мест), алгоритм завершает работу. См. подраздел « Результат» ниже, чтобы узнать, как интерпретировать результаты.

В противном случае найдите наименьшее непокрытое значение. Вычтите это значение из каждого немаркированного элемента и добавьте его к каждому элементу, покрытому двумя линиями. Вернитесь к шагу 4.

Это эквивалентно вычитанию числа из всех незакрытых строк и добавлению того же числа ко всем покрытым столбцам. Эти операции не меняют оптимальные назначения.

Результат

Если следовать этой конкретной версии алгоритма, нули со звездочками образуют минимальное назначение.

По теореме Кенига минимальное количество строк (минимальное покрытие вершин ) будет n (размер максимального соответствия ). Таким образом, когда требуется n строк, минимальное назначение стоимости можно найти, рассматривая только нули в матрице.

Библиография

• Р. Е. Буркард, М. Делл'Амико, С. Мартелло: Проблемы с заданием (пересмотренное переиздание). СИАМ, Филадельфия (Пенсильвания), 2012 г. ISBN   978-1-61197-222-1
• М. Фишетти, «Уроки операционного исследования», Edizioni Libreria Progetto Padova, Италия, 1995.
• Р. Ахуджа , Т. Маньянти , Дж. Орлин , «Сетевые потоки», Prentice Hall, 1993.
• С. Мартелло, «Йено Эгервари: от истоков венгерского алгоритма до спутниковой связи». Центральноевропейский журнал операционных исследований 18: 47–58, 2010 г.

Внешние ссылки

• Брафф, Дерек, Задача о назначениях и венгерский метод (матричный формализм).
• Мордехай Дж. Голин, Двустороннее сопоставление и венгерский метод (биграфный формализм), Конспект курса, Гонконгский университет науки и технологий .
• Венгерский алгоритм максимального соответствия (оба формализма) на веб-сайте Brilliant.
• Р. А. Пилигрим , Алгоритм назначения Мункреса. Модифицировано для прямоугольных матриц , Конспект курса, Государственный университет Мюррея .
• Майк Доус , Задача оптимального назначения , Конспект курса, Университет Западного Онтарио .
• О венгерском методе Куна – дань уважения из Венгрии , Андраш Франк , Исследовательская группа Эгервари, Пазмани П. setany 1/C, H1117, Будапешт, Венгрия.
• Лекция: «Основы исследования операций – Задача о назначениях – Венгерский алгоритм» , профессор Г. Сринивасан, факультет исследований управления, ИИТ Мадрас.
• Расширение: анализ чувствительности присваивания (с временной сложностью O(n^4)) , Лю, Шелл.
• Решите любую задачу о заданиях онлайн , содержащее пошаговое объяснение венгерского алгоритма.

Реализации

Обратите внимание, что не все из них удовлетворяют $O(n^{3})$ временная сложность, даже если они так заявляют. Некоторые могут содержать ошибки, реализуйте более медленные $O(n^{4})$ алгоритм или иметь другие недостатки. В худшем случае пример кода, ссылка на который содержится в Википедии, впоследствии может быть изменен и включен в него код эксплойта. Проверка и бенчмаркинг необходимы при использовании таких примеров кода от неизвестных авторов.

• Версии кода RA Pilgrim на Lua и Python (заявляющие, что $O(n^{3})$ временная сложность)
• Реализация Юлии
• Реализация C, утверждающая $O(n^{3})$ временная сложность
• Реализация Java утверждает $O(n^{3})$ временная сложность
• Реализация Python
• Реализация Ruby с модульными тестами
• Реализация C# утверждает $O(n^{3})$ временная сложность
• Реализация D с модульными тестами (порт версии Java, утверждающей $O(n^{3})$)
• Онлайн-интерактивная реализация
• Последовательная и параллельная реализации.
• Матлаб и Си
• Perl-реализация
• реализация на С++
• Реализация C++ утверждает $O(n^{3})$ временная сложность (лицензия с открытым исходным кодом в стиле BSD)
• Реализация MATLAB
• C-реализация
• Реализация JavaScript с модульными тестами (порт версии Java, утверждающей $O(n^{3})$ временная сложность)
• Пакет Clue R предлагает реализациюsolve_LSAP.
• Реализация Node.js на GitHub
• Реализация Python в пакете scipy