Обобщенный алгоритм Дейкстры

W = á•,•,•,•,•ñ;

PR = á–1,0,0,1,1,4ñ.

Массив PR содержит всю информацию о кратчайших путях, а массив M – об их длинах. В соответст-вии с пунктом «Построение кратчайших путей» для вершины 5 получаем предшествующие верши-ны: 5→4→1→0 или 0→1→4→5; для вершины 4: 0→1→4; для вершины 3: 0→1→3; для вершины 2: 0→2; для вершины 1: 0→1.

4.2. Алгоритм Дейкстры в задаче на минимакс. В этом случае минимизируется обобщённая длина пути, равная максимальной длине ребра, входящего в данный путь. Формулы пересчёта меток (10а) и (10b) принимают вид

W’[i] = l(0,T[i]),  W’[i] = max{M[k–1, l(P[k–1],T[i]). 

Проиллюстрируем ОАД также на примере показанного на рис. 1 графа. В данном графе число вершин n = 6. При указанной на рисунке нумерации вершин после выполнения инициализации име-ем:

P = á0,•,•,•,•,•ñ;

M = á0,•,•,•,•,•ñ;

T = á1,2,3,4,5ñ;

W = á¥,¥,¥,¥,¥ñ;

PR = á–1,•,•,•,•,•ñ.

Для 1-го шага (k = 1) формула (10а) принимает вид W’[i] = l(0,T[i]), откуда

W[0] = min{¥, l(0,1)}} = min{¥, 1} = 1;

W[1] = min{¥, l(0,2)}} = min{¥, 5} = 1;

W[0] = min{¥, l(0,3)}} = min{¥, ¥} = ¥;

W[0] = min{¥, l(0,4)}} = min{¥, ¥} = ¥;

W[0] = min{¥, l(0,5)}} = min{¥, ¥} = ¥.

Заметим, что новая метка  стала меньше старой при i = 0, i = 1. Поэтому в соответствии с пунктом 1.2 1-го шага алгоритма получаем

PR[T[0]] = PR[1] = P[0] = 0;

PR[T[1]] = PR[2] = P[0] = 0.

Далее, минимальным значением  в новом массиве W = á1,5,¥,¥,¥ñ является число 1, стоящее на 0-м месте, т.е. im = 0, vm = 1. В соответствии с пунктом 3, VC = T[im] = T[0] = 1. В соответствии с пунктом 4 получаем P = á0,1,•,•,•,•ñ, M = á0,1,• ,•,•,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á2,3,4,5,•ñ, W = á5,¥,¥,¥,•ñ. Таким образом, после выполнения 1-го шага получаем следующие 5 массивов:

P = á0,1,•,•,•,•ñ;

M = á0,1,•,•,•,•ñ;

T = á2,3,4,5,•ñ;

W = á5,¥,¥,¥,•ñ;

PR = á–1,0,0,•,•,•ñ.

Для 2-го шага (k = 2) формула (10b) принимает вид W’[i] = max{M[1], l(P[1], T[i])}, откуда

W[0] = min{5, max{1, l(1,2)}} = min{5, max{1,8}} = 5;

W[1] = min{¥, max{1, l(1,3)}} = min{¥, max{1,10}} = 10;

W[2] = min{¥, max{1, l(1,4)}} = min{¥, max{1,6}} = 6;

W[3] = min{¥, max{1, l(1,5)}} = min{¥, max{1,¥}} = ¥;

Заметим, что новая метка  стала меньше старой при i = 1, i = 2. Поэтому в соответствии с пунктом 1.2 k-го шага алгоритма при k = 2 получаем

PR[T[1]] = PR[3] = P[1] = 1;

PR[T[2]] = PR[4] = P[1] = 1.

Далее, минимальным значением  в новом массиве W = á5,10,6,¥,•ñ является число 5, стоящее на 0-м месте, т.е. im = 0, vm = 5. В соответствии с пунктом 3, VC = T[im] = T[0] = 2. В соответствии с пунктом 4 получаем P = á0,1,2,•,•,•ñ, M = á0,1,5,•,•,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á3,4,5,•,•ñ, W = á10,6,¥,•,•ñ. Таким образом, после выполнения 2-го шага получаем следующие 5 массивов:

