Cтраница 1
Алгоритм расстановки меток, который мы используем, начинается с приписывания метки 1 одному из конечных заданий. [1]
Алгоритм расстановки меток ( label setting) всегда выбирает ребро, которое гарантированно является частью конечного дерева кратчайших путей. Он работает аналогично алгоритму построения минимального остовного дерева. Если ребро было добавлено кдереву, оно уже не будет удалено. [2]
Алгоритм расстановки меток всегда выбирает связь, которая гарантированно находится в дереве кратчайших путей. После удаления из списка возможных узел добавляется к дереву и уже не будет помещен в список - Алгоритм коррекции меток всегда выбирает первый узел из списка возможных, который не всегда является лучшим выбором. Значения полей Dist и InLinKnaH-ного узла могут и не быть лучшими возможными значениями. Но в конце концов алгоритм отыщет в списке узел, через который проходит более короткий путь к выбранному узлу. Тогда алгоритм обновляет поля Di st и InLink неправильно выбранного узла и помещает этот узел обратно в список возможных. [3]
Рассмотрим алгоритм расстановки меток, приведенный в § 2.3, который был использован для построения расписания при произвольном частичном упорядочении и двух процессорах. В нем метки расставлялись от уровня к уровню. Как следует из § 2.2, уровневая стратегия строит расписания для деревьев от уровня к уровню. [4]
Как и алгоритм расстановки меток, метод коррекции меток ( label correcting) начинает работать, присваивая полю Dist корневого узла нулевое значение и помещая корневой узел в список возможных. Значения Di st для других узлов устанавливается в бесконечность. Затем из списка возможных узлов выбирается первый узел и добавляется к дереву кратчайшего пути. [5]
В отличие от алгоритма расстановки меток этот алгоритм не может обрабатывать сети, которые содержат циклы с отрицательной стоимостью. Если встречается такой цикл, то алгоритм бесконечно перемещается по связям внутри него. Каждый раз, когда алгоритм проходит через цикл, сокращается расстояние до входящих в него узлов, при этом алгоритм снова помещает узлы в список возможных узлов и снова проверяет их. При следующей проверке узлов расстояние до них также уменьшится и тд. Этот процесс продолжается, пока расстояние не достигнет нижнего граничного значения - 32 768, сСЛИ программа использует для вычисления расстояний тип Integer. Если известно, что сеть содержит отрицательные циклы, то проще всего использовать алгоритм расстановки меток. [6]
Единственное изменение требуется внести в ту часть алгоритма расстановки меток, которая выполняется сразу после того, как алгоритм нашел в списке возможных узлов узел с наименьшим значением Dist. Перед удалением узла из списка алгоритм должен проверить, является ли данный узел конечным. Если это так, то дерево кратчайшего пути уже содержит правильный путь от начального до конечного узла, и алгоритм может завершить работу. [7]
Алгоритмы расстановки И коррекции меток используют список возможных связей, чтобы отслеживать узлы, которые могут быть добавлены кдереву кратчайшего пути, но по-разному управляют этим списком. Алгоритм расстановки меток всегда выбирает связь, которая обязательно окажется частью дерева кратчайшего пути. Алгоритм коррекции меток, описанный в этом разделе, выбирает любой узел в начале списка возможных связей. [8]
Другой способ заключается в использовании метода расстановки меток, который прекращает работу, когда находит путь к конечному узлу. Алгоритм расстановки меток помещает в дерево кратчайшего маршрута только действительно существующие пути, следовательно, в тотмомент, когда алгоритм добавит конечный узелвдерево, будет найден искомый кратчайший маршрут. В алгоритме, описанном ранее, это происходит, когда удаляется конечный узел из списка возможных узлов. [9]
Алгоритмы расстановки и коррекции меток используют аналогичные классы для представления узлов и связей. Класс узла TNode содержит поле Dist, которое указывает расстояние от корня до узла в растущем дереве кратчайшего пути. В алгоритме расстановки меток для Di s t задается True, как только узел добавлен кдереву и этот параметр уже не будет изменяться. В алгоритме коррекции меток параметр Dist может быть исправлен позже, когда ребро будет заменено другим. [10]
В отличие от алгоритма расстановки меток этот алгоритм не может обрабатывать сети, которые содержат циклы с отрицательной стоимостью. Если встречается такой цикл, то алгоритм бесконечно перемещается по связям внутри него. Каждый раз, когда алгоритм проходит через цикл, сокращается расстояние до входящих в него узлов, при этом алгоритм снова помещает узлы в список возможных узлов и снова проверяет их. При следующей проверке узлов расстояние до них также уменьшится и тд. Этот процесс продолжается, пока расстояние не достигнет нижнего граничного значения - 32 768, сСЛИ программа использует для вычисления расстояний тип Integer. Если известно, что сеть содержит отрицательные циклы, то проще всего использовать алгоритм расстановки меток. [11]