Реферат: VB, MS Access, VC++, Delphi, Builder C++ принципы(технология), алгоритмы программирования
For Each link In node.Links
If node Is link.Node1 Then
Set to_node = link.Node2
Else
Set to_node = link.Node1
End If
If to_node.NodeStatus = NOT_IN_LIST Then
' Узел раньше не был в списке возможных
' узлов. Добавить его в список.
candidates.Add to_node
to_node.NodeStatus = NOW_IN_LIST
to_node.Dist = best_dist + link.Cost
Set to_node.InLink = link
ElseIf to_node.NodeStatus = NOW_IN_LIST Then
' Узел находится в списке возможных узлов.
' Обновить значения его полей Dist и inlink,
' если это необходимо.
new_dist = best_dist + link.Cost
If new_dist < to_node.Dist Then
to_node.Dist = new_dist
Set to_node.InLink = link
End If
End If
Next link
Loop
GotPathTree = True
' Пометить входящие узлы, чтобы их было проще вывести на экран.
For Each node In Nodes
If Not (node.InLink Is Nothing) Then _
node.InLink.InPathTree = True
Next node
' Перерисовать сеть.
DrawNetwork
End Sub
Важно, чтобы алгоритм обновлял поля InLink и Dist только для узлов, в которых поле NodeStatus равно NOW_IN_LIST. Для большинства сетей нельзя получить более короткий путь, добавляя узлы, которые не находятся в списке возможных узлов. Тем не менее, если сеть содержит цикл, полная длина которого отрицательна, алгоритм может обнаружить, что можно уменьшить расстояние до некоторых узлов, которые уже находятся в дереве кратчайшего маршрута, при этом две ветви дерева кратчайшего маршрута окажутся связанными друг с другом, так что оно перестанет быть деревом.
На рис. 12.10 показана сеть с циклом отрицательной цены и «дерево» кратчайшего маршрута, которое получилось бы, если бы алгоритм обновлял цену узлов, которые уже находятся в дереве.
=======329
@Рис. 12.10. Неправильное «дерево» кратчайшего маршрута для сети с циклом отрицательной цены
Программа PathS использует этот алгоритм установки меток для вычисления кратчайшего маршрута. Она аналогична программам NetEdit и Span. Если вы не вставляете или не удаляете узел или связь, то можно выбрать узел при помощи мыши и программа при этом найдет и выведет на экран дерево кратчайшего маршрута с корнем в этом узле. На рис. 12.11 показано окно программы PathS с деревом кратчайшего маршрута с корнем в узле 3.
@Рис. 12.11. Дерево кратчайшего маршрута с корнем в узле 3
=======330
Варианты метода установки меток
Узкое место этого алгоритма заключается в поиске узла с наименьшим значением поля Dist в списке возможных узлов. Некоторые варианты этого алгоритма используют другие структуры данных для хранения списка возможных узлов. Например, можно было бы использовать упорядоченный связный список. При использовании этого метода потребуется только один шаг для того, чтобы найти следующий узел, который будет добавлен к дереву кратчайшего маршрута. Этот список будет всегда упорядоченным, поэтому узел на вершине списка всегда будет искомым узлом.
Это облегчит поиск нужного узла в списке, но усложнит добавление узла в него. Вместо того чтобы просто помещать узел в начало списка, его придется поместить в нужную позицию.
Иногда также требуется перемещать узлы в списке. Если в результате добавления узла в дерево кратчайшего маршрута уменьшилось кратчайшее расстояние до другого узла, который уже был в списке, то нужно переместить этот элемент ближе к вершине списка.
Предыдущий алгоритм и этот его новый вариант представляют собой два крайних случая управления списком возможных узлов. Первый алгоритм совсем не упорядочивает список и тратит достаточно много времени на поиск узлов в сети. Второй тратит много времени на поддержание упорядоченности списка, но может очень быстро выбирать из него узлы. Другие варианты используют промежуточные стратегии.
Например, можно использовать для хранения списка возможных узлов приоритетную очередь на основе пирамид, тогда можно будет просто выбрать следующий узел с вершины пирамиды. Вставка нового узла в пирамиду и ее переупорядочение будет выполняться быстрее, чем аналогичные операции для упорядоченного связного списка. Другие стратегии используют сложные схемы организации блоков для того, чтобы упростить поиск возможных узлов.
Некоторые из этих вариантов достаточно сложны. Из‑за этой их сложности эти алгоритмы для небольших сетей часто выполняются медленнее, чем более простые алгоритмы. Тем не менее, для очень больших сетей или сетей, в которых каждый узел имеет очень большое число связей, выигрыш от применения этих алгоритмов может стоить дополнительного усложнения.
Коррекция меток
Как и алгоритм установки меток, этот алгоритм начинает с обнуления значения поля Dist корневого узла и помещает корневой узел в список возможных узлов. При этом значения полей Dist остальных узлов устанавливаются равными бесконечности. Затем для вставки в дерево кратчайшего маршрута выбирается первый узел в списке возможных узлов.
После этого алгоритм проверяет узлы, соседние с выбранным, выясняя, будет ли расстояние от корня до выбранного узла плюс цена связи меньше, чем текущее значение поля Dist соседнего узла. Если это так, то поля Dist и InLink соседнего узла обновляются так, чтобы кратчайший маршрут к соседнему узлу проходил через выбранный узел. Если соседний узел при этом не находился в списке возможных узлов, то алгоритм также добавляет его к списку. Заметьте, что алгоритм не проверяет, попадал ли этот узел в список раньше. Если путь от корня до соседнего узла становится короче, узел всегда добавляется в список возможных узлов.
Алгоритм продолжает удалять узлы из списка возможных узлов, проверяя соседние с ними узлы и добавляя соседние узлы в список до тех пор, пока список не опустеет.
Если внимательно сравнить алгоритмы установки меток и коррекции меток, то видно, что они похожи. Единственное отличие заключается в том, как каждый из них выбирает элементы из списка возможных узлов для вставки в дерево кратчайшего маршрута.
=====331
Алгоритм установки меток всегда выбирает связь, которая гарантированно находится в дереве кратчайшего маршрута. При этом после того, как узел удаляется из списка возможных узлов, он навсегда помещается в дерево и больше не попадает в список возможных узлов.
Алгоритм корректировки всегда выбирает первый узел из списка возможных узлов, который не всегда может быть наилучшим выбором. Значения полей Dist и InLink этого узла могут быть не наилучшими из возможных. В этом случае алгоритм, в конце концов, найдет в списке узел, через который проходит более короткий путь к выбранному узлу. Тогда алгоритм обновляет поля Dist и InLink и снова помещает обновленный узел в список возможных узлов.
Алгоритм может использовать новый путь для создания других путей, которые он мог пропустить раньше. Помещая обновленный узел снова в список обновленных узлов, алгоритм гарантирует, что этот узел будет проверен снова и будут найдены все такие пути.
Private Sub FindPathTree(root As PathCNode)
Dim candidates As New Collection
Dim node_dist As Integer
Dim new_dist As Integer
Dim node As PathCNode
Dim to_node As PathCNode
Dim link As PathCLink
If root Is Nothing Then Exit Sub
' Сбросить поля Marked и NodeStatus для всех узлов,
' и флаги Used и InPathTree для всех связей.
ResetPathTree
' Начать с корня дерева кратчайшего маршрута.
root.Dist = 0
Set root.InLink = Nothing
root.NodeStatus = NOW_IN_LIST
candidates.Add root
Do While candidates.Count > 0
' Добавить узел в дерево кратчайшего маршрута.
Set node = candidates(1)
candidates.Remove 1
node_dist = node.Dist
node.NodeStatus = NOT_IN_LIST
' Проверить соседние узлы.
For Each link In node.Links
If node Is link.Node1 Then
Set to_node = link.Node2
Else
Set to_node = link.Node1
End If
' Проверить, существует ли более короткий
' путь через этот узел.
new_dist = node_dist + link.Cost
If to_node.Dist > new_dist Then
' Путь лучше. Обновить значения Dist и InLink.
Set to_node.InLink = link
to_node.Dist = new_dist
' Добавить узел в список возможных узлов,
' если его там еще нет.
If to_node.NodeStatus = NOT_IN_LIST Then
candidates.Add to_node
to_node.NodeStatus = NOW_IN_LIST
End If
End If
Next link
Loop
' Пометить входящие связи, чтобы их было проще вывести.
For Each node In Nodes
If Not (node.InLink Is Nothing) Then _
node.InLink.InPathTree = True
Next node
' Перерисовать сеть.
DrawNetwork
End Sub
В отличие от алгоритма установки меток, этот алгоритм не может работать с сетями, которые содержат циклы с отрицательной ценой. Если встречается такой цикл, то алгоритм бесконечно перемещается по связям внутри него. При каждом обходе цикла расстояние до входящих в него узлов уменьшается, при этом алгоритм снова помещает узлы в список возможных узлов, и снова может проверять их в дальнейшем. При следующей проверке этих узлов, расстояние до них также уменьшится, и так далее. Этот процесс будет продолжаться до тех пор, пока расстояние до этих узлов не достигнет нижнего граничного значения -32.768, если длина пути задана целым числом. Если известно, что в сети имеются циклы с отрицательной ценой, то проще всего просто использовать для работы с ней метод установки, а не коррекции меток.
Страницы: 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