P = á0,1,2,•,•,•ñ;

M = á0,1,5,•,•,•ñ;

T = á3,4,5,•,•ñ;

W = á10,6,¥,•,•ñ;

PR = á–1,0,0,1,1,•ñ.

Для 3-его шага (k = 3) формула (10b) принимает вид W’[i] = max{M[2], l(P[2], T[i])}, откуда

W[0] = min{10, max{5, l(2,3)}} = min{10, max{5,¥}} = 10;

W[1] = min{6, max{5, l(2,4)}} = min{6, max{5,7}} = 6;

W[2] = min{¥, max{5, l(2,5)}} = min{¥, max{1,¥}} = ¥;

Заметим, что новая метка  не стала меньше старой ни при каком i. Поэтому в соответствии с пунктом 1.2 k-го шага алгоритма массив PR не изменяется.

Далее, минимальным значением  в новом массиве W = á10,6,¥,•,•ñ является число 6, стоящее на 1-м месте, т.е. im = 1, vm = 6. В соответствии с пунктом 3, VC = T[im] = T[1] = 4. В соответствии с пунктом 4 получаем P = á0,1,2,4,•,•ñ, M = á0,1,5,6,•,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á3,5,•,•,•ñ, W = á10,¥,•,•,•ñ. Таким образом, после выполнения 3-его шага получаем следующие 5 массивов:

P = á0,1,2,4,•,•ñ;

M = á0,1,5,6,•,•ñ;

T = á3,5,•,•,•ñ;

W = á10,¥,•,•,•ñ;

PR = á–1,0,0,1,1,•ñ.

Для 4-го шага (k = 4) формула (10b) принимает вид W’[i] = max{M[3], l(P[3],T[i])}, откуда

W[0] = min{10, max{6, l(4,3)}} = min{10, max{6,5}} = 6;

W[1] = min{¥, max{6, l(4,5)}} = min{¥, max{6,4}} = 6;

Заметим, что новая метка  стала меньше старой при i = 0, i = 1. Поэтому в соответствии с пунктом 1.2 k-го шага алгоритма при k = 4 получаем

PR[T[0]] = PR[3] = P[3] = 4;

PR[T[1]] = PR[5] = P[3] = 4.

Далее, минимальным значением  в новом массиве W = á6,6,•,•,•ñ является число 6. Выберем 6, стоящее на 0-м месте, т.е. im = 0, vm = 6. В соответствии с пунктом 3, VC = T[im] = T[0] = 3. В соответствии с пунктом 4 получаем P = á0,1,2,4,3,•ñ, M = á0,1,5,6,6,•ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á5,•,•,•,•ñ, W = á6,•,•,•,•ñ. Таким образом, после выполнения 4-го шага получаем следующие 5 массивов:

P = á0,1,2,4,3,•ñ;

M = á0,1,5,6,6,•ñ;

T = á5,•,•,•,•ñ;

W = á6,•,•,•,•ñ;

PR = á–1,0,0,4,1,4ñ.

Для 5-го шага (k = 5) формула (1) принимает вид W’[i] = max{M[4], l(P[4],T[i])}, откуда

W[0] = min{6, max{6, l(3,5)}} = min{6, max{6,1}} = 6;

Новая метка не стала меньше старой при i = 0. Поэтому в соответствии с пунктом 1.2 k-го шага алго-ритма массив PR не меняется. Далее, минимальным значением в новом массиве W = á6,•,•,•,•ñ являет-ся число 6. Имеем im = 0, vm = 6. В соответствии с пунктом 3, VC = T[im] = T[0] = 5. В соответствии с пунктом 4 получаем P = á0,1,2,4,3,5ñ, M = á0,1,5,6,6,6ñ; наконец, изменяя в соответствии с пунктом 5 массивы T и W, получаем T = á•,•,•,•,•ñ, W = á•,•,•,•,•ñ. Таким образом, после выполнения 5-го шага получаем следующие 5 массивов:

P = á0,1,2,4,3,5ñ;

M = á0,1,5,6,6,6ñ;

T = á•,•,•,•,•ñ;

W = á•,•,•,•,•ñ;

