Оптимизации алгоритма поиска k-кратчайших путей

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

Задача о к кратчайших путях является естественным и давно изученным обобщением задачи о кратчайших путях, в которой ищется не один, а несколько путей в порядке возрастания длины. Для заданного ориентированною графа G с неотрицательными весами ребер, положительною целого числа к и двух вершин s и t требуется найти к кратчайших путей из s в i в порядке возрастания длины. Методы поиска, к кратчайших путей используются во многих задачах. Иногда возникает необходимость найти путь, удовлетворяющий определенным ограничениям, помимо небольшой длины, однако эти ограничения могут быть плохо определены или их трудно оптимизировать. Типичное решение вычислить несколько коротких путей, и затем выбрать один из них с учетом других критериев. Пути могут использоваться для моделирования задач, имеющих известные решения, независимо от формулировки пути. Например, в модели к кратчайших путей автоматического перевода между естественными языками правильный перевод может быть найден экспертом-человеком. Перечисляя пути до появления этого известною решения, можно определить,

Исследования выполнены в рамках государственного задания ИВМиМГ СО РАН FWNM-2025-0001.

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

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

Применение концепции кратчайшего пути и алгоритма, поиска к кратчайших путей в химическом анализе было предложено Эгли в 2003 году [1]. В работе был построен орграф, узлы которого включали не только вещества, по и реакции. Хотя работа не была, направлена па создание метода генерации скелетных механизмов, опа предложила новую и полезную идею выделения основных путей реакции.

В данной работе представлена реализация алгоритма ранжирования беспетлевых путей Иена с оптимизацией. Обычная реализация прямо следует классической версии алгоритма Пепа [2], оптимизация использует подход построения обратного дерева, поскольку узлы каждого к-го кратчайшего пути без петель анализируются в обратном порядке. Хотя обе реализации имеют сложность О(кп(т + nlogn)), в худшем случае анализ повой реализации показал лучшую производительность в вычислительных экспериментах, проведенных для оценки их поведения в среднем случае.

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

• 1.    Алгоритм поиска к кратчайших путей. Одно из первых решений задачи поиска к кратчайших путей, или ранжирования к кратчайших путей между парой узлов в сети, было предложено Хоффманом и Павли в 1959 г. [3]. Авторы описали алгоритм, в котором для заданного целого числа к ^ 1 последовательно определяются 1-й кратчайший путь, 2-й кратчайший путь и так до fc-ro кратчайшего пути между заданной парой узлов. Существуют два типа задач поиска к кратчайших путей. Первый тип это нахождение путей от источника s до стока t, имеющих наименьшую длину, в которых петли разрешены. Алгоритмы для решения этого типа задач предложены в работах [3, 4, 5]. Второй тип задач поиск к путей от s до t, имеющих наименьшую длину, в которых петли не допускаются [6, 7, 8, 5].

В работе [6] авторы вводят перечисление всех возможных путей из к кратчайших путей в сети. Процедура перечисляет все пути от s до t, а затем выбирает из них к путей с наименьшей длиной. Данный алгоритм имеет два. основных недостатка: во-первых, требуется очень большое количество вычислений и памяти; во-вторых, для решения задачи с малым к требуется столько же усилий, сколько и для решения задачи с большим к, и чем больше к, тем затруднительнее использование этого алгоритма.

В работе [8] автор для поиска k-io кратчайшего пути сначала получает к — 1 кратчайший путь. Затем расстояние каждой дуги в каждом из 1-го, 2-го, ..., (А: —1)-го кратчайших путей поочередно устремляется к бесконечности. Далее задача поиска кратчайшего пути решается для каждого такого случая. Лучший из этих полученных кратчайших путей является искомым k-м кратчайшим путем. Количество вычислений, требуемых для этой процедуры, экспоненциально возрастает с ростом значения к, следовательно, если к не мало, алгоритм Поллака [8] перегружает вычислительные ресурсы.

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

В работе [5] автор описывает следующий алгоритм поиска к кратчайших путей: сначала, с помощью процедуры, аналогичной (но менее эффективной), чем алгоритм Хоффмана и Павли, находятся Н > к кратчайших путей, которые могут содержать петли [3]. Затем Н путей исследуются па к кратчайших путей, не содержащих петель. Эффективность этого алгоритма зависит от конкретной сети. Если Н кратчайших путей, полученных алгоритмом Хоффмана, не содержат петелв, алгоритм Сакаровича [5] может очень быстро определить к кратчайших путей без петель. Однако для этого алгоритма сложно указать верхнюю вычислительную границу.

• 1.1.    Определения. Пусть G = (К £) ориентированный граф с множеством вершин V и множеством ребер Е; п — ^V\ количество вершин; т = \Е\ количество ребер в графе G.

