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

первый узел в списке возможных узлов.

После этого алгоритм проверяет узлы, соседние с выбранным, выясняя, будет

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

текущее значение поля 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, если длина пути задана целым числом. Если известно, что в сети

имеются циклы с отрицательной ценой, то проще всего просто использовать для

работы с ней метод установки, а не коррекции меток.

Программа PathC использует этот алгоритм коррекции меток для вычисления

кратчайшего маршрута. Она аналогична программе PathS, но использует метод

коррекции, а не установки меток.

=======333

Варианты метода коррекции меток

Алгоритм коррекции меток позволяет очень быстро выбрать узел из списка

возможных узлов. Он также может вставить узел в список всего за один или

два шага. Недостаток этого алгоритма заключается в том, что когда он

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

хороший выбор. Если алгоритм выбирает узел до того, как его поля Dist и

InLink получат свои конечный значения, он должен позднее скорректировать

значения этих полей и снова поместить узел в список возможных узлов. Чем

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

времени это занимает.

Варианты этого алгоритма пытаются повысить качество выбора узлов без

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

практике, состоит в том, чтобы добавлять узлы одновременно в начало и конец

списка возможных узлов. Если узел раньше не попадал в список возможных

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

был раньше в списке возможных узлов, но сейчас его там нет, алгоритм

вставляет его в начало списка. При этом повторное обращение к узлу

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

списку.

Идея, заключенная в таком подходе, состоит в том, чтобы если алгоритм

совершает ошибку, она исправлялась как можно быстрее. Если ошибка не будет

исправлена в течение достаточно долгого времени, алгоритм может

использовать неправильную информацию для построения длинных ложных путей,

которые затем придется исправлять. Благодаря быстрому исправлению ошибок,

алгоритм может уменьшить число неверных путей, которые придется

перестроить. В наилучшем случае, если все соседние узлы все еще находятся в

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

предотвратит построение неверных путей.

Другие задачи поиска кратчайшего маршрута

Описанные выше алгоритмы поиска кратчайшего маршрута вычисляли все

кратчайшие пути из корневого узла до всех остальных узлов в сети.

Существует множество других типов задачи нахождения кратчайшего маршрута. В

этом разделе обсуждаются три из них: двухточечный кратчайший маршрут (point-

to-point shortest path), кратчайший маршрут для всех пар(all pairs shortest

path) и кратчайший маршрут со штрафами за повороты.

Двухточечный кратчайший маршрут

В некоторых приложениях может понадобиться найти кратчайший маршрут между

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

не важны. Простой способ решить эту задачу — вычислить полное дерево

кратчайшего маршрута при помощи метода установки или коррекции меток, а

затем выбрать из дерева кратчайший путь между двумя точками.

Другой способ заключается в использовании метода установки меток, который

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

установки меток добавляет к дереву кратчайшего маршрута только те пути,

которые обязательно должны в нем находиться, следовательно, в тот момент,

когда алгоритм добавит конечный узел в дерево, будет найден искомый

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

когда алгоритм удаляет конечный узел из списка возможных узлов.

=======334

Единственное изменение требуется внести в часть алгоритма установки меток,

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

возможных узлов узел с наименьшим значением Dist. Перед удалением узла из

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

искомым. Если это так, то дерево кратчайшего маршрута уже содержит

кратчайший маршрут между начальным и конечным узлами, и алгоритм может

закончить работу.

' Найти ближайший к корню узел в списке возможных узлов.

:

' Проверить, является ли этот узел искомым.

If node = destination Then Exit Do

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

:

На практике, если две точки в сети расположены далеко друг от друга, то

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

полного дерева кратчайшего маршрута. Алгоритм выполняется медленнее из-за

того, что в каждом цикле выполнения алгоритма проверяется, достигнут ли

искомый узел. С другой стороны, если узлы расположены рядом, то выполнение

этого алгоритма может потребовать намного меньше времени, чем построение

