Размещено на http://www.allbest.ru/

Венгерский алгоритм решения задачи о назначениях

1. Постановка задачи о назначениях

Имеется “n” работников и “n” работ. Есть матрица “A” размером “n x n” - матрица затрат. Каждый элемент матрицы обозначает, какую зарплату затребует работник “I” если будет работать на работе “j”. Каждый работник может выполнять только одну работу, а на каждой работе может работать только один работник. Требуется так распределить работников, чтобы суммарные затраты на зарплату были минимальны.

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

Построение алгоритма за O(n4)

Сразу отметим во избежание неоднозначностей, что мы в основном рассматриваем здесь задачу о назначениях в матричной постановке (т.е. дана матрица , и надо выбрать из неё  ячеек, находящихся в разных строках и столбцах). Индексацию массивов мы начинаем с единицы, т.е., например, матрица имеет индексы .

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

Назовём потенциалом два произвольных массива чисел и таких, что выполняется условие:

(Как видно, числа соответствуют строкам, а числа -- столбцам матрицы.)

Назовём значением потенциала сумму его чисел

С одной стороны, легко заметить, что стоимость искомого решения не меньше значения любого потенциала:

(Доказательство. Искомое решение задачи представляет из себя ячеек матрицы, и для каждой из них выполняется условие . Поскольку все элементы находятся в разных строках и столбцах, то, суммируя эти неравенства по всем выбранным , в левой части неравенства получаем , а в правой -- , что и требовалось доказать.)

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

Зафиксируем некоторый потенциал. Назовём ребро жёстким, если выполняется:

Вспомним об альтернативной постановке задачи о назначениях, с помощью двудольного графа. Обозначим через двудольный граф, составленный только из жёстких рёбер. Фактически, венгерский алгоритм поддерживает для текущего потенциала максимальное по количеству рёбер паросочетание графа : и как только это паросочетание станет содержать рёбер, рёбра этого паросочетания и будут являться искомым оптимальным решением (ведь это будет решение, стоимость которого совпадает с величиной потенциала).

Перейдём непосредственно к описанию алгоритма.

I. В начале алгоритма потенциал полагается равным нулю , и паросочетание полагается пустым.

II. Далее, на каждом шаге алгоритма мы пытаемся, не меняя потенциала, увеличить мощность текущего паросочетания на единицу (напоминаем, паросочетание ищется в графе жёстких рёбер ).

Для этого фактически используется обычный алгоритм Куна поиска максимального паросочетания в двудольных графах. Напомним здесь этот алгоритм.

Все рёбра паросочетания ориентируются по направлению от второй доли к первой, все остальные рёбра графа ориентируются в противоположную сторону.

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

Из всех ненасыщенных вершин первой доли запускается обход в глубину/в ширину. Если в результате обхода удалось достигнуть ненасыщенной вершины второй доли, то это означает, что мы нашли увеличивающий путь из первой доли во вторую. Если прочередовать рёбра вдоль этого пути (т.е. первое ребро включить в паросочетание, второе исключить, третье включить, и т.д.), то тем самым мы увеличим мощность паросочетания на единицу.

Если же увеличивающего пути не было, то это означает, что текущее паросочетание -- максимально в графе , поэтому в таком случае переходим к следующему пункту.

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

Обозначим через множество вершин первой доли, которые были посещены обходом алгоритма Куна при попытке поиска увеличивающей цепи; через -- множество посещённых вершин второй доли.

Посчитаем величину :

Эта величина строго положительна.

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

Теперь пересчитаем потенциал таким образом: для всех вершин сделаем , а для всех вершин -- сделаем . Получившийся потенциал по-прежнему останется корректным потенциалом.

(Доказательство. Для этого надо показать, что по-прежнему для всех и выполняется: . Для случаев, когда или -- это так, поскольку для них сумма и не изменилась. Когда -- неравенство только усилилось. Наконец, для случая -- хотя левая часть неравенства и увеличивается, неравенство всё равно сохраняется, поскольку величина , как видно по её определению это как раз максимальное увеличение, не приводящее к нарушению неравенства.)

Кроме того, старое паросочетание из жёстких рёбер можно будет оставить, т.е. все рёбра паросочетания останутся жёсткими.

(Доказательство. Чтобы некоторое жёсткое ребро перестало быть жёстким в результате изменения потенциала, надо, чтобы равенство превратилось в неравенство . Однако левая часть могла уменьшиться только в одном случае: когда . Но раз , то это означает, что ребро не могло быть ребром паросочетания, что и требовалось доказать.)