PR = á–1,0,0,4,1,4ñ.

Массив PR содержит всю информацию о кратчайших путях, а массив M – об их длинах. В соответ-ствии с пунктом «Построение кратчайших путей» для вершины 5 получаем предшествующие вер-шины: 5→4→1→0 или 0→1→4→5; для вершины 4: 0→1→4; для вершины 3: 0→1→4→3; для вер-шины 2: 0→2; для вершины 1: 0→1.

В предыдущем пункте 4.1 для классического случая получили: для вершины 5: 0→1→4→5; для вершины 4: 0→1→4; для вершины 3: 0→1→3; для вершины 2: 0→2; для вершины 1: 0→1. Сравнивая с ответом в минимаксном случае, видим отличие для пути в вершину 3: 0→1→3 в случае суммы и 0→1→4→3 в случае минимакса. Для более сложных графов отличия могут быть значительными.

 

5. Применения минимаксной длины

В разделе 2 приведены примеры  Дейкстровой функции длины. Одной из них является минимак-сная функция, когда за длину пути принимается максимальная длина среди всех рёбер данного пути:

L(P) = max{l(a,b)},                                                                                                                                        (22)

где минимум берётся по всем рёбрам (a,b), образующим путь P.

 В силу основной  теоремы 1, для нахождения минимального пути при указанной функции мож-но использовать ОАД, вычислительная эффективность которого столь же высока, как и у класси-ческого алгоритма Дейкстры. Это важно, поскольку различные задачи оптимизации могут быть ес-тественно представлены как задача нахождения минимального пути, длина которого определяется формулой (22). Ниже рассматриваются два реальных примера таких задач.

5.1. Частотная дихотомия графов. Одной из достаточно известных задач является задача де-композиции графа (т.е. его разделения на несколько подграфов, по возможности слабо связанных друг с другом). Оригинальный подход к решению этой задачи (в контексте анализа структуры соци-альных сетей) был предложен в работах [3, 4]. Суть дела может быть кратко изложена следующим образом.

Положим начальную частоту  во всех рёбрах данного неориентированного графа G равной 0. Пусть для случайной пары вершин (a,b) графа G построен некоторый соединяющий их путь. Приба-вим по 1 к частотам всех рёбер, вошедших в построенный путь. Выберем другую случайную пару вершин и таким же образом изменим частоты рёбер. Повторим данную операцию достаточно много раз. Тогда частоты в рёбрах, входящих в «узкий» разрез, окажутся достаточно велики (по крайней мере, в одном из таких рёбер). Удалим ребро с максимальной частотой из графа, положим все часто-ты опять равными 0, и будем повторять эту процедуру до тех пор, пока граф не станет несвязным. Последовательно удаляемые рёбра содержат искомый разрез. А последовательное применение про-цесса к найденным подграфам позволяет выявить групповую структуру сети, представленной дан-ным графом.

В работе [5] была предложена более эффективная версия этого (названного частотным) подхо-да. Очевидный недостаток алгоритма Ньюмана и Жирвана (указанный уже его авторами), состоит в том, что после удаления одного ребра с максимальной частотой вся накопленная ранее статистика по частотам рёбер никак не используется в дальнейшем. Если бы эту информацию удалось сохранить для последующих шагов, это могло бы значительно ускорить алгоритм.

Заметим, что в ранее  предлагавшихся частотных алгоритмах пути, соединяющие очередную па-ру вершин, проводятся независимо от предыдущих путей. Однако учёт всех ранее проведённых путей позволяет получать разрезы между двумя группами вершин, в которых все рёбра имеют одина-ковую максимальную частоту. Тогда одновременное и однократное удаление всех рёбер с макси-мальной частотой определяет искомую дихотомию графа.

