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

Алгоритм венгерского метода состоит из подготовительного этапа и из конечного числа итераций. На подготовительном этапе строится матрица X0 (xij)m,n, элементы которой неотрицательны и удовлетворяют неравенствам:

Если эти условия являются равенствами, то матрица Хo - решение транспортной задачи. Если среди условий имеются неравенства, то осуществляется переход к первой итерации. На k-й итерации строится матрица Хk (xij)m,n. Близость этой матрицы к решению задачи характеризует число Dk - суммарная невязка матрицы Хk:

В результате первой итерации строится матрица Хl, состоящая из неотрицательных элементов. При этом Dl D0. Если Dl 0, то Хl - оптимальное решение задачи. Если Dl 0, то переходят к следующей итерации. Они проводятся до тех пор, пока Dk при некотором k не станет равным нулю. Соответствующая матрица Хk является решением транспортной задачи.

Венгерский метод наиболее эффективен при решении транспортных задач с целочисленными объемами производства и потребления. В этом случае число итераций не превышает величины D0/2 (D0 - суммарная невязка подготовительного этапа).

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

    Волков И.К., Загоруйко Е.А. Исследование операций: Учеб. для вузов. 2-е узд. / Под ред.. В.С. Зарубина, А.П. Крищенко. – М.: Узд-во МГТУ им. Н.Э. Баумана, 2002. – 436 с.

    Зайченко Ю.П. Исследование операций: Учеб. пособие для студентов вузов. – 2-е изд., перераб. и доп. – Киев: Вища школа. Главное изд-во, 1979. 392 с.

    И. А. Акулич. Математическое программирование в примерах и задачах. - М.: «Высшая школа», 1986.- 319 с.

    Сакович В.А. Исследование операций (детерминированные методы и модели): Справочное пособие. - Мн.: Выш. шк., 1984.-256с.

    Таха Х. Введение в исследование операций: в двух книгах. Кн.1,2 Пер. с англ. - М.: Мир, 1985.

    Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 1998. – 141с.

Содержательная постановка задачи. В объединении находится n автомобилей, способных каждый перевозить в месяц Q i тонн груза (i = 1,2,…, n). С их помощью необходимо обеспечить перевозку грузов (пиломатериал, шурупы и т.д.) от поставщиков к потребителям по n маршрутам в количестве R j тонн в месяц (j = 1,2,…, n).
Задача заключается в том, чтобы перевезти все грузы с минимальными издержками, для этого надо каждый автомобиль пустить по одному и только его маршруту. Если возможность автомобиля в перевозке груза ниже потребности потребителя этого груза, то на данный маршрут автомобиль не может быть назначен. Поэтому составляется матрицу С, характеризующую издержки i-го автомобиля, в случае, если он будет назначен на j-й маршрут.

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

Алгоритм венгерского метода .

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

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

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

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

Шаг 2. (Определение назначений). На этом шаге можно использовать алгоритм поиска «наибольшего паросочетания с матрицей двудольного графа (существуют и другие возможности), если все =0 матрицы заменить на «1», а >0 на «0».

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

Шаг 3 . (Модификация редуцированной матрицы). Для редуцированной матрицы стоимостей:

а) Вычислить число нулей в каждой невычеркнутой строке и каждом невычеркнутом столбце.

б) Вычеркнуть строку или столбец с максимальным числом нулей.

в) Выполнять пункты а) и б) до тех пор, пока не будут вычеркнуты все нули.

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

Перейти к шагу 2.

Замечание 3 .Если исходная задача является задачей максимизации, то все элементы матрицы стоимостей следует умножить на (-1) и сложить их с достаточно большим числом так, чтобы матрица не содержала бы отрицательных элементов. Затем задачу следует решать как задачу минимизации.

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

Итерация 1

Шаг 1 . Редукция строк и столбцов.

Значения минимальных элементов строк 1, 2, 3 и 4 равны 2, 4, 11 и 4 соответственно. Вычитая из элементов каждой строки соответствующее минимальное значение, получим следующую матрицу:

Значения минимальных элементов столбцов 1, 2, 3 и 4 равны 0, 0, 5 и 0 соответственно. Вычитая из элементов каждого столбца соответствующее минимальное значение, получим следующую матрицу.

