Главная Бухгалтерия в кармане Учет расходов Экономия на кадровиках Налог на прибыль Как увеличить активы Основные средства
Главная ->  Гамильтоновы циклы 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 [ 133 ] 134 135 136 137 138 139 140 141



/4 18 Н 15 1

Xj ,4 Хг, 9

Ю

Рис. 12.25. (а) Совершенное паросочетание в G. (б) Паросочетание с распустившейся вершиной (в) Максимальное паросочетание.



4. Задача о назначениях

В этом разделе мы рассмотрим частный случай паросочетании - в двудольных графах [9, 18, 25]. Задан двудольный граф G = (X и , А), где X и Х* - независимые множества вершин и каждое ребро aj = (Xj, х^) £ А имеет х, g х^ g Х* и вес Cj. Мы хотим найти совершенное паросочетание графа G с максимальным (или минимальным) весом. Минимизационный вариант этой задачи хорошо известен в литературе как задача о назначениях (ЗН), и он без потери общности часто обсуждается в связи с полными двудольными графами.

Пусть 1 I = I Х* I = и. Рассматривая полный двудольный граф iir , , легко видеть, что задача о паросочетании для этого специального случая может быть решена с помощью методов, предназначенных для исследования потоков в сетях (из гл. 11), и поэтому нет необходимости в применении общего алгоритма паросочетания, изложенного в разд. 3 настоящей главы. Пусть добавлен искусственный источник s с дугами (s, х,), Vx g Z , имеющими единичную пропускную способность и нулевую стоимость (вес), и искусственный сток t с дугами (х^, ), V х^ g Х**, также имеющими единичную пропускную способность и нулевую стоимость (вес). Если рассматривать ребра из А как ориентированные, т.е. как дуги (х^, х^) с единичными пропускными способностями, то максимальный поток с минимальной стоимостью (весом) от S к г будет иметь значение п, а по этим дугам будет проходить ненулевой поток (со значением 1) ) с минимальной суммарной стоимостью (весом). Эти дуги из А будут тогда образовывать в G совершенное паросочетание с минимальной стоимостью (весом). Очевидно, что в случае такой специальной структуры графа многие шаги общего алгоритма нахождения потока минимальной стоимости (веса) могут быть упрощены с целью получения более эффективной процедуры для ЗН.

1) Отметим, что в соответствии с гл. 11, если все пропускные способности - целые, то потоки по дугам тоже будут целые, т. е. в нашем случае о или

нее [30]. Программа для вычислительной машины, приведенная в [30], дает зависимость вида О [и^>], а другая программа [29] - зависимость вида О \г^\. Эдмондс и Джонсон [29] привели типичный результат для задачи о паросочетании (на самом деле - для обш;ей задачи, обсуждавшейся в разд. 5, с = 1 или 2 и 1. Cj 10) с 300 вершинами и 1500 ребрами, потребовавшей для решения около 30 секунд на ИБМ 360/91.



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

4.1. Алгоритм для ЗН (случай минимизации)

Описанный здесь алгоритм был предложен Кёнигом [22], Эгер-вари [15] и Куном [23, 24] и известен как венгерский алгоритм.

4.1.1. Описание алгоритма

Присвоение начальных значений

Шаг 1. Вершинам из множеств Z° и X* графа G присвоить веса щ и соответственно, причем так, чтобы для любого ребра Uj - {xi, Хи) выполнялось неравенство + Cj.

Формирование графа G

Шаг 2. Построить специальный остовный подграф G графа G с данными текущими весами [п].

Построение дерева

Шаг 3. Если в G нет никакого альтернирующего дерева Т, то выращивать его, взяв в качестве корня некоторую экспонированную вершину Xi графа G, принадлежащую множеству X ; если экспонированных вершин нет, то перейти к шагу 7. Если альтернирующее дерево уже существует, то продолжать выращивать его. Если дерево Т окажется аугментальным, то перейти к шагу 4, а если венгерским - к шагу 5.

Аугменталъное дерево

Шаг 4. Улучшить текущее паросочетание, взаимно поменяв (вдоль аугментальной цепи) ребра, принадлежащие ему и ему не принадлежащие.

Отбросить дерево Т и перейти к шагу 3. Венгерское дерево

Шаг 5. Для ребер Uj = (х^, х^), не лежащих в G, одна концевая вершина которых принадлежит текущему дереву Т и помечена



1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 [ 133 ] 134 135 136 137 138 139 140 141

© 2024 Constanta-Kazan.ru
Тел: 8(843)265-47-53, 8(843)265-47-52, Факс: 8(843)211-02-95