Решение задачи венгерским способом

Задача о назначениях онлайн

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

Предупреждение

Задача о назначениях − теория

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

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

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

При решении задачи о назначениях применяется венгерский метод, что существенно упрощает решение задачи.

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

Сделаем несколько определений.

1. Нулевые элементы квадратной матрицы S будем называть независимыми нулями , если столбец и строка, в которых находится данный нулевой элемент не содержат другого нулевого элемента.

2. Две прямоугольные матрицы и порядка mxn называются эквивалентными, если , , .

Решение задачи имеет подголовительную и итерационную части.

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

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

Этап 1. Если количество независимых нулей равно размерности матрицы, то задача решена и позиции отмеченных нулей является решением задачи о назначениях. Если же количество независимых нулей меньше n, то продолжаем процедуру. Выделяем столбцы матрицы C содержащие нули со звездочкой. Если среди невыделенных элементов матрицы нет нулевых, то переходим к этапу 3. Если обнаруживается невыделенный нуль, то есть два варианта:

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

Вариант 2. Строка, содержащая невыделенный нуль не содержит нуль со звездой. В этом случае отмечаем этот нуль знаком ° и переходим к этапу 2.

Этап 2. Исходя из нуля со знаком °, в строке которой нет нуля со звездой (вариант 2) строим следующую цепочку элементов матрицы C: Исходный 0° − 0* (лежащий в одном столбце (если существует)) − 0° (лежащей в одной строке с предшествующим 0* и т.д. Цепочка имеет вид 0°−0*−0°−. и обязательно заканчивается 0°. Там, где 0°, заменяем на 0*, а на четных позициях уничтожаем знак * над нулями. Далее уничтожаем все ° над нулями и снимаем выделения из столбцов и строк. Число независимых нулей увеличился на единицу. Переходим к этапу 1.

Этап 3. К этому этапу переходим после завершения этапа 1, когда независимых нулей нет.

Среди невыделенных элементов находим минимальный q>0. Далее величину q вычитаем из всех элементов матрицы C расположенных на невыделенных строках, и прибавляем ко всем элементам на выделенных столбцах (можно и так: величину q вычитаем из всех невыделенных элементов матрицы C и прибавляем ко всем элементам, находящимся на пересечении выделенных строк и столбцов). В полученной матрице появятся невыделенные нули поэтому переходим к этапу 1.

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

Источник

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

Венгерский алгоритм (англ. Hungarian algorithm) — алгоритм, решающий задачу о назначениях за полиномиальное время. Оригинальная версия была придумана и разработана Х. Куном в 1955 году и имела асимптотику [math] O(n^4) [/math] , но позже Эдмонс и Карп (а также, независимо от них, Томидзава) показали, что можно улучшить ее до [math] O(n^3) [/math] .

Задача:

Пусть дан взвешенный полный двудольный граф c целыми весами ребер [math] K_ [/math] , нужно найти в нем полное паросочетание минимального веса. Вес паросочетания определяется как сумма весов его ребер. Далее будем обозначать левую и правую доли графа за [math] X [/math] и [math] Y [/math] соответственно, вес ребра [math] xy [/math] — как [math] c(xy) [/math] .

Содержание

Вспомогательные леммы [ править ]

Доказательство: [math]\triangleright[/math] Полное паросочетание для каждой вершины содержит ровно одно ребро, инцидентное этой вершине. Указанная операция изменит на одно и то же число вес любого паросочетания. Значит, ребро, которое принадлежало оптимальному паросочетанию в старом графе, в новом графе тоже будет ему принадлежать. [math]\triangleleft[/math]

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

Доказательство: [math]\triangleright[/math]

Рассмотрим матрицу весов графа. Не умаляя общности, можно сказать, что множества [math] X’ [/math] и [math] Y’ [/math] состоят из первых элементов множеств [math] X [/math] и [math] Y [/math] соответственно (мы упорядочиваем множества по номерам вершин). Тогда вся матрица делится на 4 блока:

[math] Y’ [/math]	[math] Y \backslash Y’ [/math]
[math] X’ [/math]	[math] A + d — d [/math]	[math] C + d [/math]
[math] X \backslash X’ [/math]	[math] B — d [/math]	[math] D [/math]

Веса группы [math] A [/math] будут сначала увеличены, а потом уменьшены на [math] d [/math] , поэтому они не изменятся, веса группы [math] D [/math] вообще изменяться не будут. Все веса группы [math] B [/math] будут уменьшены на [math] d [/math] , но [math] d [/math] — минимум среди этих весов, поэтому они останутся неотрицательными. [math]\triangleleft[/math]

Лемма:

Доказательство:

[math]\triangleright[/math]

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

[math]\triangleleft[/math]

Общий метод [ править ]

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

Алгоритм, решающий задачу, работает с графом, как с матрицей весов.

• Вычитаем из каждой строки значение ее минимального элемента. Теперь в каждой строке есть хотя бы один нулевой элемент.
• Вычитаем из каждого столбца значение его минимального элемента. Теперь в каждом столбце есть хотя бы один нулевой элемент.
• Ищем в текущем графе полное паросочетание из ребер нулевого веса:
  • Если оно найдено, то желаемый результат достигнут, алгоритм закончен.
  • В противном случае, покроем нули матрицы весов минимальным количеством строк и столбцов (это не что иное, как нахождение минимального вершинного покрытия в двудольном графе). Пусть [math] X_c [/math] и [math] Y_c [/math] — множества вершин минимального вершинного покрытия из левой и правой долей (то есть, строк и столбцов) соответственно, тогда применим преобразование [math] X_c \uparrow\downarrow (Y \setminus Y_c) [/math] . Для этого преобразования [math] d [/math] будет минимумом по всем ребрам между [math] X \setminus X_c [/math] и [math] Y \setminus Y_c [/math] , то есть, ребер нулевого веса здесь нет, поэтому, после его выполнения в матрице весов появится новый нуль. После этого перейдем к шагу 1.

Анализ времени работы [ править ]

Поиск максимального паросочетания или минимального вершинного покрытия в двудольном графе совершается за [math] O(n^3) [/math] операций. При каждом повторении шагов 1-4 в матрице весов появляется новый нуль. Этот нуль соответствует некоторому новому ребру между вершинами из множеств [math] X \setminus X_c [/math] и [math] Y \setminus Y_c [/math] . Всего в графе [math] n^2 [/math] ребер, значит, всего будет совершено не более [math] O(n^2) [/math] итераций внешнего цикла. Поэтому, верхняя оценка времени работы данного метода — [math] O(n^5) [/math] . Более точная оценка довольно сложна и зависит от порядка чисел в матрице весов графа.

Алгоритм за [math] O(n^3) [/math] [ править ]

Общая идея [ править ]

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

Описание алгоритма [ править ]

• Начало
• Шаг 0. Введем следующее понятие:

Назовём потенциалом два произвольных массива чисел [math] u[1 \ldots n] [/math] и [math] v[1 \ldots n] [/math] таких, что выполняется условие: [math] u[i] + v[j] \leqslant a[i][j]

(i = 1 \ldots n)[/math] , где [math] a [/math] — заданная матрица.

• Шаг 1. Добавляем в рассмотрение очередную строку матрицы [math] a. [/math]
• Шаг 2. Пока нет увеличивающей цепи, начинающейся в этой строке, пересчитываем потенциал.
• Шаг 3. Как только появляется увеличивающая цепь, чередуем паросочетание вдоль неё (включая тем самым последнюю строку в паросочетание), и переходим к началу (к рассмотрению следующей строки).
• Конец

Ключевые идеи [ править ]

• Для проверки наличия увеличивающей цепочки нет необходимости запускать обход Куна заново после каждого пересчёта потенциала. Вместо этого можно оформить обход Куна в итеративном виде: после каждого пересчёта потенциала мы просматриваем добавившиеся жёсткие рёбра и, если их левые концы были достижимыми, помечаем их правые концы также как достижимые и продолжаем обход из них.
• Развивая эту идею дальше, можно прийти к такому представлению алгоритма: это цикл, на каждом шаге которого сначала пересчитывается потенциал, затем находится столбец, ставший достижимым (а таковой всегда найдётся, поскольку после пересчёта потенциала всегда появляются новые достижимые вершины), и если этот столбец был ненасыщен, то найдена увеличивающая цепь, а если столбец был насыщен — то соответствующая ему в паросочетании строка также становится достижимой.
• Теперь алгоритм принимает вид: цикл добавления столбцов, на каждом из которых сначала пересчитывается потенциал, а затем какой-то новый столбец помечается как достижимый.
• Чтобы быстро пересчитывать потенциал (быстрее, чем наивный вариант за [math] O(n^2) [/math] ), надо поддерживать вспомогательные минимумы по каждому из столбцов [math] j [/math] .

Реализация [ править ]

[math] \mathtt [/math] — прямоугольная входная матрица, где [math] \mathtt [/math] . Матрица хранится в 1-индексации.

v[0 \dots n]> [/math] — потенциал.

[math] \mathtt [/math] — массив паросочетания. Для каждого стобца [math] \mathtt [/math] он хранит номер соответствующей выбранной строки [math] \mathtt [/math] (или [math] \mathtt <0>[/math] , если ничего не выбрано). Полагаем, что [math] \mathtt [/math] равно номеру рассматриваемой строки.

[math] \mathtt [/math] — массив, хранящий для каждого столбца [math] \mathtt [/math] вспомогательные минимумы, необходимые для быстрого пересчета потенциала.

[math] \mathtt(a[i][j] — u[i] — v[j])> [/math] , где [math] \mathtt [/math] — множество вершин первой доли, которые были посещены обходом алгоритма Куна при попытке поиска увеличивающей цепи.

[math] \mathtt [/math] — массив, содержащий информацию о том, где эти минимумы достигаются, чтобы мы могли впоследствии восстановить увеличивающую цепочку.

Время работы [ править ]

Оценим время работы алгоритма. Во внешнем цикле мы добавляем в рассмотрение строки матрицы одну за другой. Каждая строка обрабатывается за время [math] O(n^2) [/math] , поскольку при этом могло происходить лишь [math] O(n) [/math] пересчётов потенциала (каждый — за время [math] O(n) [/math] ), для чего за время [math] O(n^2) [/math] поддерживается массив [math] minv [/math] ; алгоритм Куна суммарно отработает за время [math] O(n^2) [/math] (поскольку он представлен в форме [math] O(n) [/math] итераций, на каждой из которых посещается новый столбец).

Итоговая асимптотика составляет [math] O(n^3) [/math] .

Источник

Читайте также:  Способ реализации социальной политики это