полного дерева кратчайшего маршрута.

Для некоторых сетей, таких как сеть улиц, можно оценить, насколько близко

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

сеть содержит все улицы южной Калифорнии, и две точки расположены на

расстоянии 10 миль, следует использовать версию, которая останавливается

после того, как найдет конечный узел. Если же точки удалены друг от друга

на 100 миль, возможно, меньше времени займет вычисление полного дерева

кратчайшего маршрута.

Вычисление кратчайшего маршрута для всех пар

В некоторых приложениях может потребоваться быстро найти кратчайший маршрут

между всеми парами узлов в сети. Если нужно вычислить большую часть из N2

возможных путей, может быть быстрее вычислить все возможные пути вместо

того, чтобы находить только те, которые нужны.

Можно записать кратчайшие маршруты, используя два двумерных массива, Dist и

InLinks. В ячейке Dist(I, J) находится кратчайший маршрут из узла I в узел

J, а в ячейке InLinks(I, J) — связь, которая ведет к узлу J в кратчайшем

пути из узла I в узел J. Эти значения аналогичны значениям Dist и InLink в

классе узла в предыдущем алгоритме.

Один из способов найти все кратчайшие маршруты заключается в том, чтобы

построить деревья кратчайшего маршрута с корнем в каждом из узлов сети при

помощи одного из предыдущих алгоритмов, и затем сохранить результаты в

массивах Dists и InLinks.

========335

Другой метод вычисления всех кратчайших маршрутов последовательно строит

пути, используя все больше и больше узлов. Вначале алгоритм находит все

кратчайшие маршруты, которые используют только первый узел и узлы на концах

пути. Другими словами, для узлов J и K алгоритм находит кратчайший маршрут

между этими узлами, который использует только узел с номером 1 и узлы J и

K, если такой путь существует

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

два первых узла. Затем он строит пути, используя первые три узла, первые

четыре узла, и так далее до тех пор, пока не будут построены все кратчайшие

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

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

сети.

Заметьте, что кратчайший маршрут между узлами J и K, использующий только

первые I узлов, включает узел I, только если Dist(J, K) > Dist(J, I) +

Dist(I, K). Иначе кратчайшим маршрутом будет предыдущий кратчайший маршрут,

который использовал только первые I - 1 узлов. Это означает, что когда

алгоритм рассматривает узел I, требуется только проверить выполнение

условия Dist(J, K) > Dist(J, I) + Dist(I, K). Если это условие выполняется,

алгоритм обновляет кратчайший маршрут из узла J в узел K. Иначе старый

кратчайший маршрут между этими двумя узлами остался бы таковым.

Штрафы за повороты

В некоторых сетях, в особенности сетях улиц, бывает полезно добавить штраф

и запреты на повороты (turn penalties) В сети улиц автомобиль должен

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

занимать больше времени, чем поворот направо или движение прямо. Некоторые

повороты могут быть запрещены или невозможны из-за наличия разделительной

полосы. Эти аспекты можно учесть, вводя в сеть штрафы за повороты.

Небольшое число штрафов за повороты

Часто важны только некоторые штрафы за повороты. Может понадобиться

предотвратить выполнение запрещенных или невозможных поворотов и присвоить

штрафы за повороты лишь на нескольких ключевых перекрестках, не определяя

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

узел, для которого заданы штрафы, на несколько узлов, которые будут неявно

учитывать штрафы.

Предположим, что требуется добавить один штраф за поворот на перекрестке

налево и другой штраф за поворот направо. На рис. 12.12 показан

перекресток, на котором требуется применить эти штрафы. Число рядом с

каждой связью соответствует ее цене. Требуется применить штрафы за вход в

узел A по связи L1, и затем выход из него по связям L2 или L3.

Для применения штрафов к узлу A, разобьем этот узел на два узла, по одному

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

две связи, поэтому узел A разбивается на два узла A1 и A2, и связи,

