Практическое занятие 5 Тема: сетевой алгоритм поиска оптимальных путей Контрольные вопросы

1. Необходимость поиска оптимальных путей.

2. Виды алгоритмов поиска оптимальных путей.

3. Сущность сетевого алгоритма поиска оптимальных путей.

4. Последовательность шагов для достижения оптимального пути.

Оптимальным является путь минимальной длины (ранга, стоимости и т.п.) максимальной ёмкости (пропускной способности и т.п.). При решении задач поиска оптимальных путей чаще всего возникает задача определения путей минимальной длины или ранга.

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

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

С помощью сетевого метода можно определить оптимальные по длине (рангу, стоимости, ёмкости, пропускной способности или другим характеристикам) пути из фиксированной вершины і к остальным вершинам сети (или из всех узлов сети к фиксированному узлу і ).

Сетевой метод построен на предоставлении каждой вершине q таких пометок:

Lq – длина пути из вершины і к вершине q;

Nq – номер вершины, который является предоконечным на пути из вершины і к вершине q;

*q – служебная пометка, сформированная в процессе поиска кратчайших путей для увеличения скорости сходимости алгоритма.

Сущность этого метода сводится к выполнению представленных ниже шагов (рис.5.1).

Шаг 1. Установление исходных пометок вершинам сети (вершинам графа):

Li = 0; Ni = 0; *i = 0,

где ^*і – исходная вершина ( вершина-источник);

Lq = ; Nq = 0; *_q = 0,

где q – остальные узлы сети, q i.

Шаг 2.Среди всех вершин j, у которых пометка ^*j = 0, выбираем вершину, которая имеет Lj = min ( при первоначальном выборе это всегда вершина-источник і).

Шаг 3. Для всех вершин q, смежных с j , выбираем ту, у которой *q = 0, проверяется выполнение неравенства

Lq > Lj + ljq,

где ljq – длина ветви от узла j к узлу q;

Lq, Lj – пометки узлов q и j, что определяют длину пути из узла і к узлам q и j соответственно.

Если неравенство выполняется, то старые пометки узла q – Lq и Nq заменяют на новые:

Lq = Lj + lj _q;

Nq = j.

Если неравенство не выполняется, то замена пометок узла q не производится.

Шаг 4. После проверки всех вершин, смежных с j, вершине присваивается пометка *j=1.

Шаг 5. Проверка завершения работы алгоритма по условию: (n – 1) вершина имеет пометку *n=1 (n – количество вершин сети). Если условие выполняется, то алгоритм работу завершает, иначе – осуществляется переход к шагу 2.

На рис. 5.1 изображен граф, возле вершин которого написаны пометки, сформированные в ходе поиска кратчайших путей из вершины і=1 к остальным вершинам графа. Последняя (нижняя) пометка возле каждой вершины содержит информацию о кратчайшем пути от вершины 1 графа. Цифры над ребрами – это длина ребер. Сформированные пометки предоставляют возможность определить длину пути и сам путь в виде последовательности вершин графа (узлов сети), которые его составляют.

Например, путь из второй вершины к первой вершине (или из первого узла ко второму узлу) имеет длину 45 (L₂=45), проходит через вершины 2–4–1; для третьей вершины L₃=85, путь проходит через вершины 3–2–4–1 и т.п. Длина пути определяется пометкой Lq узла, путь – пометкой Nq.

Пометки Nq из вершины выбираются до тех пор, пока на определенной вершине не будет Nq=і , где і – номер вершины-источника.

Например, для определения μ₃₁ (μ₁₃) просматриваются пометки вершины 3; L₃=85, N₃=2. Это означает, что длина пути L₃₁=85, путь проходит через вершину 2. Дальше отыскиваем N₂=4, то есть в пути есть вершина 4 и, наконец, N₄=1. Итак, путь μ₃₁ проходит через вершины 3–2–4–1; поскольку все ребра неориентированные, то μ₃₁=1–4–2–3. Аналогично определим: μ₅₁ =5–2–4–1.

Рассмотренный алгоритм может использоваться для поиска кратчайшего пути между двумя заданными вершинами j и x. Работу алгоритм при этом завершает, когда в качестве очередной выбираемого на шаге 2 алгоритма вершины j оказывается вершина х, то есть j = х.

Рисунок 5.1 – Поиск кратчайших путей сетевым методом

Рассмотренный алгоритм может быть использован для поиска оптимальных путей по другим критериям. Например, при поиске путей минимальной стоимости достаточно характеристикам ветвей lij придать смысл стоимости Ц_іj, тогда пометки Lq определят стоимость пути Ц_q. При поиске путей минимального ранга достаточно все значения характеристик ветвей задать lij =1, тогда Lq определят ранг пути Rq.