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

07.04.2014

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

Еще два примера применения алгоритма каскадного матричного умножения, впервые описанного в статье «Транзитивное замыкание запросом» http://infostart.ru/public/158512/

Заслуженно или нет, но задача поиска кратчайшего пути в графе получила широкую популярность. Она часто рассматривается в учебниках по программированию. Алгоритм поиска кратчайшего пути чаще других непростых алгоритмов приходится вспоминать и на практике. Поэтому будет интересным рассмотреть решение этой задачи не совсем обычным способом: с помощью языка запросов 1С. Тем более, что и исходные данные и результат решения задачи представляют собой таблицы.

Исходные данные задачи поиска кратчайшего пути в графе представляют собой таблицу G дуг графа и их весов как расстояний, соединяющих пункты - вершины графа

i	V	W	F
1	V1	W1	F1
2	V2	W2	F2
…	…	…	…
m	Vm	Wm	Fm

и  параметры &А, &Б, задающие начальную и конечную вершины пути.

В задаче требуется определить путь P – таблицу вида

i	V
1	&A
2	V2
3	V3
…	…
k	&B

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

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

Предлагаемый алгоритм состоит из пролога, рефрена и эпилога.

Пролог заключается в том, что к строкам исходной таблицы приписываются (union) строки таблицы

i	V	W	F
1	V1	V1	0
2	V2	V2	0
…	…	…	0
n	Vn	Vn	0

по числу вершин в графе.

Для этого используется запрос

SELECT V, W, F
  INTO G1
  FROM G
UNION
SELECT V, V, 0
  FROM G
UNION
SELECT W, W, 0
  FROM G
 

Рефрен состоит в том, чтобы соединить полученную на предыдущем шаге таблицу саму с собой по условию равенства конца дуги первого образа с началом дуги второго образа. При этом формируются все возможные пути из соединения пар смежных дуг. Сгруппировав полученное произведение таблиц по началу первой и концу второй дуги и выбрав агрегатной функцией минимумы сумм длин состыкованных дуг, мы получим таблицу минимальных расстояний для путей длины в две дуги (и менее). Очень важным является наличие в соединяемых таблицах строк вида (Vi, Vi, 0), отражающих соединение каждой вершины самой с собой путем нулевой длины. Именно их наличие включает во множество путей, из которых выбирается минимум, пути меньшей длины и, таким образом, помогает «накапливать» результат.

Рефрен состоит в выполнении запроса

SELECT L.V, H.W, MIN(L.F + H.F) AS F
  INTO G2
  FROM G1 AS L               
  JOIN G1 AS H
    ON L.W = H.V
  GROUP BY L.V, H.W
 

При каждом повторении рефрена охват длин путей будет увеличиваться в два раза, поэтому рефрен нужно повторить минимум ]Log2(N)[ раз, где N – число вершин или известный "диаметр" графа.

После завершения повторов рефрена таблица будет содержать минимальные расстояния между парами всех транзитивно-связанных вершин.

Теперь, чтобы выбрать собственно путь, нужно выбрать вершины графа по условию, чтобы сумма расстояния до нее от начальной вершины пути &A и расстояния от нее до конечной вершины &B была равна длине найденного кратчайшеuj пути. Первый элемент суммы также удобно использовать для упорядочивания пунктов найденного пути. Таким образом, эпилог запроса выглядит следующим образом:

SELECT H.V, L.F
  FROM G2 AS L
  JOIN G2 AS H
    ON L.W = H.V
    JOIN (SELECT F FROM G2 WHERE V = &a AND W = &b) AS X
      ON (X.F = L.F + H.F)
  WHERE L.V = &a AND H.W = &b
  ORDER BY L.F
 

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

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

А, во-вторых, при относительно небольших размерах графа в 100-200 вершин, лишними затратами можно попросту пренебречь, взамен получив очень несложный и удобный алгоритм.

Ну и, в третьих, еще есть возможности оптимизации алгоритма путем его некоторого усложнения.

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

Под критическим путем понимается  путь из заданной вершины &A в вершину &B, сумма расстояний переходов между пунктами  на котором МАКСИМАЛЬНА. Определение «критического пути» используется тогда, когда исходный граф представляет собой сетевой график какого-либо комплекса работ (проекта).  Этот путь показывает ключевые (критические) работы проекта, продолжительность выполнения которых непосредственно влияет на время выполнения проекта в целом. Чтобы определить критический путь, можно даже не переписывать приведенный запрос, заменяя агрегатную функцию с функции МИНИМУМ на МАКСИМУМ. Достаточно в исходной таблице использовать отрицательные значения расстояний.

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

ВЫБРАТЬ G.V, G.W, G.F
ПОМЕСТИТЬ G
ИЗ    &G КАК G
;
ВЫБРАТЬ V, W, F
ПОМЕСТИТЬ G1
ИЗ G
ОБЪЕДИНИТЬ
ВЫБРАТЬ V, V, 0
ИЗ G
ОБЪЕДИНИТЬ
ВЫБРАТЬ W, W, 0
ИЗ G
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G2
ИЗ G1 КАК L СОЕДИНЕНИЕ G1 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G4
ИЗ G2 КАК L СОЕДИНЕНИЕ G2 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G8
ИЗ G4 КАК L СОЕДИНЕНИЕ G4 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G16
ИЗ G8 КАК L СОЕДИНЕНИЕ G8 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G32
ИЗ G16 КАК L СОЕДИНЕНИЕ G16 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ F
ПОМЕСТИТЬ X
ИЗ G32 КАК G2
ГДЕ V = &a И W = &b
;
ВЫБРАТЬ H.V, L.F
ИЗ G32 КАК L СОЕДИНЕНИЕ G32 КАК H ПО L.W = H.V СОЕДИНЕНИЕ X ПО (X.F = L.F + H.F)
ГДЕ L.V = &a И H.W = &b
УПОРЯДОЧИТЬ ПО L.F
 

На следующем рисунке приведена последовательность шагов 1-5 определения кратчайшего пути между вершиной 1 и 17 в графе, вершины которого связаны последовательно: 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17.

Для тестирования предложенного алгоритма приведена обработка «Путепровод».  Она позволяет задавать дуги графа и их вес и находить кратчайший или критический путь. Кроме того,  в обработке запрограммирована возможность автоматически заполнить таблицу исходных данных связями станций московского или питерского метро. Тогда с помощью нее можно находить кратчайший путь между заданными станциями метро. 

Текст публикации

Все новости