Автор работы: Пользователь скрыл имя, 08 Октября 2012 в 23:37, контрольная работа
Рассматриваются неориентированные простые графы (напомним, что простым называется граф, любые две вершины которого соединены не более чем одним ребром). С каждым ребром (x, y) заданного графа G ассоциировано неотрицательное число l(x, y), называемое весом или длиной ребра (содержательно это число может быть расстоянием, стоимостью, пропускной способностью и т.д; здесь используется наиболее распространённый термин «длина»). Удобно считать, что любые две вершины соединены ребром, но для реально отсутствующих рёбер l(x, y) = ¥.
ОБОБЩЁННЫЙ АЛГОРИТМ ДЕЙКСТРЫ
1. Постановка задачи.
Рассматриваются неориентированные простые графы (напомним, что простым называется граф, любые две вершины которого соединены не более чем одним ребром). С каждым ребром (x, y) заданного графа G ассоциировано неотрицательное число l(x, y), называемое весом или длиной ребра (содержательно это число может быть расстоянием, стоимостью, пропускной способностью и т.д; здесь используется наиболее распространённый термин «длина»). Удобно считать, что любые две вершины соединены ребром, но для реально отсутствующих рёбер l(x, y) = ¥.
С каждым путём P в графе G связано неотрицательное
число L(P) (далее называемое длиной
пути P). Для любых
двух вершин графа G минимальным
или кратчайшим путём называется лю-бой соединяющий
их путь P с минимальной
длиной L(P). Подробнее:
путь P, соединяющий
заданные вершины a и b, называется
минимальным или кратчайшим, если для
любого другого пути P', соеди-няющего
те же самые вершины a и b, верно, что L(P) ≤ L(P' ).
Основной задачей, рассматриваемой и решаемой в настоящей работе, является следующая: Для заданной вершины a найти кратчайшие пути, соединяющие a со всеми вершинами графа G. В том случае, когда длина пути считается равной сумме длин всех его рёбер, данная задача была ре-шена около полувека тому назад выдающимся современным математиком Дейкстрой (Dijkstra). В данном материале будет изложена модификация его алгоритма, позволяющая практически при той же конструкции найти минимальные пути для достаточно широкого класса функций длины (выража-ющих зависимость обобщённой длины L(P) от длин входящих в путь P рёбер). Описанию рассмот-ренного класса функций посвящён раздел 2. В 3-ем разделе излагается обобщённый алгоритм Дейкс-тры (ОАД) и доказывается его корректность. В 4-ом разделе проиллюстрировано применение ОАД для классического и минимаксного случая. В 5-м разделе рассмотрены реальные задачи, в которых использование минимаксной функции длины является естественным и целесообразным.
2. Обобщённая длина
Введём необходимые понятия и обозначения. Пусть P – любой путь, соединяющий вершины a и с и пусть вершина b является предпоследней (перед с) вершиной на пути P. Обозначим часть пути P от a до b через P(a, b), а весь путь обозначим через P(a, b, с). Все вершины a, b и с считаются раз-личными. Далее рассматриваются функции длины L(P), для которых выполнены следующие условия.
1. Для путей P, не содержащих рёбер (т.е. состоящих из одной вершины), L(P) = 0.
2. Для каждого пути P, состоящего из единственного ребра (a, b),
L(P) = Φ(l(a, b)),
где Φ(x) - неотрицательная функция от одной неотрицательной переменной.
3. Существует неотрицательная функция F(x, y) от двух неотрицательных переменных, такая, что для всех путей P, содержащих хотя бы два ребра
L(P(a, b, с)) = F(L(P(a, b), l(b, c)).
4. В тех же обозначениях
L(P(a, b)) ≤ L(P(a, b, с)).
5. Функции Φ(x) и F(x, y) являются неубывающими по всем переменным.
6. Φ(∞) = ∞, F(∞,y) = F(x,∞) = F(∞,∞ ) = ∞.
Условие 1 является совершенно естественным. Условие 2 выражает длину пути, состоящего из одного ребра, через длину самого ребра. Условие 3 означает, что длина пути P(a, b, с) однозначно выражается через длину этого же пути P(a, b) без последнего ребра, и длины последнего ребра l(b, c). Условие 4 выражает естественное требование: длина части пути не может превосходить длину всего пути. Условие 5 выражает естественное требование к зависимости длины пути от длин его частей: при увеличении длины части длина всего пути не может уменьшиться. Условие 6 также является естественным, если считать, что любые две вершины соединены ребром, но при отсутствии реального ребра считать длины таких фиктивных рёбер равными ∞.
Условия 1 – 6 играют центральную роль в дальнейших конструкциях. Остановимся на этом подробнее, для чего рассмотрим некоторые примеры функций длины L(P).
1. Длина пути равна сумме длин всех его рёбер («классический» случай). В этом случае F(x, y)= x + y, Φ(x) = x и выполнение условий 1 – 6 очевидно.
2. Длина пути равна
максимальной длине ребра
3. Длина пути L(P) определяется формулой
L(P) = f(Σl(x, y)),
где сумма берётся по всем рёбрам, входящим в путь P, и f – строго возрастающая функция одной неотрицательной переменной. Покажем, что в этом случае функция F(x,y), удовлетворяющая (1), (2), (3) и (4), существует. Действительно, можно положить
F(x, y) = f (f –1(x) + y), Φ(x) = f(x).
Формулы (1), (2), (3) и (4) прямо следует из (5) и (6).
Заметим, что длина пути L(P), равная корню квадратному из суммы длин всех его рёбер, как и длина пути L(P), равная квадрату суммы длин всех его рёбер, укладываются в рассматриваемый случай.
4. Длина пути равна среднему арифметическому длин всех рёбер, входящих в путь. В этом слу-чае
L(P(a, b, с)) = L(P(a, b))• + l(b, c)• ,
где n – число рёбер в пути P(a, b, с). Это значит, что представления (2) в рассматриваемом случае не существует, поскольку в формулу (7) в явном виде входит зависимость от n.
Назовём функцию длины L(P), для которой выполнены условия 1 – 5, длиной Дейкстры или Дейкстровой длиной. В трёх первых случаях длина была Дейкстровой, а в 4-м случае – нет.
Имеют место
Утверждение 1. Пусть P(a, b, с) – некоторый путь, P(a, b) – его начальный участок, P0(a, b) – другой путь из a в b, такой что L(P0(a, b)) ≤ L(P(a, b)). Тогда
L(P0(a, b, с)) ≤ L(P(a, b, с)).
Доказательство непосредственно следует из представления (2) и условия 5 ■
Утверждение 2. Пусть P – любой путь, соединяющий вершины a и с и пусть вершина b являет-ся любой промежуточной вершиной на пути P. Тогда
L(P(a, b)) ≤ L(P(a, b, с)).
Доказательство. Разница между формулами (9) и (3) состоит в том, что в (3) промежуточная вершина b является предпоследней, а в (9) – любой. Доказательство получается последовательным применением (3), начиная с предпоследнего места и кончая заданной позицией. Подробнее: зануме-руем все вершины на пути P: x0, x1, …, xk, …, xn–1, xn. В силу (3) имеем
L(P(x0, xn–1)) ≤ L(P(x0, xn–1, xn)).
Далее, аналогично
L(P(x0, xn–2)) ≤ L(P(x0, xn–2, xn–1)),
……………………………………
L(P(x0, xk)) ≤ L(P(x0, xk, xk+1)),
откуда и следует требуемое равенство:
L(P(x0, xk)) ≤ L(P(x0, xk, xn)) ■
3. Обобщённый алгоритм Дейкстры
Предлагаемый алгоритм основан на продолжении путей через последнюю вершину, для кото-рой уже точно известны и минимальный путь, и его длина. Он практически совпадает с классическим алгоритмом Дейкстры, отличаясь только деталями.
Идея алгоритма построения дерева минимальных путей и определения их длин, предложенного в 1959г. Е. Дейкстрой, такова. На каждом этапе одна новая вершина включается в множество S отме-ченных вершин, для которых минимальные пути найдены. Обозначим эту только что включённую в множество S вершину через w. Тогда на следующем этапе к множеству S добавляется вершина v с са-мым коротким путем из а, проходящим по множеству S, предпоследней вершиной на котором явля-ется w.
В работе предлагается алгоритм именно такой структуры. Отличие его от классического состо-ит в возможности находить кратчайшие пути при описанной выше функции длины (зависимости длины пути от длин входящих в него рёбер) достаточно общего вида (см раздел 2). При изложении алгоритма, как и при доказательстве его корректности, использовались книги [1, 2].
Введём необходимые понятия и обозначения. Пусть G = áV, Eñ – неориентированный граф с множеством вершин V и множеством рёбер E. Понятия длины ребра и пути были введены в разделе 1. Ищутся минимальные пути из фиксированной вершины а во все остальные вершины. Если для каждой вершины vÎV, достижимой из а, зафиксировать один кратчайший путь из а в v, то получив-шийся граф будет представлять ориентированное дерево с корнем а. Это дерево называется деревом минимальных путей из а.
Предполагается, что задан неориентированный граф G = áV, Eñ, содержащий n вершин. Без ог-раничения общности можно считать, что все вершины задаются номерами от 0 до n–1 и что началь-ная вершина имеет номер 0. Длина ребра между вершинами i и j обозначена через l(i, j); если нет реб-ра, соединяющего эти вершины, то l(i, j) = ¥. Предполагается, что заданы функция Φ(x) одной пере-менной, функция F(x, y) двух переменных и функция длины L, удовлетворяющие условиям 1 – 6.
Обобщённый алгоритм Дейкстры (ОАД). Алгоритм находит кратчайшие пути из начальной вершины 0 во все остальные вершины графа. Для реализации алгоритма вводятся пять одномерных массивов:
1) Массив P вершин, уже получивших постоянные метки (для этих вершин кратчайшие пути из начальной вершины уже известны, а постоянная метка – это длина кратчайшего пути из начальной вершины в данную вершину). Длина массива P равна n.
2) Массив M постоянных меток (на i-ом месте стоит длина кратчайшего пути из начальной вершины в вершину P[i]). Длина массива M равна n.
3) Массив T вершин, ещё не получивших постоянных меток. Длина массива T равна n–1.
4) Массив W временных меток (на i-ом месте стоит длина текущего пути из вершины 0 в вер-шину T[i]). Длина массива W равна n–1.
5) Массив PR номеров вершин, непосредственно предшествующих вершинам 0, 1, …, n–1 в текущих путях (после завершения работы алгоритма все пути будут кратчайшими) из вершины 0. В массиве PR на i-ом месте стоит вершина PR[i], непосредственно предшествующая вершине i. Длина массива PR равна n.
В процессе работы алгоритма происходит заполнение всех массивов. Позиции в массивах, значения которых в данный текущий момент могут быть произвольными, заполняются знаком •.
Инициализация. Положим
P[0] = 0 (в массиве вершин, получивших постоянные метки, на 0-м месте стоит начальная вершина 0);
M[0] = 0 (длина кратчайшего пути от вершины 0 до самой себя равна 0);
T[i] = i+1, i = 0, 1, …, n–2 (все вершины, кроме начальной, образуют массив T);
W[i] = ¥, i = 1, …, n–1 (временные метки всех вершин, кроме начальной, инициализируют-
ся бесконечностью);
PR[0] = −1 (у начальной вершины 0 нет предшествующей).
В результате инициализации массив P включает (на нулевом месте) одну вершину 0, для которой минимальный путь из неё же самой в неё же саму является пустым (не содержит рёбер), а его длина равна 0 в соответствие с условием 1 из раздела 2. Временные метки (т.е. текущие длины путей) равны ¥ для всех остальных вершин, в том числе и тех, которые соединены ребром с вершиной 0.
На шагах 1, 2, … , n ровно для одной вершины определяется путь минимальной длины. Суть операций на каждом шаге – модификации пяти указанных массивов (массив PR, вообще говоря, на некоторых шагах может не изменяться).
Шаг 1
1. Для i = 0, 1, …, n–1 выполняются следующие действия:
1.1. W’[i] = Φ(l(0,T[i])
(именно здесь и только здесь используется функция Φ длины пути, состоящего из одного ребра, соединяющего вершину 0 с вершиной T[i]);
1.2. Если W’[i] < ¥, то W[i] = W’[i] и PR[T[i]] = 0 (в том случае, когда ребро из начальной вершины 0 в вершину T[i] реально присутствует, временная метка вершины T[i] становится равной длине пути, состоящего из одного этого ребра, а предшествующей вершиной – на-чальная вершина 0).
2. Выбираем в массиве W временных меток минимальную (если их несколько, то можно взять любую из них). Обозначим номер выбранного минимума в массиве W через im, а его значение – через vm.
3. Положим VC = T[im]. Таким образом, VC – это вершина с минимальной временной меткой, равной vm.
4. Положим P[1] = VC, M[1] = vm. Таким образом, число вершин, имеющих постоянную метку, стало равным 2. Сама эта вершина занесена в массив P, а её постоянная метка – в массив M на 1-ую позицию (следующую за 0-ой).
5. Удалим из массивов T и W элементы с номером im (сдвинув все элементы с бóльшими индек-
сами на одну позицию влево). Таким образом, число вершин, имеющих временную метку, стало меньше на единицу.
Шаг k (k > 1).
1. Для i = 0, 1, …, n–k–1 выполняются следующие действия:
1.1. W’[i] = F(M[k–1], l(P[k–1],T[i])