Новый частотный алгоритм подробно изложен и проанализирован в [5]. Здесь даётся описание только одной итерации. Именно, пусть некоторое количество путей уже проведено и в рёбрах уже накоплены некоторые частоты. Пусть выбрана очередная пара вершин (p, q). Будем считать длиной каждого ребра текущее (накопленное к данной итерации) значение частоты. Путь, соединяющий вершины p и q, будем искать как минимаксный путь, т.е. как кратчайший путь, в котором длина пути равна максимальной длине ребра (в данном случае – накопленной частоте). Такой способ будет «зас-тавлять» очередные пути избегать рёбер с большими значениями частоты и проходить между ними. Доказывается, что он приводит к построению равномерного разреза, т.е. разреза, в котором все рёбра имеют одинаковую максимальную частоту. Это, в свою очередь, даёт возможность получения интуи-тивно правильных классификаций в случаях, с которыми не справлялись другие методы классифика-ции (см. подробности в работе [5]).

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

Задан граф G телекоммуникационной сети. С каждым ребром e графа G связана пропускная способность c(e) соответствующего кабеля, измеряемая в Мбит/сек. Типовые значения – 2, 8, 34, 55, 134, … (так называемая цифровая иерархия).

Задаётся множество F троек áu, v, φñ, где u и v – вершины графа G (обычно соответствуют узлам сети), φ = φ(u, v) – чётное натуральное число, равное величине трафика между соответствующими уз-лами (в Мбит/сек). При этом в разных тройках áu, v, φñ множества вершин {u, v} являются разными. Поток в сети определяется следующим образом. Для каждой тройки áu, v, φñÎF задаётся φ ⁄ 2 путей, соединяющих вершины u и v (пути, вообще говоря, могут совпадать). По каждому пути передаётся две единицы трафика. Реально это означает, что установлено соединение между вершинами u и v , в котором поддерживается передача информации с минимальной частотой 2 Мбит/сек (нижний уро-вень цифровой иерархии). Обозначим суммарный поток в ребре e (т.е. удвоенное общее число путей, соединяющих любые пары вершин из заданных троек множества F и при этом содержащих ребро e) через φ(e). При этом требуется, чтобы суммарный поток не превышал пропускной способности во всех рёбрах графа:

φ(e) ≤ c(e).                                                                                                                                                    (23)

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

 → min                                                                                                                                           (24)

Суть дела в том, что  такой критерий выражает требование к устойчивости работы сети при одновре-менном росте трафика для всех пар её узлов(см. подробности в [6]).

Для решения данной задачи дискретной оптимизации в реальных сетях, содержащих десятки или сотни узлов, могут быть использованы различные эвристические методы. Один из них состоит в последовательной маршрутизации для отдельных путей при оптимизации на каждом шаге критерия (24). Идея состоит в следующем. Пусть уже проведено несколько путей. Поэтому для каждого ребра известен текущий поток φ(e). Тогда число

 ,                                                                                                                                                           (25)

равное новой нагрузке в ребре e, если бы новый путь прошёл через это ребро, также известно. Опти-мизация критерия (24) на данном шаге означает проведение нового пути таким образом, чтобы мак-симальное значение (25) было бы как можно меньше. Но последняя задача как раз совпадает с зада-чей нахождения кратчайшего пути при минимаксной функции длины, когда длина каждого ребра оп-ределяется выражением (25). Решив эту вычислительно простую задачу для каждого из ещё не прове-дённых путей, выберем для добавления на данном шаге именно тот путь, который в наименьшей сте-пени увеличивает критерий (24). На первом шаге процедуры используется длина (ни один путь ещё не проведён). Экспериментальные исследования показали хорошее качество получаемых реше-ний.

 

Заключение

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

 

Литература

1. Дехтярь М.И. Лекции по дискретной математике. – БИНОМ, М.: 2009. 260 с.

2. Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов. – М.: Мир, 1981. 368 с.

3. Newman, M.E.J., Girvan, M. Community structure in social and biological networks. – Proc. Natl. Acad. Sci. USA 99, 7821–7826, 2002.

4. Newman, M.E.J. Detecting community structure in networks. – Eur. Phys. J. B 38, 321–330, 2004.

5. Rubchinsky А. A Divisive-Agglomerative Classification Algorithm Based on the Minimax Modification of Frequency Approach: Working paper WP7/2010/07. – Moscow: University – Higher School of Econo-mics, 2010. 48 p.

6. Method for cost effective ring allocation in telecommunication networks – Patent Number 125683 in Isra-el. Inventors: Lev Bregman, Yuri Kazarinov, Boris Model, Alexander Rubchinsky, and Alexander Virtzer.