Смекни!
smekni.com

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

=====324

@Рис. 12.8. Дерево кратчайшего маршрута

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

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

Public Id As Integer

Public X As Single

Public Y As Single

Public Links As Collection

Public Dist As Integer ' Расстояние от корня дерева пути.

Public NodeStatus As Integer ' Статус дерева маршрута.

Public InLink As PathSLink ' Связь, ведущая к узлу.

======325

Используя поле InLink, программа может перечислить узлы в пути от корня до узла I в обратном порядке при помощи следующего кода:

Dim node As PathSNode

Set node = I

Do

' Вывести узел.

Print node.Id

If node Is Root Then Exit Do

' Перейти к следующему узлу вверх по дереву.

If node.IsLink.Node1 Is node Then

Set node = node.InLink.Node2

Else

Set node = node.InLink.Node1

End If

Loop

Класс link в алгоритме включает поле InPathTree, которое указывает, является ли связь частью дерева кратчайшего маршрута.

Public Node1 As PathSNode

Public Node2 As PathSNode

Public Cost As Integer

Public InPathTree As Boolean

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

Установка меток

В начале этого алгоритма значения поля Dist корневого узла устанавливается равным 0. Затем корневой узел помещается в список возможных узлов, при этом значение поля NodeStatus этого узла принимает значение NOW_IN_LIST, указывая на то, что он находится в списке.

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

Затем алгоритм удаляет этот узел из списка, и устанавливает значение поля NodeStatus для этого узла равным WAS_IN_LIST, указывая на то, что этот узел теперь является частью дерева кратчайшего маршрута. Поля Dist и IsLink узла уже имеют правильные значения. Для каждого корневого узла, значение поля IsLink равно Nothing, а значение поля Dist равно нулю.

После этого алгоритм проверяет все связи, выходящие из выбранного узла. Если соседний узел на другом конце связи никогда не находился в списке возможных узлов, то алгоритм добавляет его к списку. Он устанавливает значение поля NodeStatus соседнего узла равным NOW_IN_LIST., а значение поля Dist — расстоянию от корневого узла до выбранного узла плюс цене связи. И, наконец, он присваивает значение полю InLink соседнего узла так, чтобы оно указывало на связь с соседним узлом.

========326

Во время проверки алгоритмом связей, выходящих из выбранного узла, если значение поля NodeStatus соседнего узла равно NOW_IN_LIST, то этот узел уже находится в списке возможных узлов. Алгоритм проверяет текущее значение Dist соседнего узла, проверяя, не будет ли путь через выбранный узел короче. Если это так, то он обновляет поля InLink и Dist соседнего узла и оставляет соседний узел в списке возможных узлов.

Алгоритм повторяет этот процесс, удаляя узлы из списка возможных узлов, проверяя соседние с ними узлы и добавляя соседние узлы в список до тех пор, пока список не опустеет.

На рис. 12.9 показана часть дерева кратчайшего маршрута. В этой точке алгоритм проверил узлы A и B, удалил их из списка возможных узлов, и проверил их связи. Узлы A и B уже добавлены к дереву кратчайшего маршрута, и теперь в списке возможных узлов находятся узлы C, D и E. Жирные стрелки на рис. 12.9 соответствуют значениям полей InLink узлов в этой точке. Например, значение поля InLink для узла E соответствует связи между узлами E и B.

После этого алгоритм ищет в списке возможных узлов узел с наименьшим значением Dist. В данной точке значения полей Dist узлов C, D и E равны 10, 21 и 22 соответственно, поэтому алгоритм выбирает узел C. Узел C удаляется из списка возможных узлов, и его полю NodeStatus присваивается значение WAS_IN_LIST. Теперь узел C является частью дерева кратчайшего маршрута, и его поля Dist и InLink имеют правильные значения.

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

Текущий кратчайший маршрут от корня в узел E — это путь A, B, E, полная цена которого равна 22. Но цена пути A, C, E равна всего 17., что меньше, чем текущая цена 22, поэтому алгоритм обновляет значение InLink для узла E, и присваивает полю Dist этого узла значение 17.

@Рис. 12.9. Часть дерева кратчайшего маршрута

=========327

Private Sub FindPathTree(root As PathSNode)

Dim candidates As New Collection

Dim i As Integer

Dim best_i As Integer

Dim best_dist As Integer

Dim new_dist As Integer

Dim node As PathSNode

Dim to_node As PathSNode

Dim link As PathSLink

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

' Найти ближайший к корню узел‑кандидат.

best_dist = INFINITY

For i = 1 To candidates.Count

new_dist = candidates(i).Dist

If new_dist < best_dist Then

best_i = i

best_dist = new_dist

End If

Next i

' Добавить узел к дерева кратчайшего маршрута.

Set node = candidates(best_i)

candidates.Remove best_i

node.NodeStatus = WAS_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

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 в списке возможных узлов. Некоторые варианты этого алгоритма используют другие структуры данных для хранения списка возможных узлов. Например, можно было бы использовать упорядоченный связный список. При использовании этого метода потребуется только один шаг для того, чтобы найти следующий узел, который будет добавлен к дереву кратчайшего маршрута. Этот список будет всегда упорядоченным, поэтому узел на вершине списка всегда будет искомым узлом.

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

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

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

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