Наконец, чтобы показать, что изменения потенциала не могут происходить бесконечно, заметим, что при каждом таком изменении потенциала количество вершин, достижимых обходом, т.е. , строго увеличивается. (При этом нельзя утверждать, что увеличивается количество жёстких рёбер.)

(Доказательство. Во-первых, любая вершина, которая была достижимой, достижимой и останется. В самом деле, если некоторая вершина достижима, то до неё есть некоторый путь из достижимых вершин, начинающийся в ненасыщенной вершине первой доли; а поскольку для рёбер вида сумма не меняется, то весь этот путь сохранится и после изменения потенциала, что и требовалось доказать. Во-вторых, покажем, что в результате пересчёта потенциала появилась хотя бы одна новая достижимая вершина. Но это почти очевидно, если вернуться к определению : то ребро , на котором был достигнут минимум, теперь станет жёстким, а, значит, вершина станет достижимой благодаря этому ребру и вершине .)

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

Таким образом, рано или поздно будет найден потенциал, которому соответствует совершенное паросочетание , являющееся ответом на задачу.

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

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

Построение алгоритма за O(n3)

Научимся теперь реализовывать тот же алгоритм за асимптотику (для прямоугольных задач -- ).

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

· Добавляем в рассмотрение очередную строку матрицы .

· Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.

· Как только появляется увеличивающая цепь, чередуем паросочетание вдоль неё (включая тем самым последнюю строку в паросочетание), и переходим к началу (к рассмотрению следующей строки).

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

Для этого мы вспомним два факта, доказанных нами выше:

· При изменении потенциала вершины, которые были достижимы обходом Куна, достижимыми и останутся.

· Всего могло произойти лишь пересчётов потенциала, прежде чем будет найдена увеличивающая цепь.

Отсюда вытекают ключевые идеи, позволяющие достичь требуемой асимптотики:

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

· Развивая эту идею дальше, можно прийти к такому представлению алгоритма: это цикл, на каждом шаге которого сначала пересчитывается потенциал, затем находится столбец, ставший достижимым (а таковой всегда найдётся, поскольку после пересчёта потенциала всегда появляются новые достижимые вершины), и если этот столбец был ненасыщен, то найдена увеличивающая цепь, а если столбец был насыщен -- то соответствующая ему в паросочетании строка также становится достижимой.

Теперь алгоритм принимает вид: цикл добавления строк, на каждом из которых сначала пересчитывается потенциал, а затем какой-то новый столбец помечается как достижимый.

Чтобы быстро пересчитывать потенциал (быстрее, чем наивный вариант за ), надо поддерживать вспомогательные минимумы по каждому из столбцов :

Как легко видеть, искомая величина выражается через них следующим образом:

Таким образом, нахождение теперь можно произвести за .

Поддерживать этот массив необходимо при появлении новых посещённых строк. Это, очевидно, можно сделать за на одну добавляемую строку (что в сумме даст ). Также обновлять массив надо при пересчёте потенциала, что также делается за время на один пересчёт потенциала (поскольку меняется только для недостигнутых пока столбцов: а именно, уменьшается на ).

Таким образом, алгоритм принимает такой вид: во внешнем цикле мы добавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время , поскольку при этом могло происходить лишь пересчётов потенциала (каждый -- за время ), для чего за время поддерживается массив ; алгоритм Куна суммарно отработает за время (поскольку он представлен в форме итераций, на каждой из которых посещается новый столбец).

Итоговая асимптотика составляет -- или, если задача прямоугольна, .

Реализация венгерского алгоритма

Приведем здесь реализацию венгерского алгоритма на языке C#. Логика работы программы проста: в качестве параметра для запуска программы указывается путь к .txt файлу, в котором находится матрица из условия задачи (все элементы матрицы разделяются пробелами между собой, причем каждая строка записывается в отдельной строке файла). На выходе программа выдает распределение работников по работам (в номерах), а также минимальные затраты на зарплату.

Итак, первым делом подключаем стандартные библиотеки С#, а также две специализированные библиотеки для работы с матрицей:

венгерский алгоритм матрица паросочетание

using System;

using System.IO;

using MatrixMath;

using Longnumber;

Далее создаем пространство имен, класс и статический метод Main - точка входа программы:

namespace Hungarian

