Смекни!
smekni.com

VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования (стр. 66 из 72)

Чтобы обновить решение, используя расширяющий путь, найдем наименьшую остаточную пропускную способность в пути. Затем скорректируем потоки в пути в соответствии с этим значением. Например, на рис. 12.23 наименьшая остаточная пропускная способность сетей в расширяющем пути равна 2. Чтобы обновить потоки в сети, к любой связи I‑J на пути добавляется поток 2, а из всех обратных им связей J‑I вычитается поток 2.

@Рис. 12.22. Остаточная сеть

========345

@Рис. 12.23. Расширяющий путь через остаточную сеть

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

Чтобы скорректировать остаточную сеть в этом примере, проследуем по расширяющему пути. Вычтем 2 из остаточной пропускной способности всех связей I‑J вдоль пути, и добавим 2 к остаточной пропускной способности соответствующей связи J‑I. На рис. 12.24 показана скорректированная остаточная сеть для этого примера.

Если больше нельзя найти ни одного расширяющего пути, то можно использовать остаточную сеть для вычисления потоков в исходной сети. Для каждой связи между узлами I и J, если остаточный поток между узлами I и J меньше, чем пропускная способность связи, то поток должен равняться пропускной способности минус остаточный поток. В противном случае поток должен быть равен нулю.

Например, на рис. 12.24 остаточный поток из узла A в узел C равен 1 и пропускная способность связи A‑C равна 3. Так как 1 меньше 3, то поток через узел будет равен 3 - 1 = 2. На рис. 12.25 показаны потоки в сети, соответствующие остаточной сети на рис. 12.24.

@Рис. 12.24. Скорректированная остаточная сеть

========346

@Рис. 12.25. Максимальные потоки

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

Этот метод имеет два отличия от метода поиска кратчайшего маршрута коррекцией меток. Во‑первых, этот метод не прослеживает связи с нулевой остаточной пропускной способностью. Алгоритм же кратчайшего маршрута проверяет все пути, независимо от их цены.

Во‑вторых, этот алгоритм проверяет все узлы не больше одного раза. Алгоритм поиска кратчайшего маршрута коррекцией меток, будет обновлять узлы и помещать их снова в список возможных узлов, если он позднее найдет более короткий путь от корня к этому узлу. При поиске расширяющего пути нет необходимости проверять его длину, поэтому не нужно обновлять пути и помещать узлы назад в список возможных узлов.

Следующий код демонстрирует, как можно вычислять максимальные потоки в программе на Visual Basic. Этот код предназначен для работы с неориентированными сетями, похожими на те, которые использовались в других программах примеров, описанных в этой главе. После завершения работы алгоритма он присваивает связи цену, равную потоку через нее, взятому со знаком минус, если поток течет в обратном направлении. Другими словами, если сеть содержит объект, представляющий связь I‑J, а алгоритм определяет, что поток должен течь в направлении связи J‑I, то потоку через связь I‑J присваивается значение, равное потоку, который должен был бы течь через связь J‑I, взятому со знаком минус. Это позволяет программе определять направление потока, используя существующую структуру узлов.

=======347

Private Sub FindMaxFlows()

Dim candidates As Collection

Dim Residual() As Integer

Dim num_nodes As Integer

Dim id1 As Integer

Dim id2 As Integer

Dim node As FlowNode

Dim to_node As FlowNode

Dim from_node As FlowNode

Dim link As FlowLink

Dim min_residual As Integer

If SourceNode Is Nothing Or SinkNode Is Nothing _

Then Exit Sub

' Задать размер массива остаточной пропускной способности.

num_nodes = Nodes.Count

ReDim Residual(1 To num_nodes, 1 To num_nodes)

' Первоначально значения остаточной пропускной способности

' равны значениям пропускной способности.

For Each node In Nodes

id1 = node.Id

For Each link In node.Links

If link.Node1 Is node Then

Set to_node = link.Node2

Else

Set to_node = link.Node1

End If

id2 = to_node.Id

Residual(id1, id2) = link.Capacity

Next link

Next node

' Повторять до тех пор, пока больше

' не найдется расширяющих путей.

Do

' Найти расширяющий путь в остаточной сети.

' Сбросить значения NodeStatus и InLink всех узлов.

For Each node In Nodes

node.NodeStatus = NOT_IN_LIST

Set node.InLink = Nothing

Next node

' Начать с пустого списка возможных узлов.

Set candidates = New Collection

' Поместить источник в список возможных узлов.

candidates.Add SourceNode

SourceNode.NodeStatus = NOW_IN_LIST

' Продолжать, пока список возможных узлов не опустеет.

Do While candidates.Count > 0

Set node = candidates(1)

candidates.Remove 1

