Алгоритм цветения - Blossom algorithm

В алгоритм цветения является алгоритм в теория графов для строительства максимальное соответствие на графиках. Алгоритм был разработан Джек Эдмондс в 1961 г.,^[1] и опубликовано в 1965 году.^[2] Учитывая общую график грамм = (V, E) алгоритм находит соответствие M такая, что каждая вершина в V инцидентен не более чем с одним ребром в M и |M| максимально. Сопоставление строится путем итеративного улучшения начального пустого сопоставления по увеличивающимся путям в графе. В отличие от двудольный При сопоставлении ключевой новой идеей является то, что цикл нечетной длины в графе (цветке) сокращается до одной вершины, а поиск продолжается итеративно в сокращенном графе.

Алгоритм работает во времени ${\displaystyle O(|E||V|^{2})}$, куда ${\displaystyle |E|}$ это количество края графика и ${\displaystyle |V|}$ это его количество вершины. Лучшее время работы ${\displaystyle O(|E||V|^{1/2})}$ для решения той же задачи можно использовать гораздо более сложный алгоритм Микали и Вазирани.^[3]

Основная причина того, что алгоритм цветения важен, состоит в том, что он дал первое доказательство того, что соответствие максимального размера может быть найдено с использованием полиномиального количества времени вычислений. Другая причина в том, что это привело к линейное программирование многогранное описание паросочетания многогранник, давая алгоритм минимальногомасса соответствие.^[4] Как разработано Александр Шрайвер, дальнейшее значение результата связано с тем, что это был первый многогранник, доказательство целостности которого "не следует просто из полная унимодулярность, и его описание стало прорывом в многогранная комбинаторика."^[5]

Расширение путей

Данный грамм = (V, E) и соответствующий M из грамм, вершина v является незащищенный если нет края M инцидент с v. Путь в грамм является альтернативный путь, если его края попеременно не входят M И в M (или в M а не в M). An расширение пути п - это чередующийся путь, который начинается и заканчивается в двух различных открытых вершинах. Обратите внимание, что количество несовпадающих ребер в увеличивающем пути на единицу больше, чем количество совпавших ребер, и, следовательно, общее количество ребер в увеличивающем пути нечетное. А соответствующее увеличение по расширяющемуся пути п это операция по замене M с новым соответствием ${\displaystyle M_{1}=M\oplus P=(M\setminus P)\cup (P\setminus M)}$.

К Лемма Берже, соответствие M максимальна тогда и только тогда, когда нет M-аугментация пути в грамм.^[6][7] Следовательно, соответствие либо максимальное, либо его можно увеличить. Таким образом, начиная с начального сопоставления, мы можем вычислить максимальное сопоставление, увеличивая текущее сопоставление дополнительными путями до тех пор, пока мы можем их найти, и возвращаться всякий раз, когда не осталось дополнительных путей. Мы можем формализовать алгоритм следующим образом:

   ВХОД: График грамм, начальное соответствие M на грамм   ВЫХОД: максимальное соответствие М * на граммA1 функция find_maximum_matching(грамм, M) : М *A2 п ← find_augmenting_path(грамм, M) A3 если п не пусто тогдаA4 возвращаться find_maximum_matching(грамм, увеличить M вдоль п) A5 ещеA6 возвращаться MA7 конец, еслиA8 конечная функция

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

Цветение и сокращение

Данный грамм = (V, E) и соответствующий M из грамм, а цвести B это цикл в грамм состоящий из 2к + 1 края которых ровно k принадлежать M, и где одна из вершин v цикла ( основание) такова, что существует чередующийся путь четной длины ( корень) из v к открытой вершине ш.

В поисках цветков:

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

Определить сжатый граф ГРАММ' как график, полученный из грамм к договор каждый край B, и определим согласованное соответствие M ’ как соответствие ГРАММ' соответствующий M.

ГРАММ' имеет M ’-автоматический путь если и только если грамм имеет M-augmenting path, и что любой M ’-автоматический путь П' в ГРАММ' возможно поднял для M-аугментация пути в грамм путем отмены сжатия B так что сегмент П' (если есть) прохождение через v_B заменяется соответствующим сегментом, проходящим через B.^[8] Более подробно:

• если П' проходит через сегмент u → v_B → ш в ГРАММ', то этот отрезок заменяется отрезком u → (u ’→ ... → w’) → w в грамм, где цветут вершины ты и w ’ и сторона B, (u ’→ ... → w’), идущий от ты к w ’ выбираются так, чтобы новый путь по-прежнему чередовался (ты выставлен в отношении ${\displaystyle M\cap B}$, ${\displaystyle \{w',w\}\in E\setminus M}$).

• если П' имеет конечную точку v_B, то отрезок пути u → v_B в ГРАММ' заменяется сегментом u → (u ’→ ... → v’) в грамм, где цветут вершины ты и v ’ и сторона B, (u ’→ ... → v’), идущий от ты к v ’ выбираются так, чтобы путь был чередующимся (v ’ выставлен, ${\displaystyle \{u',u\}\in E\setminus M}$).

Таким образом можно сжимать цветы и выполнять поиск в сжатых графах. Это сокращение лежит в основе алгоритма Эдмондса.

В поисках пути к увеличению

При поиске расширяющегося пути используется вспомогательная структура данных, состоящая из лес F чьи отдельные деревья соответствуют определенным частям графа грамм. На самом деле лес F то же самое, что использовалось бы для поиска максимального соответствия в двудольные графы (без необходимости сжимать цветы). На каждой итерации алгоритм либо (1) находит увеличивающий путь, (2) находит цветок и рекурсивно переходит на соответствующий сжатый граф, либо (3) делает вывод, что дополнительных путей нет. Вспомогательная структура создается с помощью дополнительной процедуры, обсуждаемой ниже.^[8]

В процедуре построения рассматриваются вершины v и края е в грамм и постепенно обновляет F по мере необходимости. Если v находится на дереве Т леса, мы позволяем корень (v) обозначают корень Т. Если оба ты и v находятся в одном дереве Т в F, мы позволяем расстояние (u, v) обозначим длину единственного пути из ты к v в Т.

    ВХОД: График грамм, соответствие M на грамм    ВЫХОД: увеличивающий путь п в грамм или пустой путь, если ничего не найдено B01 функция find_augmenting_path(грамм, M) : пB02 F ← пустой лесB03 снять отметку со всех вершин и ребер в граммотметьте все края MB05 для каждого открытая вершина v делатьB06 создать одноэлементное дерево { v } и добавьте дерево в FB07 конец дляB08 пока есть непомеченная вершина v в F с расстояние (v, корень (v)) четное делатьB09 пока существует неотмеченное ребро е = { v, ш } делатьB10 если ш не в F тогда                   // ш совпадает, поэтому добавьте е и w 's совпал край с FB11 Икс ← вершина соответствует ш в MB12 добавить края { v, ш } и { ш, Икс } к дереву vB13 ещеB14 если расстояние (ш, корень (ш)) странно тогда                       // Ничего не делать. B15 ещеB16 если корень (v) ≠ корень (ш) тогда                           // Сообщаем об увеличении пути в F ${\displaystyle \cup }$ { е } .B17 п ← путь (корень(v) → ... → v) → (ш → ... → корень(ш)) B18 возвращаться пB19 еще                           // Сжать цветок в грамм и ищем путь в сжатом графе. B20 B ← цветение образовано е и края на пути v → ш в ТB21 G ’, M’ ← договор грамм и M к BB22 П' ← find_augmenting_path(ГРАММ', M ’) B23 п ← лифт П' к граммB24 возвращаться пB25 конец, еслиB26 конец, еслиB27 конец, еслиB28 отметка края еB29 конец покаB30 отметка вершины vB31 конец покаB32 возвращаться пустой путь B33 конечная функция

Примеры

Следующие четыре рисунка иллюстрируют выполнение алгоритма. Пунктирными линиями обозначены края, которых в настоящее время нет в лесу. Сначала алгоритм обрабатывает опушку вне леса, которая вызывает расширение текущего леса (строки B10 - B12).

Затем он обнаруживает цветок и сжимает график (линии B20 - B21).

Наконец, он находит увеличивающийся путь P 'в сжатом графе (линия B22) и поднимает его до исходного графа (линия B23). Обратите внимание, что способность алгоритма сжимать цветы здесь имеет решающее значение; алгоритм не может найти п непосредственно в исходном графе, потому что в строке B17 алгоритма рассматриваются только ребра вне леса между вершинами на четном расстоянии от корней.

Анализ

Лес F построенный find_augmenting_path () функция - переменный лес.^[9]

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

Каждая итерация цикла, начиная со строки B09, либо добавляет к дереву Т в F (строка B10) или находит путь увеличения (линия B17), или находит цветок (линия B20). Нетрудно заметить, что время работы ${\displaystyle O(|E||V|^{2})}$.

Двудольное соответствие

Когда грамм является двудольный, нечетных циклов в грамм. В этом случае соцветия никогда не будут обнаружены, и можно просто удалить строки B20 - B24 алгоритма. Таким образом, алгоритм сводится к стандартному алгоритму для построения сопоставлений максимальной мощности в двудольных графах.^[7] где мы неоднократно ищем дополнительный путь простым обходом графа: это, например, случай Алгоритм Форда – Фулкерсона.

Взвешенное соответствие

Задачу согласования можно обобщить, присвоив веса ребрам в грамм и просят набор M который производит сопоставление максимального (минимального) общего веса: это максимальное соответствие веса проблема. Эта проблема может быть решена с помощью комбинаторного алгоритма, который использует невзвешенный алгоритм Эдмондса в качестве подпрограммы.^[6] Колмогоров предлагает эффективную реализацию этого на C ++.^[10]

Рекомендации

1. Эдмондс, Джек (1991), «Взгляд на небеса», в J.K. Ленстра; A.H.G. Риннуй Кан; А. Шрайвер (ред.), История математического программирования --- сборник личных воспоминаний, CWI, Амстердам и Северная Голландия, Амстердам, стр. 32–54.
2. Эдмондс, Джек (1965). «Дорожки, деревья и цветы». Может. J. Math. 17: 449–467. Дои:10.4153 / CJM-1965-045-4.
3. Микали, Сильвио; Вазирани, Виджай (1980). An O (V^1/2E) алгоритм поиска максимального совпадения в общих графах. 21-й ежегодный симпозиум по основам компьютерных наук. Издательство IEEE Computer Society Press, Нью-Йорк. С. 17–27.
4. Эдмондс, Джек (1965). «Максимальное соответствие и многогранник с 0,1-вершиной». Журнал исследований Национального бюро стандартов Раздел B. 69: 125–130. Дои:10.6028 / jres.069B.013.
5. Шрайвер, Александр (2003). Комбинаторная оптимизация: многогранники и эффективность. Алгоритмы и комбинаторика. Берлин Гейдельберг: Springer-Verlag. ISBN  9783540443896.
6. Ловас, Ласло; Пламмер, Майкл (1986). Теория соответствия. Akadémiai Kiadó. ISBN  963-05-4168-8.
7. Карп, Ричард, "Алгоритм недвудольного соответствия Эдмондса", Примечания к курсу. У. К. Беркли (PDF), заархивировано из оригинал (PDF) на 2008-12-30
8. Тарджан, Роберт, «Отрывочные заметки о невероятном алгоритме усыхания цветения Эдмондса для общего согласования», Примечания к курсу, факультет компьютерных наук, Принстонский университет (PDF)
9. Кеньон, Клэр; Ловас, Ласло, «Алгоритмическая дискретная математика», Технический отчет CS-TR-251-90, Департамент компьютерных наук, Принстонский университет
10. Колмогоров, Владимир (2009), «Blossom V: новая реализация алгоритма идеального соответствия с минимальной стоимостью», Математическое программирование вычислений, 1 (1): 43–67, Дои:10.1007 / s12532-009-0002-8