Подграфом в графе G(V,E) называется граф H(Vh,Eh), такой что Vu Е Vh, v Е V и Ve Е Е_н, е Е Е.

Пусть е Е Е. такое что е = (u^v), тогда обозначим head(e) = v начало дуги е и tail(e) = и конец дуги е.

Обозначим wq : Е —> R⁺ функцию веса для ребер графа G.

Пусть u,v Е V, тогда путем из вершины и в вершину v в графе G называется последовательность вершин Р = Р^ = (uq = u,Vi,... ,v_r = и), такая что (щ,^+1) £ Е для V?' : 0 < t < г. Путь Р будем обозначать как и -Е V.

Путь называется простым тогда и только тогда, когда Vi ^ Vj для ^i,j : 0 ^ i < j ^ т.

Для возможности вычисления длины пути расширим функцию Wq на множество всех путей следующим образом: Wg(P) = Д WQ(viVi+i).

i=0        .

Обозначим путь гд —> w_p как (щ,.. . ,v_r. Q) путь, полученный сложением двух путей (щ,..., д.) и Q = (ид,..., Wp), если (щ., ид) € Е.

Пусть существует путь и —> v, тогда длину кратчайшего пути и —> и в графе G обозначим dQ^u,v).

Пусть t Е V, тогда обратным деревом кратчайших путей Т с корнем в t пазовом любой подграф G, для которого выполняются условия: 1) Vu Е Т \ {t} имеет максимум одно исходящее ребро, a t вообще не имеет таких ребер: 2) Vu € Т длина пути Р^ равна ^g(^u0)-, то есть Р^ является кратчайшим путем.

Пусть s,t E V, тогда S множество к попарно неравных кратчайших путей, такое что wg(Pi) Г wa{P2h где Pi Е S и Р₂^ S.

• 1.2.    Описание алгоритма Иена поиска к кратчайших путей. Задача поиска к кратчайших путей заключается в нахождении к путей, имеющих наименьшую длину от начальной до конечной вершины взвешенного графа, при этом каждый путь является простым, то есть не посещает одну и ту же вершину более одного раза [2]. Алгоритм Иона является классическим методом решения задачи в ориентированных графах с неотрицательными весами дуг.

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

База индукции к! = 1. Вычисляется кратчайший путь Pq = До = s, Vi,...,v_r = t) от вершины s до вершины t с помощью алгоритма Дейкстры [9] (Pq существует, иначе решений нет). Второй кратчайший путь является простым кратчайшим ответвлением Рц.

Алгоритм Йена, вычисляет ответвление для каждой вершины Ui пути Pq следующим образом:

• 1)    Для Vi,i = 0, г — 1 создается подграф Gi(PQ графа G путем удаления вершин По, ■ ■ ■ ,fi-i, чтобы избежать ответвления, не являющегося простым, и удалением ребра Дц^-щ), чтобы получить путь, отличающийся ОТ Pq.

• 2)    Для \/i,i = 0, г — 1 вычисляется кратчайший путь Qi от Ui до t и подграфе G^Pq) с. использованием алгоритма. Дейкстры. Если не существует пути, то данное г не рассматривается па шаге 3.

• 3)    Для \/i,i = 0, г — 1 простое ответвление До, ... ,Vi,Qi) пути Pq добавляется в множество кандидатов С. Индекс ответвления г сохраняется явно в паре с ответвлением До,.. . ,Vi, Qi) для последующего использования.

Вторым искомым путем будет самый короткий путь из множества кандидатов С.

Индукционное предположение для 0 < V <  к. Предположим, что множество к' кратчайших путей S вычислено, множество кандидатов С содержит простые пути s —» t, а также существует кратчайший путь Q Е G, такой что S U Q является множеством А/ + 1 кратчайших путей.

Шаг индукции к' —> к' + 1. Пусть Q = До = s,...,v_r = t) и ДО ^ j < г) индекс ответвления. Q удаляется из множества кандидатов С и добавляется в результирующее множество S'. Затем вычисляются все простые ответвления и добавляются в множество кандидатов С'.

• 1)    Для Vj, j ^ i < г создается подграф Gi(Q) графа G путем удаления вершин Vq, . .. ,Vi-i и всех дуг вида Д,ш), таких что множество кандидатов С уже содержит путь с префиксом До,... ,Vi,w).

• 2)    Для Vi, j ^ i < г вычисляется кратчайший путь Qi от Uj до i в Gi(Q). Если не существует пути, то данное i нс рассматривается на шаге 3.

• 3)    Для VJ, j ^ i < г ответвление До,... ^i-Qi) пути Q добавляется в множество кандидатов С с его индексом ответвления i.