{

class Program

{

static void Main(string[] args)

{

Делаем простую проверку, определяющую, был ли дан на вход программе файл с матрицей, и точно ли он существует. В противном случае перехватываем исключение и выводим на экран сообщение об ошибке. После чего завершаем выполнение программы:

try

{

if (!File.Exists(args[0]))

throw new Exception("Файл не существует");

}

catch

{

Console.WriteLine("Путь к файлу с матрицей не существует или не указан!\nВ качестве параметра к запуску необходимо указать путь к .txt файлу с матрицей!");

return;

}



Приближаясь к самому алгоритму, вначале инициализируем все необходимые массивы. А именно: создаем матрицу А, переводим ее в двумерный массив a[,], создаем массивы для потенциала u[] и v[], массив для паросочетаний p[] и массив для восстановления увеличивающей цепочки way[]. Последние четыре массива заполняем нулями. Последним шагом в подготовке является создание константы INF, являющейся (по задумке) максимальным возможным целым числом (в данном случае это максимальное число, помещающеяся в размерность int):

Matrix A = new Matrix(args[0]);

A.PrintMatrix();

int n = A.dim;

int m = A.dim;

int[,] a = new int[n + 1, m + 1];

for (int i = 0; i < n; i++)

for (int j = 0; j < m; j++)

a[i + 1, j + 1] = Convert.ToInt32(A.matrix[i, j].ToString());

int[] u = new int[n + 1];

int[] v = new int[m + 1];

int[] p = new int[m + 1];

int[] way = new int[m + 1];

for (int i = 0; i <= n; i++)

u[i] = 0;

for (int i = 0; i <= m; i++)

{

v[i] = 0;

p[i] = 0;

way[i] = 0;

}

const int INF = 2147483647;

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

Итак, создаем внешний цикл for, который будет добавлять нам строки из матрицы одну за одной. Заносим в нулевой элемент массива паросочетаний текущую строку, создаем массив минимумов по столбцам (заполняя его максимальным числом) и массив столбцов, которые мы уже посетили (изначально все его элементы заполняем как false):

for (int i = 1; i <= n; i++)

{

p[0] = i;

int j0 = 0;

int[] minv = new int[m + 1];

bool[] used = new bool[m + 1];

for (int h = 0; h <= m; h++)

{

minv[h] = INF;

used[h] = false;

}

Далее следует цикл do-while, который работает, пока не будет найден свободный столбец j0. На каждой итерации этого цикла мы отмечаем посещенным столбец j0, полученный на прошлой итерации (изначально он нулевой), а также новую строку i0 - смежную в паросочетании столбцу j0 (изначально берется новая добавленная строка i). Кроме того, в обязательном порядке пересчитываем минимумы по столбцам (они изменились в следсвие добавления новой строки) и заодно пересчитываем глобальный минимум delta.



do

{

used[j0] = true;

int i0 = p[j0], delta = INF, j1 = 0;

for (int j = 1; j <= m; j++)

{

if (!used[j])

{

int cur = a[i0, j] - u[i0] - v[j];

if (cur < minv[j])

{

minv[j] = cur;

way[j] = j0;

}

if (minv[j] < delta)

{

delta = minv[j];

j1 = j;

}

}

}

После этого пересчитываем потенциал u[] и v[] в соответствии с алгоритмом, изменяем минимумы по столбцам и в качестве нового столбца j0 берем столбец j1, на котором был найден минимум.

for (int j = 0; j <= m; j++)

{

if (used[j])

{

u[p[j]] += delta;

v[j] -= delta;

}

else

{

minv[j] -= delta;

}

}

j0 = j1;

} while (p[j0] != 0);

По окончании цикла мы найдем увеличивающую цепочку, развернуть которую нам поможет массив way[] и, собственно, сами паросочетания p[]:

do

{

int j1 = way[j0];

p[j0] = p[j1];

j0 = j1;

} while (j0 != 0);

}

Алгоритмы завершает работу когда будут добавлены все строки матрицы, а ответ будет храниться в наших паросочетания p[]. Чтобы сделать ответ более привычным: каждой строке j сопоставить найденный столбец ans[j] необходимо дополнительно пройтись по паросочетаниям:

int[] ans = new int[n + 1];

ans[0] = 0;

for (int j = 1; j <= m; j++)

ans[p[j]] = j;

Console.WriteLine("Распределение работников:");

for (int j = 1; j <= n; j++)

Console.WriteLine(j + "->" + ans[j]);

Console.WriteLine("Суммарные затраты: {0}", -v[0]);

}

}

}

Получив массив ответов ans[] выводим его на экран. Удивительно, но нам даже не потребуется делать каких-либо дополнительных вычислений для определения суммарных минимальных затрат: они уже были посчитаны в ходе алгоритма и сохранены в нулевом элементе массива v[], с тем лишь отличием, что там затраты хранятся с противоположным знаком. Остается только умножить v[0] на минус единицу и вывести на экран суммарные затраты.

Размещено на Allbest.ru

...