Алгоритм решения задачи о максимальном потоке

 

Задачу о максимальном потоке можно решать методом целочисленного линейного программирования. Однако существует более простой и эффективный метод, использующий особенности сетевой постановки задачи, – метод расстановки меток. Метод итерационный, каждая итерация включает два шага.

Шаг 1. Исходя из имеющегося допустимого потока производится расстановка пометок всех узлов и тем самым отыскивается путь, по которому можно увеличить исходный поток, не нарушая его допустимости. После этого определяется величина приращения потока.

Шаг 2. Имеющийся поток увеличивается по найденному пути на определённую величину.

 

Основу алгоритма составляет процедура мечения. Рассмотрим ее подробнее.

Метка узла j имеет следующую структуру: [i; ±; e(j)], где

i - номер узла, из которого помечен j (причем это не обязательно предок, может быть и потомок),

± - направление мечения («+», когда i - предок, j - потомок; «-», когда i - потомок, j -  предок),

e(j) - возможное приращение потока от источника s до узла j, не нарушающее ограничений задачи; определяется так:

если «+», т.е. существует дуга (ij)ÎА, то e(j) = min{с _ij - f_ij ;e(i)},

если «-», т.е. существует дуга (ji)ÎА, то e(j) = min{f_ji ;e(i)}.

Каждый узел сети может находиться в одном из трёх состояний:

1) не помечен, не просмотрен,

2) помечен, но не просмотрен,

3) помечен, просмотрен.

На каждой итерации мечение начинается с положения, когда все узлы не помечены и не просмотрены, кроме первого. Узел s всегда помечен. Его метка [*,*,¥], т. е. это источник потока бесконечной величины. Расстановка пометок производится строго в соответствии с порядком нумерации узлов сети. Для первого узла (очередного помеченного узла i) просматриваются все непомеченные узлы, связанные с ним дугами (ij)ÎА или (ji)ÎА.

Узел j может быть помечен из узла i, если узел i помечен; существует дуга (ij)ÎА и с_ij > f_ij  или существует дуга (ji)ÎА и f_ji > 0. Ранее уже было рассмотрено, как определять в этих случаях все элементы метки.

После того, как все «соседи» узла i просмотрены и по возможности помечены, узел i приобретает статус «помечен и просмотрен», а процедура продолжается для помеченных, но еще не просмотренных узлов. Процесс мечения на данной итерации завершается, когда оказывается помеченным сток t.

Величина e(t) определяет приращение потока через сеть на данной итерации - DV, а путь, по которому проводится дополнительный поток, отыскиваем следующим образом. Начиная с последнего узла t, просматриваем метки: если t помечен из j, ищем, откуда помечен j. Пусть он помечен из i, тогда ищем далее, откуда помечен i, и так продолжаем до прихода в источник s.

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

Начинать решение задачи можно с любого допустимого потока, в том числе с нулевого, так как он всегда допустим. Критерием окончания служит невозможность мечения узла t. При этом множество помеченных узлов представляет собой множество Х, непомеченных - , что определяет минимальный разрез. Отметим, что в окончательном решении все прямые дуги минимального разреза насыщены, т. е. с_ij = f_ij , а все обратные - несут нулевые потоки.

Пример

Требуется отыскать максимальный поток и минимальный разрез в сети, представленной на рис. 4.1. Пропускные способности указаны рядом с дугами. Исходный (ненулевой) поток задан: f₁₂ =1, f₂₃ =1, f₃₄ =1, f₄₅ =1, f₅₆ =1.

Решение задачи показано на рис. 4.2, 4.3 и в таблице 4.1.

[*,*,¥]                    [1,+,6]                      [4,+,3]

                      с = 6                      с = 4 f = 1

     1                              4                              5

с = 1 f = 1                с = 2 f = 1               с = 3 f = 1

 

               с = 3 f = 1                   с = 5

     2                              3                              6

  [3,-,1]                     [4,-,1]                      [3,+,1]  DV = 1

 

Рис. 4.1. Сетевая модель транспортной сети в исходном состоянии; показана первая расстановка пометок

 

 

[*,*,¥]                   [1,+,5]                       [4,+,3]

                с = 6 f = 1                  с = 4 f = 1

     1                              4                              5

с = 1 f = 1               с = 2 f = 0               с = 3 f = 1

 

               с = 3 f = 1                  с = 5 f = 1

     2                              3                              6

                                                                           [5,+,2]  DV = 2

Рис. 4.2. Сетевая модель после первого увеличения потока и второй расстановки пометок

 

 

[*,*,¥]                     [1,+,3]                     [4,+,1]

                с = 6 f =3                       с = 4 f = 3

     1                              4                              5

с = 1 f = 1               с = 2                           с = 3 f = 3

                                                                                                       минимальный

                с = 3 f = 1                 с = 5 f = 1                       разрез С(1,4,5; 2,3,6) = 4

     2                              3                              6 максимальный поток V = 4

 

Рис. 4.3. Сетевая модель с показанным на ней окончательным решением задачи; последний узел на этой итерации остался непомечен

 

 

                                                                                    Таблица 4.1

Узлы сети	И т е р а ц и и
	1	2	3
1	[*,*,¥]	[*,*,¥]	[*,*,¥]
2	[3,-,1]	-	-
3	[4,-,1]	-	-
4	[1,+,6]	[1,+,5]	[1,+,3]
5	[4,+,3]	[4,+,3]	[4,+,1]
6	[3,+,1]	[5,+,2]	-
DV	1	2	0
V	1+1=2	2+2=4
f12	1	1
f14	0+1=1	1+2=3
f23	1	1
f34	1-1=0	0
f36	0+1=1	1
f45	1	1+2=3
f56	1	1+2=3

 

Окончательное решение задачи - в колонке предпоследней итерации.

 

⇐ Предыдущая45678910111213Следующая ⇒

Поделиться: