Венгерский алгоритм для неквадратной матрицы

62408

Хочется рассмотреть задачу о назначениях для прямоугольной матрицы, но не совсем понятно, как это делать.
Вот что пишется:
Задача о назначениях звучит так:
Заданы два конечных множества K и L и матрица a[K,L] (обычно считается что |K| = |L|). Цель найти взаимно однозначное соответствие f : K > L которое делает сумму по всем k a[k, f(k)] минимальной.
Венгерский метод решения этой задачи был впервые предложен американским математиком Х. Куном. Кун использовал теорию паросочетаний известную ему по работам венгерских ученых, Д. Кенига и Э. Эгервари, и поэтому назвал свой алгоритм венгерским методом.
Алгоритм не кажется особо сложным, хотя достаточно тяжело понять почему он работает.
Он состоит из трех основных шагов:
1. Мы "спускаем" до нуля каждую строку и каждый столбец. Это означает что мы создаем по крайней мере один ноль в каждой строке и каждом столбце.
2. Мы строим максимальное паросочетание на всех нулях полученных на предыдущем шаге.
3. Если максимальное паросочетание окажется полным, то задача уже решена. В противном случае, построенное вместе с паросочетанием минимальное контролирующие множество (K', L') поможет нам решить задачу. Согласно определению минимального контролирующего множества, для всех нулевых элементов a[k, l] либо k принадлежит K' либо l принадлежит L'. Поэтому все элементы подматрицы a[K\K', L\L'] больше нуля. Теперь мы находим минимальный элемент этой подматрицы и мы прибавляем его к a[K', L] и вычитаем из a[K, L\L']. После этого мы возвращаемся к шагу номер два.
Алгоритм выполняется до тех пор пока не будет построено полное паросочетание.
Здесь, на мой взгляд, всё-таки обойдён случай, когда |K| >< |L|, так как не совсем понятно, что делать с "лишними" столбцами или строками, и не совсем понятно, как обходить полноту, так как в прямоугольном случае полнота иногда, вроде бы, есть, но правильного решения не даёт.
Кто имел опыт работы с подобными задачами? Поделитесь знаниями, пожалуйста.

62408

Можно ли в случае прямоугольной матрицы достраивать её до квадратной, дописывая в столбик или строку нули (при поиске максимального паросочетания) или какие-нибудь большие числа (в случае минимального)?

Xephon

В этих алгоритмах собаку съел Максим Бабенко
Его сайт с библиотекой - http://shade.msu.ru/~mab/
Оставить комментарий
Имя или ник:
Комментарий: