WikiDer > Алгоритм Йена - Википедия

Yens algorithm - Wikipedia

Алгоритм Йены вычисляет единый источник K-короткие пути без петель для график с неотрицательным край Стоимость.[1] Алгоритм был опубликован Jin Y. Yen в 1971 году и использует любые алгоритм кратчайшего пути найти лучший путь, затем переходит к поиску K - 1 отклонение от наилучшего пути.[2]

Алгоритм

Терминология и обозначения

ОбозначениеОписание
Размер графа, то есть количество узлов в сети.
В узел графа, где колеблется от к . Это означает, что является исходным узлом графа и является приемным узлом графа.
Стоимость грани между и , при условии, что и .
В кратчайший путь от к , куда колеблется от к . потом , куда это 2-й узел кратчайший путь и это третий узел кратчайший путь и так далее.
Путь отклонения от в узле , куда колеблется от к . Обратите внимание, что максимальное значение является , который является узлом непосредственно перед стоком в кратчайший путь. Это означает, что путь отклонения не может отклоняться от кратчайший путь у раковины. Пути и следуйте по тому же пути, пока узел, тогда край отличается от любого пути в , куда колеблется от к .
Корневой путь что следует за этим до узел .
Подъездной путь что начинается в узел и заканчивается у раковины.

Описание

Алгоритм можно разбить на две части, определяя первую k-кратчайший путь, , а затем определяя все остальные k-кратчайшие пути. Предполагается, что контейнер проведет k-самый короткий путь, тогда как контейнер , будет иметь потенциал k-короткие пути. Чтобы определить , то кратчайший путь от истока до раковины, любой эффективный алгоритм кратчайшего пути может быть использован.

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

Первый процесс можно далее разделить на три операции, выбрав , нахождение , а затем добавив в контейнер . Корневой путь, , выбирается путем нахождения подпути в что следует за первым узлы , куда колеблется от к . Тогда, если путь найден, стоимость ребра из установлен на бесконечность. Далее подъездная дорога, , находится путем вычисления кратчайшего пути от ответвительного узла, узла , в раковину. Удаление ранее использованных кромок из к гарантирует, что ответвление будет другим. , добавление корневого пути и ответвления добавляется к . Затем ребра, которые были удалены, т.е. для которых была установлена ​​бесконечная стоимость, восстанавливаются до своих исходных значений.

Второй процесс определяет подходящий путь для найдя путь в контейнере с наименьшей стоимостью. Этот путь удален из контейнера и вставлен в контейнер и алгоритм переходит к следующей итерации.

Псевдокод

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

функция ЙенКСП (График, источник, сток, К): // Определяем кратчайший путь от источника до приемника.    A [0] = Дейкстра (График, источник, сток); // Инициализируем набор для хранения потенциального k-го кратчайшего пути.    B = []; за k из 1 к K: // Узел ответвления находится в диапазоне от первого узла до предпоследнего узла в предыдущем k-кратчайшем пути.        за я из 0 к размер (A [k - 1]) - 2: // Узел ответвления извлекается из предыдущего k-кратчайшего пути, k - 1.            spurNode = A [k-1] .node (i); // Последовательность узлов от источника до ответвительного узла предыдущего k-кратчайшего пути.            rootPath = A [k-1] .nodes (0, я); для каждого путь p в А: если rootPath == p.nodes (0, i): // Удаляем ссылки, которые являются частью предыдущих кратчайших путей с одним и тем же корневым путем.                    удалить p.edge (i, i + 1) из График; для каждого узел rootPathNode в rootPath, кроме spurNode: удалить rootPathNode из График; // Вычислить путь ответвления от узла ответвления до стока.            spurPath = Dijkstra (График, spurNode, сток); // Весь путь состоит из корневого и ответвительного пути.            totalPath = rootPath + spurPath; // Добавляем в кучу потенциальный k-кратчайший путь.            если (totalPath не входит в B): B.append (totalPath); // Добавляем обратно ребра и узлы, которые были удалены из графа.            восстановить края к График; восстановить узлы в rootPath к График; если B пусто: // Это обрабатывает случай, когда нет ответвлений или не осталось ответвлений.            // Это могло произойти, если ответвления уже исчерпаны (добавлены в A),             // или нет никаких ответвлений - например, когда и исходная, и приемная вершины             // лежать в «тупике».            перемена; // Сортируем возможные k-кратчайшие пути по стоимости.        B.sort (); // Добавление пути с наименьшей стоимостью становится k-кратчайшим путем.        A [k] = B [0]; // На самом деле нам лучше использовать shift, так как мы удаляем первый элемент        B.pop (); возвращаться А;

Пример

Алгоритм k-кратчайшего пути Йена, K = 3, от A до F

В примере используется йен K-Алгоритм кратчайшего пути для вычисления трех путей из к . Алгоритм Дейкстры используется для вычисления наилучшего пути от к , который со стоимостью 5. Этот путь добавляется к контейнеру и становится первым k- кратчайший путь, .

Узел из становится ответвительным узлом с корневым путем, . Край, , удаляется, потому что он совпадает с корневым путем и путем в контейнере . Алгоритм Дейкстры используется для вычисления ответвления , который , стоимостью 8. добавлен в контейнер как потенциальный k-коротчайший путь.

Узел из становится ответвительным узлом с . Край, , удаляется, потому что он совпадает с корневым путем и путем в контейнере . Алгоритм Дейкстры используется для вычисления ответвления , который , стоимостью 7. добавлен в контейнер как потенциальный k-коротчайший путь.

Узел из становится ответвительным узлом с корневым путем, . Край, , удаляется, потому что он совпадает с корневым путем и путем в контейнере . Алгоритм Дейкстры используется для вычисления ответвления , который , стоимостью 8. добавлен в контейнер как потенциальный k-коротчайший путь.

Из трех путей в контейнере B, выбран, чтобы стать потому что у него самая низкая стоимость 7. Этот процесс продолжается до 3-го числа. k-коротчайший путь. Однако в рамках этой 3-й итерации обратите внимание, что некоторые ответвления не существуют. И путь, который выбран стать является .

Функции

Космическая сложность

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

Сложность времени

Временная сложность алгоритма Йена зависит от алгоритма кратчайшего пути, используемого при вычислении ответвлений, поэтому предполагается алгоритм Дейкстры. Алгоритм Дейкстры имеет худшую временную сложность, равную , но с использованием кучи Фибоначчи становится ,[3] куда количество ребер в графе. Поскольку алгоритм Йены делает обращается к Дейкстре при вычислении ответвлений, где - длина ответвлений. В сокращенном графике ожидаемое значение является , а в худшем случае . , временная сложность становится .[4]

Улучшения

Алгоритм Йены можно улучшить, используя кучу для хранения , множество потенциальных k-короткие пути. Использование кучи вместо списка улучшит производительность алгоритма, но не усложнит его.[5] Один из способов немного снизить сложность - пропустить узлы, где нет ответвлений. Этот случай возникает, когда все ответвительные пути от ответвительного узла были использованы в предыдущем . Также, если контейнер имеет пути минимальной длины, относительно путей в контейнере , затем их можно извлечь и вставить в контейнер поскольку более коротких путей найти не удастся.

Модификация Лоулера

Юджин Лоулер предложила модификацию алгоритма Йена, в которой путь дубликатов не вычисляется, в отличие от исходного алгоритма, в котором они вычисляются и затем отбрасываются, когда обнаруживаются дубликаты.[6] Эти дублирующиеся пути являются результатом вычисления ответвлений узлов в корне . Например, отклоняется от в каком-то узле . Любая подъездная дорога, куда , который рассчитывается, будет дублироваться, потому что они уже были рассчитаны во время итерация. Следовательно, только ответвительные пути для узлов, которые были на ответвительном пути должны быть рассчитаны, т.е. только куда колеблется от к . Чтобы выполнить эту операцию для , необходима запись для идентификации узла, в котором разветвленный от .

Смотрите также

Рекомендации

  1. ^ Йен, Джин Й. (1970). «Алгоритм поиска кратчайших маршрутов от всех исходных узлов к заданному месту назначения в общих сетях». Квартал прикладной математики. 27 (4): 526–530. Дои:10.1090 / qam / 253822. МИСТЕР 0253822.
  2. ^ а б c Йен, Джин Ю. (июль 1971 г.). "Поиск k Кратчайшие пути без петель в сети ». Наука управления. 17 (11): 712–716. Дои:10.1287 / mnsc.17.11.712. JSTOR 2629312.
  3. ^ Фредман, Майкл Лоуренс; Тарджан, Роберт Э. (1984). Кучи Фибоначчи и их использование в улучшенных алгоритмах оптимизации сети. 25-й ежегодный симпозиум по основам информатики. IEEE. С. 338–346. Дои:10.1109 / SFCS.1984.715934.CS1 maint: ref = harv (связь)
  4. ^ Булье, Эрик (2007). Маршрутизация пути в ячеистых оптических сетях. Чичестер, Англия: John Wiley & Sons. ISBN 9780470032985.
  5. ^ Брандер, Эндрю Уильям; Синклер, Марк С. Сравнительное исследование k-Алгоритмы кратчайшего пути. Департамент инженерии электронных систем, Университет Эссекса, 1995.
  6. ^ Лоулер, EL (1972). «Процедура вычисления k лучших решений задач дискретной оптимизации и ее применение к задаче поиска кратчайшего пути». Наука управления. 18 (7): 401–405. Дои:10.1287 / mnsc.18.7.401.

внешняя ссылка