Следующим (к' + 2) кратчайшим путем будет кратчайший путь из множества кандидатов.

• 1.3. Оптимизации алгоритма поиска. Оптимизация алгоритма проведена па основе алгоритма, предложенного в работе Али Аль Зуби [10], улучшающего метод поиска к кратчайших путей Даниэля Курца, и Петра Муцеля [11]. Улучшение направлено па уменьшение потребления оперативной памяти.

Основная идея алгоритма, сводится к построению обратных деревьев кратчайших путей. Пусть С_si_mpi_e приоритетная очередь, построенная па основе двоичной кучи. Данная очередь хранит первые к простых путей кандидатов и их длину в виде ((Tq, eQ. Ti,... .Th^eh-T^iYlb}. где Ti обратное дерево кратчайших путей: ei € Е дуга; lb длина пути в графе G. Дерево Th+i может храниться в множестве Та^е, в противном случае оно вычисляется с помощью алгоритма Дейкстры. При этом Vi,i — 0. h Ti гарантированно вычислено и хранится в Т_сас^_е. Чтобы извлечь из данного представления путь, необходимо пройти от вершины s до tailfeo) в обратном дереве кратчайших путей Tq, проследовать по дуге ед в Ti до tail(ei) и так далее до тех пор. пока по будет достигнута вершина t дерева Th+i-

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

В начале работы алгоритма вычисляется обратное дерево кратчайших путей Tq, содержащее кратчайший путь з —У t, если такого пути нет, то пет и решения задачи. Дерево Tq добавляется в C_si_mpi_e. Цикл выполняется до тех пор, пока ие будет найдено к кратчайших путей или ие исчерпаны очереди C_si_mpi_e и Cnot-simpie- В последнем случае результирующее множество S будет содержать меньше к элементов.

В каждой итерации цикла алгоритм сначала выбирает лучший элемент р из двух очередей (с приоритетом для Csimpie- если оценки lb для лучших элементов обеих очередей совпадают). Если р был извлечен из C_Si_mpi_e, то р имеет вид ((То,ец,Т1,... ,Th,eh = (uh,Vh),Th+i),lbf тогда алгоритм действует следующим образом. Если Т^^ не сохранен в Tcache, то он вычисляется и сохраняется. Затем извлекается уже описанным способом простой путь Р из р и добавляется в результирующее множество S. Далее алгоритм обрабатывает все ответвления.

• 1)    Для дуги е = (и,v) Е Е, и Е P^fy ^ {s,... ,Vh, ■ ■ ■ ,и} проверяем, является ли простым путь Р_е, следующий сначала вдоль Р от вершины з до Vh, затем вдоль Р^Ф¹, вдоль ребра е и, наконец, вдоль P^f⁺¹.

• 2)    Если Р_е является простым, то добавляем в C_Si_mpi_e элемент вида ((Tq, во, Ti, . . . , Th, eh, T_h+i,e,T_h+i),lb_e), где lb_e длина пути Р_е.

• 3)    Если ответвление е ие является простым, то оно добавляется в множество X = {fi,... ,f_r}, такое что для всех i,j,l . l^i находится между (или равен) tail(fi) и tail(fi) на пути Р^¹ ■

• 4)    Если множество X ^ 0, то необходимо добавить X как группу кандидатов в С_not—simple ■

Пусть fi = (ui,Vi), тогда обозначим 1\ = lb_fi = w_G(Pi)+w_G(PvfCf) + w_G(fy в этом случае lb = min Ibi, где Pi путь от s до Vh вдоль Р. i^i^r

В случае, если элемент р извлекается из очереди C_not-simpie, то р имеет вид ((Тщво,71, ... .Th,eh,T_h+i,X,T_h+1),lb), e_h = (uh,v'h) ^и A = (s = Xo,...,x_h = E^ префикс пути, представленного элементом р, P^ff¹ = (v'_h,v'_h+l,... ,v'_p — t), и для \/j fj = (v^vf). Зг* : 1 < z* ^ г, такой что lb = Ibi*, алгоритм обрабатывает одновременно несколько ответвлений jr,fr—l,- - ■ ,fi* ■

• 1)    Строится обратное дерево кратчайших путей Т^ в графе G_r — G — {xq, .. . ,Xh = v'_h, ■ ■ ■ ^ц} ^с использованием алгоритма. Дейкстры. В очередь C_si_mpi_e добавляется элемент

вида ((TfpeQ^Ti,... ,T_h,e_h,T_h+1, f_r,Tr)^ где Q_r = Р^Р^Р^ простой путь от s до t. Дерево T' не сохраняется в Tcache- ¹¹⁰ сохраняется «указатель» на него.

• 2)    Для каждого j от г — 1 до Г (по убыванию) строится дерево Т'_г в графе G_r = G — {.r.o,...,Xh = <■/...., г/} па основе Т^₊₁ с использованием алгоритма обновления обратного дерева кратчайших путей [12]. В очередь С simple добавляется элемент вида ((T₀,e_a,T₁,...,T_h,e_h.T_h+l.J_j,T^,w_c(Q_j'}), где Q, = Pi^^.