Шаг 2 . Поиск допустимого решения, для которого все назначения имеют нулевую стоимость. Используем алгоритм поиска наибольшего паросочетания. Преобразуем матрицу в матрицу двудольного графа, затем в рабочую таблицу:

Находим паросочетание:

Это паросочетание не совершенное, т.е. полного назначения нет. На Шаг 3.

Шаг 3. Модификация редуцированной матрицы.

а) Число нулей в строках 1, 2, 3 и 4 равно 1, 1, 2 и 1 соответственно. Для столбцов соответствующие величины равны 2, 1, 1 и 1.

б) Максимальное число нулей, по два, содержат строка 3 и столбец 1. Выбираем строку 3 и вычеркиваем все ее элементы горизонтальной линией.

в) Число невычеркнутых нулей в строках 1, 2 и 4 равно 1, 1 и 1 соответственно. Для столбцов соответствующие значения равны 2, 1, 0, и 0. Поэтому мы должны выбрать столбец 1 и вычеркнуть его вертикальной линией. После этого останется только один невычеркнутый нуль – элемент (2,2). Поэтому можно вычеркнуть либо строку 2, либо столбец 2. Вычеркивая строку 2 горизонтальной линией, получаем следующую матрицу:

г) Значение минимального невычеркнутого элемента равно 2. Вычитая его из всех невычеркнутых элементов и складывая его со всеми элементами, расположенными на пересечении двух линий, получаем новую матрицу стоимостей.

Задача о назначениях ставится весьма естественно.

Приведём несколько вариантов постановки (как легко видеть, все они эквивалентны друг другу):

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

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

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

Историческая справка

Алгоритм был разработан и опубликован Гарольдом Куном (Harold Kuhn) в 1955 г. Сам Кун дал алгоритму название "венгерский", потому что он был в значительной степени основан на более ранних работах двух венгерских математиков: Денеша Кёнига (Dénes Kőnig) и Эйгена Эгервари (Jenő Egerváry).

В 1957 г. Джеймс Манкрес (James Munkres) показал, что этот алгоритм работает за (строго) полиномиальное время (т.е. за время порядка полинома от , не зависящего от величины стоимостей).

Поэтому в литературе данный алгоритм известен не только как "венгерский", но и как "алгоритм Куна-Манкреса" или "алгоритм Манкреса".

Впрочем, недавно (в 2006 г.) выяснилось, что точно такой же алгоритм был изобретён за век до Куна немецким математиком Карлом Густавом Якоби (Carl Gustav Jacobi). Дело в том, что его работа "About the research of the order of a system of arbitrary ordinary differential equations", напечатанная посмертно в 1890 г., содержавшая помимо прочих результатов и полиномиальный алгоритм решения задачи о назначениях, была написана на латыни, а её публикация прошла незамеченной среди математиков.

Также стоит отметить, что первоначальный алгоритм Куна имел асимптотику , и лишь позже Джек Эдмондс (Jack Edmonds) и Ричард Карп (Richard Karp) (и независимо от них Томидзава (Tomizawa)) показали, каким образом улучшить его до асимптотики .

Построение алгоритма за

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Приведённая реализация фактически была разработана Андреем Лопатиным несколько лет назад. Её отличает удивительная лаконичность: весь алгоритм помещается в 30 строк кода .

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

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

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

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

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

Сам алгоритм представляет из себя внешний цикл по строкам матрицы , внутри которого происходит добавление в рассмотрение -ой строки матрицы. Внутренняя часть представляет собой цикл "do-while (p != 0)", который работает, пока не будет найден свободный столбец . Каждая итерация цикла помечает посещённым новый столбец с номером (посчитанным на прошлой итерации; а изначально равным нулю — т.е. стартуем мы с фиктивного столбца), а также новую строку — смежную ему в паросочетании (т.е. ; а изначально при берётся -ая строка). Из-за появления новой посещённой строки нужно соответствующим образом пересчитать массив , заодно мы находим минимум в нём — величину , и в каком столбце этот минимум был достигнут (заметим, что при такой реализации могло оказаться равной нулю, что означает, что на текущем шаге потенциал можно не менять: новый достижимый столбец есть и без того). После этого производится пересчёт потенциала , соответствующее изменение массива . По окончании цикла "do-while" мы нашли увеличивающую цепочку, оканчивающуюся в столбце , "раскрутить" которую можно, пользуясь массивом предков .