node.NodeStatus = WAS_IN_LIST

id1 = node.Id

' Проверить выходящие из узла связи.

For Each link In node.Links

If link.Node1 Is node Then

Set to_node = link.Node2

Else

Set to_node = link.Node1

End If

id2 = to_node.Id

' Проверить, что residual > 0, и этот узел

' никогда не был в списке.

If Residual(id1, id2) > 0 And _

to_node.NodeStatus = NOT_IN_LIST _

Then

' Добавить узел в список.

candidates.Add to_node

to_node.NodeStatus = NOW_IN_LIST

Set to_node.InLink = link

End If

Next link

' Остановиться, если помечен узел‑сток.

If Not (SinkNode.InLink Is Nothing) Then _

Exit Do

Loop

' Остановиться, если расширяющий путь не найден.

If SinkNode.InLink Is Nothing Then Exit Do

' Найти наименьшую остаточную пропускную способность

' вдоль расширяющего пути.

min_residual = INFINITY

Set node = SinkNode

Do

If node Is SourceNode Then Exit Do

id2 = node.Id

Set link = node.InLink

If link.Node1 Is node Then

Set from_node = link.Node2

Else

Set from_node = link.Node1

End If

id1 = from_node.Id

If min_residual > Residual(id1, id2) Then _

min_residual = Residual(id1, id2)

Set node = from_node

Loop

' Обновить остаточные пропускные способности,

' используя расширяющий путь.

Set node = SinkNode

Do

If node Is SourceNode Then Exit Do

id2 = node.Id

Set link = node.InLink

If link.Node1 Is node Then

Set from_node = link.Node2

Else

Set from_node = link.Node1

End If

id1 = from_node.Id

Residual(id1, id2) = Residual(id1, id2) _

- min_residual

Residual(id2, id1) = Residual(id2, id1) _

+ min_residual

Set node = from_node

Loop

Loop ' Повторять, пока больше не останется расширяющих путей.

' Вычислить потоки в остаточной сети.

For Each link In Links

id1 = link.Node1.Id

id2 = link.Node2.Id

If link.Capacity > Residual(id1, id2) Then

link.Flow = link.Capacity - Residual(id1, id2)

Else

' Отрицательные значения соответствуют

' обратному направлению движения.

link.Flow = Residual(id2, id1) - link.Capacity

End If

Next link

' Найти полный поток.

TotalFlow = 0

For Each link In SourceNode.Links

TotalFlow = TotalFlow + Abs(link.Flow)

Next link

End Sub

=======348-350

Программа Flow использует метод поиска расширяющего пути для нахождения максимального потока в сети. Она похожа на остальные программы в этой главе. Если вы не добавляете или не удаляете узел или связь, вы можете выбрать источник при помощи левой кнопки мыши, а затем выбрать сток при помощи правой кнопки мыши. После выбора источника и стока программа вычисляет и выводит на экран максимальный поток. На рис. 12.26 показано окно программы, на котором изображены потоки в небольшой сети.

Приложения максимального потока

Вычисления максимального потока используются во многих приложениях. Хотя для многих сетей может быть важно знать максимальный поток, этот метод часто используется для получения результатов, которые на первый взгляд имеют отдаленное отношение к пропускной способности сети.

Непересекающиеся пути

Большие сети связи должны обладать избыточностью (redundancy). Для заданной сети, например такой, как на рис. 12.27, может потребоваться найти число непересекающихся путей из источника к стоку. При этом, если между двумя узлами сети есть множество непересекающихся путей, все связи в которых различны, то соединение между этими узлами останется, даже если несколько связей в сети будут разорваны.

Можно определить число различных путей, используя метод вычисления максимального потока. Создадим сеть с узлами и связями, соответствующими узлам и связям в коммуникационной сети. Присвоим каждой связи единичную пропускную способность.

@Рис. 12.26. Программа Flow

=====351

@Рис. 12.27. Сеть коммуникаций

Затем вычислим максимальный поток в сети. Максимальный поток будет равен числу различных путей от источника к стоку. Так как каждая связь может нести единичный поток, то ни один из путей, использованных при вычислении максимального потока, не может иметь общей связи.

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

Разделим каждый узел за исключением источника и стока на два узла, соединенных связью единичной пропускной способности. Соединим первый из полученных узлов со всеми связями, входящими в исходный узел. Все связи, выходящие из исходного узла, присоединим ко второму полученному после разбиения узлу. На рис. 12.28 показана сеть с рис. 12.27, узлы на которой разбиты таким образом. Теперь найдем максимальный поток для этой сети.

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

@Рис. 12.28. Коммуникационная сеть после преобразования

======352

@Рис. 12.29. Сеть распределения работы