• 2.    Численные эксперименты.

  • 2.1.    Описание графов. Для тестирования алгоритмов использованы графы, полученные из различных источников [13 15].

Оставшаяся же часть ответвлений ((To,eo,Ti,... ,Th,eh-Th+i,X',Th₊i), min IbA, где l^j

x' = {/1,...,л» 1} возвращается в C_not__simpi_e.

Сложность алгоритма, в худшем случае аналогична сложности базовой версии алгоритма Йена, то есть O(kn(m + п log п)).

NW (USA-road-d/USA-road-t). Дорожная сеть Северо-Запада США. Граф ориентированный, дуги соответствуют направлениям движения, веса расстояниям. Размеры: 1 207 945 вершин и 2 840 208 дуг [13].

FLA (USA-road-d/USA-road-t). Дорожная сеть штата Флорида. Граф аналогичен указанному выше. Размеры: 1 070 376 вершин и 2 712 798 дуг [13].

Rome99. Большой фрагмент городской дорожной сети Рима (Италия). Размеры: 3 353 вершин и 8 870 дуг [13].

• 14    (SNAP). Сеть соавторств в категории Astro Physics па arXiv: неориентированный граф, ребро между авторами означает совместную публикацию. Размеры: 18 772 вершин и 198 110 ребер [14].

• 15    (SNAP). Сеть соавторств в категории Condensed Matter (arXiv), неориентированный граф. Размеры: 23 133 вершин и 93 497 ребер [15].

• 16    (SNAP). Сеть соавторств в категории General Relativity and Quantum Cosmology (arXiv), неориентированный граф. Размеры: 5 242 вершин и 14 496 ребер [16].

• 17    (SNAP). Сеть соавторств в категории High Energy Physics Theory (arXiv), неориентированный граф. Размеры: 9 877 вершин и 25 998 ребер [17].

• 2.2.    Результаты вычислений. Результаты работы алгоритма были протестированы па графах, описанных выше.

В табл. 1, 2 приведены время выполнения и объем памяти, использованной при выполнении алгоритма поиска к кратчайших путей для 1000 произвольных пар вершин при различных значениях к.

В табл. 1 сделан акцент па ускорение по времени, при этом увеличивается объем использованной памяти. В табл. 2 реализован оптимальный алгоритм, в котором была поставлена цель уменьшить затраты памяти, при этом увеличилось время исполнения. Для графов ca-AstroPh и ca-CondMat в табл. 1 получена и оптимизация по памяти.

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

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

Таблица 1

Оптимизация по времени

Г раф	k=2		k=3		k 4		k=5		k= 10
	T, mc	M, Кб	T, mc	M, Кб	T, mc	M, Кб	T, mc	M, Кб	T, mc	M, Кб
NW	148	45227	208	48119	234	49409	314	53414	556	65846
FLA	127	41065	172	43385	227	45095	304	48684	595	60721
Rome99	0,01	1813	0,03	1836	o,i	1857	0,19	1888	0,77	2019
ca-AstroPh	3,6	2683	3,3	2706	3,6	2726	3,5	2750	3,9	2859
ca-CondMat	2,6	2792	2,6	2792	4	2746	4,6	2759	3,6	2799
ca-GrQc	0,002	1821	0,002	1827	0,001	1831	0,003	1810	0,015	1817
ca-HepTh	0,71	2091	0,67	2098	0,69	2113	0,67	2114	0,7	2127

Таблица 2

Оптимизация по памяти

Граф k=2 k 3 k 4 k=5 k 10 T, mc M, Кб T, mc M, Кб T, mc M, Кб T, mc M, Кб T, mc M, Кб NW 253 32690 365 34536 450 35336 591 37058 1225 46079 FLA 281 30406 374 32204 454 33312 693 35842 1148 44361 Rome99 0,08 1596 0,2 1598 0,39 1607 0,64 1615 1,47 1705 ca-AstroPh 8,7 2905 8,4 2897 8,4 2899 8,6 2908 9,2 2932 ca-CondMat 8,7 3004 8,8 3024 8,7 3015 8,9 3020 8,6 3024 ca-GrQc 0,7 1750 0,7 1751 0,7 1748 0,7 1746 0,7 1741 ca-HepTh 2,3 1991 2,4 1994 2,5 2001 2,4 2005 2,4 2009 проходящий через вещество-концентратор. Глобальный путь позволяет идентифицировать последовательные цепочки превращения соединений от начальных реагентов до конечных продуктов всего реакционною процесса. Учитывая основные глобальные пути, через которые проходят наибольшие потоки элемента, можно идентифицировать наиболее важные цепочки превращения, которые должны быть сохранены в скелетном механизме.

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

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

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