Константа — это "бесконечность", т.е. некоторое число, заведомо большее всех возможных чисел во входной матрице .

Vector< int > u (n+ 1 ) , v (m+ 1 ) , p (m+ 1 ) , way (m+ 1 ) ; for (int i= 1 ; i<= n; ++ i) { p[ 0 ] = i; int j0 = 0 ; vector< int > minv (m+ 1 , INF) ; vector< char > used (m+ 1 , false ) ; do { used[ j0] = true ; int i0 = p[ j0] , delta = INF, j1; 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; } 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 ) ; do { int j1 = way[ j0] ; p[ j0] = p[ j1] ; j0 = j1; } while (j0) ; }

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

Vector< int > ans (n+ 1 ) ; for (int j= 1 ; j<= m; ++ j) ans[ p[ j] ] = j;

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

int cost = - v[ 0 ] ;

Примеры задач

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

  • максимальное паросочетание минимального веса (т.е. в первую очередь максимизируется размер паросочетания, во вторую — минимизируется его стоимость).

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

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

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

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

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

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

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

  • Покрытие ориентированного ациклического графа путями : дан ориентированный ациклический граф, требуется найти наименьшее число путей (при равенстве — с наименьшим суммарным весом), чтобы каждая вершина графа лежала бы ровно в одном пути.
  • Раскраска дерева . Дано дерево, в котором каждая вершина, кроме листьев, имеет ровно сыновей. Требуется выбрать для каждой вершины некоторый цвет из цветов так, чтобы никакие две смежные вершины не имели одинакового цвета. Кроме того, для каждой вершины и каждого цвета известна стоимость покраски этой вершины в этот цвет, и требуется минимизировать суммарную стоимость.

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

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

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

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

  • Задача о потенциалах . Дана матрица . Требуется найти два массива и такие, что для любых и выполняется , но при этом сумма элементов массивов и максимальна.

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

Литература

  • Harold Kuhn. The Hungarian Method for the Assignment Problem
  • James Munkres. Algorithms for Assignment and Transportation Problems

Теорема 1.

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

для из базиса

Метод потенциалов

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

Вычисляются потенциалы, затем для небазисных пар индексов определяются оценки по формуле

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

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



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

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

Рассмотри задачу о назначениях с матрицей эффективностей

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

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

Теорема 2 (Эгервари).

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

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

Алгоритм венгерского метода

Предварительный этап

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

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

Шаг 2. Теперь вычтем из элементов каждой строки матрицы минимальный элемент той же строки матрицы , результат остаётся на месте уменьшаемых элементов:

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

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

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

Основной этап

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

Если число отмеченных звездочкой нулей равно , то процесс окончен: места, занимаемые нулями со звездочкой, соответствуют переменным равным 1, в оптимальном варианте назначения.

Если нулей со звездочкой меньше , то

2. Помечаем знаком «+» сверху столбцы матрицы, в которых есть , и считаем эти столбцы занятыми.

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

Если в матрице нет незанятых нулей, то переходим к пункту 5.

Если незанятые нули есть, то выбираем первый из них (просматривая поочередно строки слева направо). Отмечаем его каким-нибудь промежуточным значком (например, штрихом ). Если в его строке нет нуля со звездочкой, то переходим к п.4; если в его строке есть, то

3. Столбец, в котором находится , лежащий в той же строке, что и только что отмеченный штрихом нуль, считаем снова незанятым и знак «+» сверху снимаем. Строку, в которой находится наш объявляем занятой и помечаем знаком «+» справа. Возвращаемся к третьему абзацу пункта 2.

4. Строим цепочку из нулей: начинаем с только что отмеченного штрихом нуля (), идем по столбцу до , от него по строке к , и т.д., пока это возможно. Цепочка оборвется на каком-то (возможно на первом же ). Звездочки у нулей в цепочке снимаем, а вместо штрихов у нулей в цепочке ставим звездочки. Получим новый набор нулей со звездочкой, который содержит на один нуль больше, чем предыдущий набор.

Снимаем все пометки, кроме звездочек, и возвращаемся ко второму абзацу пункта 1.

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