выходящие из узла A, заменяются соответствующими связями, выходящими из

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

узлов соответствует входу в узел A и повороту в сторону соответствующей

связи.

======336

@Рис. 12.12. Перекресток

Затем связь L1, входящая в узел A, заменяется на две связи, входящие в

каждый из двух узлов A1 и A2. Цена этих связей равна цене исходной связи L1

плюс штрафу за поворот в соответствующем направлении. На рис. 12.13 показан

перекресток, на котором введены штрафы за поворот. На этом рисунке штраф за

поворот налево из узла A равен 5, а за поворот направо —2.

Помещая информацию о штрафах непосредственно в конфигурацию сети, мы

избегаем необходимости модифицировать алгоритмы поиска кратчайшего

маршрута. Эти алгоритмы будут находить правильные кратчайшие маршруты с

учетом штрафов за повороты.

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

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

маршрут между узлами I и J, но узел I оказался разбит на несколько узлов.

Полагая, что можно покинуть узел I по любой связи, можно создать ложный

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

Соединим этот узел связями с нулевой ценой с каждым из узлов, получившихся

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

корнем в ложном узле, то при этом будут найдены все кратчайшие маршруты,

содержащие любой из этих узлов. На рис. 12.14 показан перекресток с рис.

12.13, связанный с ложным корневым узлом.

@Рис. 12.13. Перекресток со штрафами за повороты

=======337

@Рис. 12.14. Перекресток, связанный с ложным корнем

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

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

узел J был разбит на несколько узлов, то вначале, как обычно, нужно найти

дерево кратчайшего маршрута с корнем в узле I. Затем проверяются все узлы,

на которые был разбит узел J и находится ближайший из них к корню дерева.

Путь к этому узлу и есть кратчайший маршрут к исходному узлу J.

Большое число штрафов за повороты

Предыдущий метод будет не слишком эффективным, если вы хотите ввести штрафы

за повороты для большинства узлов в сети. Лучше будет создать совершенно

новую сеть, которая будет включать информацию о штрафах.

. Для каждой связи между узлами A и B в исходной сети в новой сети

создается узел AB;

. Если в исходной сети соответствующие связи были соединены, то полученные

узлы также соединяются между собой. Например, предположим, что в

исходной сети одна связь соединяла узлы A и B, а другая — узлы B и C.

Тогда в новой сети нужно создать связь, соединяющую узел AB с узлом BC;

. Цена новой связи складывается из цены второй связи в исходной сети и

штрафа за поворот. В этом примере цена связи между узлом AB и узлом BC

будет равна цене связи, соединяющей узлы B и C в исходной сети плюс

штрафу за поворот при движении из узла A в узел B и затем в узел C.

На рис. 12.15 изображена небольшая сеть и соответствующая новая сеть,

представляющая штрафы за повороты. Штраф за поворот налево равен 3, за

поворот направо — 2, а за «поворот» прямо — нулю. Например, так как поворот

из узла B в узел E — это левый поворот в исходной сети, штраф для связи

между узлами BE и EF в новой сети равен 3. Цена связи, соединяющей узлы E и

F в исходной сети, равна 3, поэтому полная цена новой связи равна 3 + 3 =

6.

=======338

@Рис. 12.15. Сеть и соответствующая ей сеть со штрафами за повороты

Предположим теперь, что требуется найти для исходной сети дерево

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

сети ложный корневой узел, затем построим связи, соединяющие этот узел со

всеми связями, которые покидают узел D в исходной сети. Присвоим этим

связям ту же цену, которую имеют соответствующие связи в исходной сети. На

рис. 12.16 показана новая сеть с рис. 12.15 с ложным корневым узлом,

соответствующим узлу D. Дерево кратчайшего маршрута в этой сети нарисовано

жирной линией.

Чтобы найти кратчайший маршрут из узла D в узел C, необходимо проверить все

узлы в новой сети, которые соответствуют связям, заканчивающимся в узле C.

Страницы: 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