Наименьшие остовные деревья

Если задана сеть с ценой связей, то наименьшим остовным деревом (minimal spanning tree) называется остовное дерево, в котором суммарная цена всех связей в дереве будет наименьшей. Наименьшее остовное дерево можно использовать, чтобы связать все узлы в сети путем с наименьшей ценой.

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

Заметьте, что сеть может иметь несколько наименьших остовных деревьев. На рис. 12.6 показаны два изображения сети с двумя различными наименьшими остовными деревьями, которые нарисованы жирными линиями. Полная цена обоих деревьев равна 32.

 

@Рис. 12.5. Магистральные телефонные кабели, связывающие шесть городов

 

========320

 

@Рис. 12.6. Два различных наименьших остовных дерева для одной сети

 

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

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

Подобные алгоритмы, которые находят глобальный оптимум, при помощи серии локально оптимальных приближений называются поглощающими алгоритмами[RV20] (greedy algorithms). Можно представлять себе поглощающие алгоритмы как алгоритмы типа восхождения на холм, не являющиеся при этом эвристиками — они гарантированно находят наилучшее возможное решение.

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

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

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

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

 

=========321

 

 

Private Sub FindSpanningTree(root As SpanNode)

Dim candidates As New Collection

Dim to_node As SpanNode

Dim link As SpanLink

Dim i As Integer

Dim best_i As Integer

Dim best_cost As Integer

Dim best_to_node As SpanNode

 

If root Is Nothing Then Exit Sub

   

' Сбросить флаг Marked для всех узлов и флаги

' Used и InSpanningTree для всех связей.

ResetSpanningTree

 

' Начать с корня остовного дерева.

root.Marked = True

Set best_to_node = root

 

Do

   ' Добавить связи последнего узла в список

   ' возможных связей.

   For Each link In best_to_node.Links

      If Not link.Used Then

          candidates.Add link

          link.Used = True

      End If

   Next link

 

   ' Найти самую короткую связь в списке возможных

   ' связей, которая ведет к узлу, которого еще нет

   ' в дереве.

   best_i = 0

   best_cost = INFINITY

   i = 1

   Do While i <= candidates.Count

      Set link = candidates(i)

      If link.Node1.Marked Then

      Set to_node = link.Node2

      Else

          Set to_node = link.Node1

      End If

      If to_node.Marked Then

          ' Связь соединяет два узла, которые

          ' оба находятся в дереве.

          ' Удалить ее из списка возможных связей.

          candidates.Remove i

      Else

          If link.Cost < best_cost Then

              best_i = i

              best_cost = link.Cost

              Set best_to_node = to_node

          End If

          i = i + 1

      End If

   Loop

       

   ' Если больше не осталось связей, которые можно

   ' было бы добавить, то мы сделали все, что могли.

   If best_i < 1 Then Exit Do

 

   ' Добавить наилучшую связь и узел на ее конце в дерево.

   Set link = candidates(best_i)

   link.InSpanningTree = True

   candidates.Remove best_i

       

   best_to_node.Marked = True

Loop

 

GotSpanningTree = True

   

' Перерисовать сеть.

DrawNetwork

End Sub

 

Этот алгоритм проверяет каждую связь не более одного раза. При проверке каждой связи, она добавляется в список возможных связей, а затем удаляется из него. Если этот список находится в приоритетной очереди на основе пирамид, то для вставки или удаления элемента из очереди потребуется время порядка O(log(N)), где — число связей в сети. В этом случае полное время выполнения алгоритма будет порядка O(N * log(N)).

Если список возможных связей находится в коллекции, как в вышеприведенном коде, то для поиска в списке связи с наименьшей ценой потребуется время порядка O(N), при этом полное время выполнения алгоритма будет порядка O(N²). Для малых N производительность будет приемлемой. Если же число связей в сети достаточно велико, то список возможных связей следует хранить в приоритетной очереди, а не в коллекции.

Программа Span использует этот алгоритм для поиска наименьшего остовного дерева. Эта программа аналогична программе NetEdit. Она позволяет загружать, редактировать и сохранять на диске файлы, представляющие сеть. Если выбрать какой‑либо узел в программе двойным щелчком мыши, то программа найдет и выведет на экран наименьшее остовное дерево с корнем в этом узле. На рис. 12.7 показано окно программы Span, в котором показано наименьшее остовное дерево с корнем в узле 9.

 

======322-323

 

@Рис. 12.7. Программа Span

 

Кратчайший маршрут

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

На рис. 12.8 показано дерево, в котором дерево кратчайшего маршрута с корнем в узле A нарисовано жирной линией. Это дерево изображает кратчайший маршрут из узла A до всех остальных узлов в сети. Например, кратчайший маршрут из узла A в узел F проходит через узлы A, C, E, F.

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

Алгоритмы установки меток (label setting) всегда выбирают связь, которая гарантированно окажется частью конечного кратчайшего маршрута. Этот метод работает аналогично методу поиска наименьшего остовного дерева. Если связь добавлена в дерево, то она не будет удалена позже.

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

 

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

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

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

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

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

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

Коррекция меток

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

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

 

=======333

 

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

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

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

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