§2.4. Связь между потоками и паросочетаниями
Следующее простое построение позволяет установить связь между потоками в сетях и Паросочетаниями в двудольном графе. Рассмотрим произвольный двудольный граф с множеством вершин V разбитым на доли X и Y. Добавим две дополнительные вершины – источник s и сток t. Добавим ребро sx из источника в каждую вершину доли x и аналогично ребро yt из каждой вершины доли Y в сток. Все пропускные способности положим единичными. Оказывается, что между потоками в построенной сети и паросочетаниями в исходном графе существует взаимнооднозначное соответствие. А потому мощность максимального Паросочетания в исходном графе равняется величине максимального потока. Таким образом, задача о паросочетании является частным случаем задачи о нахождении максимального потока в сети. А потому любой алгоритм нахождения максимального потока можно применить к решению задачи о паросочетании.
Однако стоит заметить, что частная задача о паросочетании может быть решена более эффективно, поскольку алгоритм нахождения максимального потока является общим и не использует двудольную природу исходной сети.
Глава 3. Задача о назначениях: «взвешенный» вариант задачи о паросочетаниях
§3.1. Монж: оптимальное назначение
Задача о назначениях является одной из старейших задач комбинаторной оптимизации. Еще в 1784 году ее исследовал Монж (Monge) (в своих работах он использовал термин «задача о транспортировке». Монж был мотивирован задачей транспортировки земли, которую он рассматривал как дискретную, комбинаторную задачу транспортировки молекул: «Когда необходимо перевезти землю из одного места в другое, необходимо учитывать как количество перевозимой земли, так и наличие свободного места там, куда она перевозится. Цена транспортировки одной молекулы пропорциональна ее весу и расстоянию перевозки, а значит, полная цена перевозки должна быть пропорциональна сумме произведений весов молекул на пройденное расстояние».
Формально, Мондж рассматривает следующую задачу: «Пусть на плоскости заданы две области, ABCD и abcd, ограниченные произвольным контуром, непрерывные или дискретные, найти пусть которому должна следовать каждая молекула М первой области, чтобы перейти в некоторую молекулу m второго области, таким образом, что в результате этого перемещения область ABCD была перемещена в область abcd, и сумма произведений веса каждой молекулы на пройденное ей расстояние было минимальным». Мондж предложил геометрический метод решения данной задачи. Несмотря на его геометрическую интуитивность, он был не совсем верен, как заметил в 1928 году Аппель.
§3.2. Теорема Эгервари
В 1931 году Эгервари опубликовал «взвешенный» вариант теоремы Кёнига: Пусть элементы a_ij матрицы A размера n неотрицательные целые числа, и пусть для некоторых наборов неотрицательных чисел L_i и M_j выполнены условия: а_ij <= L_i + M_j (для всех I и j), тогда получим что min sum (L_k + M_k) = max (a_1p(1) + .. + a_np(n)), где максимум берется по всем перестановкам p.
Доказательство, предложенное Эгервари, сугубо алгоритмично и ведет к алгоритму, использующему «невзвешенную» задачу о паросочетании в качестве подзадачи. Пусть W – максимальное число в матрице А, тогда алгоритму потребуется применить задачу о Паросочетании O(nW) раз, а суммарное время работы алгоритма составит O(nWB(n)), где B(n) – наилучшая оценка времени работы алгоритма нахождения максимального Паросочетания. Этот метод послужил основой для сформулированного в 1955 году «Венгерского метода» Куна, которые мы подробнее рассмотрим далее.
Другим результатом Эгервари было установление следующей двойственной природы задачи о взвешенном Паросочетании: пусть G = (V, E) – двудольный граф и пусть w: E -> R неотрицательная весовая функция. Тогда вес максимального Паросочетания в G равняется минимальному значению y(V), где y: V -> R, таково что: y >= 0 и y_u + y_v >= w(uv).
§3.3. 1940е годы
Первый алгоритм для задачи о назначениях был опубликован Истерфилдом (Easterfield) в 1946 году. Мотивация этого алгоритма была следующей: «Что касается исследования в области задач демобилизации вооруженных сил, представляется возможным организовать переход людей из расформированных отрядов в другие отряды таким образом, чтобы их не пришлось потом переводить снова то момента их демобилизации. Более того, исследования количеств людей в различных группах позволили бы организовать этот процесс с наименьшим возможным количеством задержек. К сожалению, непредвиденный конец Японской войны не дал возможности проверить эффективность этой теории в деле. Тем не менее, алгоритм, изложенный в данной статье, возник именно в процессе исследований в этой области».
Похоже, что Истерфилд работал, не имея представления о других исследованиях в данной области. Он сформулировал и доказал теорему эквивалентную теореме Халла, а также представил метод решения данной задачи, из которого можно извлечь результаты, полученные Эгервари.
Идея Истерфильда основана на переборе всех подмножеств вершин в лексикографическом порядке, что привело к алгоритму со сложностью O(n^2 * 2^n) (что является улучшением по сравнению с перебором всех перестановок, на который требуется n! действий). Этот алгоритм был в дальнейшем уточнен в 1960 году.
Настоящий прорыв в решении задачи о назначениях был совершен в 1951 году, когда Диниц показал, что задача о назначениях может быть сформулирована как линейная программа, автоматически обладающая целочисленным решением. Таким образом, к задаче о назначениях стало возможно применить симплекс-метод.
Диниц рассматривал задачу о назначениях применительно к распределению работы среди людей. Он писал: «Как было сказано, в задаче о назначениях возникает лишь конечное число перестановок. Поэтому с математической точки зрения достаточно рассмотреть все перестановки и выбрать из них оптимальную. Например, если мы рассмотрим задачу для хотя бы для 10 человек, возникнет более трех с половиной миллионов перестановок, поэтому данный математический подход окажется неприменимым на практике».
В 1949 году Робинсон в отчете для RAND написал что его «неудачный попытки» решения задачи о коммивояжере привели к интересному алгоритму решения задачи о назначениях, основанном на «отмене циклов». Идея его была следующей: рассмотрим произвольную перестановку p. Для всех i,j определим «длину» L_ij = a_jp(j) – a_ip(i) если j != p(i), и бесконечности в противном случае. Если в графе с такими длинами возникнет цикл отрицательного веса, это позволит сразу улучшить перестановку p. Если же такого цикла не окажется, то перестановка p оптимальна. Как отметил Робинсон, данный метод можно применять к графам из 50 вершин, при условии наличия необходимых вычислительных средств.
§3.3. Ранние 1950е
На семинаре по теории игр в Принстонском Университете в 1951 году, Фон Нейман (Von Neumann) указал на то, что задача о назначениях может быть сформулирована в виде игры с нулевой суммой для двух игроков, и нахождение ее решения эквивалентно поиску оптимальной стратегии в этой игре. Игра устроена следующим образом: пусть задана матрица A. Первый игрок будет играть строками этой матрицы, второй игрок – столбцами. Первый игрок выбирает номер строки, второй – номер столбца, после чего первый «платит» второму A_ij «денег». Индексы строк и столбцов чередоваться не могут, таким образом игра продолжается n раундов (где n – размер матрицы).
Сведение данной игры к задаче о назначениях не очевидно. В дальнейшем к этой идее обращались Браун (Brown) и Робинсок. Фон Нейман также заметил, что поиск оптимальной стратегии по видимому можно осуществить за время пропорциональное некоторой степени n, что заметно меньше чем «очевидное» решение за время n!. Тем не менее, никакой аргументации этого наблюдения не последовало. Похожие идеи также были в работах Дулмага (Dulmage) и Гальперина (Halperine) (1955) и Купманса (Koopmans) и Бекмана (Beckmann) (1955, 1957).
В работах Лорда (Lord) (1952) и Двайера (Dwyer) (1954), был изложен некоторый геометрический подход («метод оптимальных регионов»). Обзор методов решения задачи о назначениях по состоянию на 1953 год был сделан Моцкиным (Motzkin) в 1956 году.
§3.4. Вычислительные результаты начала 1950х годов
В статье, представленной в 1951 году на Симпозиуме по Линейным Неравенствам и Линейному Программированию в Вашингтоне, Воташ (Votaw) и Орден (Orden) упомянули, что для решения задачи о назначениях размера 10 * 10 требуется около 3 минут вычислений на машине SEAC (National Bureau of Standards Eastern Automatic Computer). В то же время для решения задачи о назначениях того же размера при использовании симплекс-метода требовалось около 20 минут.
Однако, в воспоминаниях Куна от 1991 года он пишет: «Эта история началась летом 1953 года, когда Национальное Бюро Стандартов США собрали группу выдающихся алгебраистов и специалистов по комбинаторике в Институте Численного анализа (INA) расположенного на территории Университета Калифорнии в Лос-Анджелесе. Из-за нехватки места, я делил офис с Тедом Моцкиным, чьи работы в области линейных неравенств продвинули эту теорию на десять лет вперед. Одной из новинок, презентованных в INA, был компьютер SWAC (Standards Western Automatic Computer). SWAC был меньше, но быстрее чем его предшественник – компьютер SEAC. В течение лета, Томпкинс (C.B. Tompkins) предпринимал попытки решить задачу о назначениях размера 10*10 на машине SWAC. Но так как эта задача является задачей линейного программирования со 100 неотрицательными переменными и 20 ограничивающими равенствами, ему это не удалось. В 1953 году в мире просто не существовало машины, способной справиться с такими объемами вычислений».