Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
=======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. Сеть распределения работы
Распределение работы
Предположим, что имеется группа сотрудников, каждый из которых обладает определенными навыками. Предположим также, что существует ряд заданий, которые требуют привлечения сотрудника, обладающего заданным набором навыков. Задача распределения работы (work assignment) состоит в том, чтобы распределить работу между сотрудниками так, чтобы каждое задание выполнял сотрудник, имеющий соответствующие навыки.
Чтобы свести эту задачу к вычислению максимального потока, создадим сеть с двумя столбцами узлов. Каждый узел в левом столбце представляет одного сотрудника. Каждый узел в правом столбце представляет одно задание.
Затем сравним навыки каждого сотрудника с навыками, необходимыми для выполнения каждого из заданий. Создадим связь между каждым сотрудником и каждым заданием, которое он способен выполнить, и присвоим всем связям единичную пропускную способность.
Создадим узел‑источник и соединим его с каждым из сотрудников связью единичной пропускной способности. Затем создадим узел‑сток и соединим с ним каждое задание, снова при помощи связей с единичной пропускной способностью. На рис. 12.29 показана соответствующая сеть для задачи распределения работы с четырьмя сотрудниками и четырьмя заданиями.
Страницы: 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
