Главная / Информатика / Обоснование алгоритма волны

Обоснование алгоритма волны

По индукции легко устанавливается, что на каждом шагу работы алгоритма метка l(X), которой снабжена какая-либо вершина X, указывает на то, что имеется путь веса l(X) из вершины A В вершину B. Присвоение новой метки l(X) означает, что найден не обнаруженный ранее путь из A в X минимального на данный момент веса. При этом все пути, о которых идёт речь, являются элементарными, т. е. не содержат циклов, так как присоединение цикла к пути не уменьшает его веса. Так как число элементарных путей в орграфе конечно, то алгоритм обязательно закончит свою работу.

Те вершины, которые не будут снабжены метками после окончания работы алгоритма, недостижимы из вершины A. Действительно, допустим, что C — такая вершина и предположим, что существует путь (X0, X1,…, Xk1, Xk), где X0=A, Xk=C. Пусть Xi — последняя из вершин этого пути, снабжённых меткой. Тогда мы получаем противоречие с тем, что алгоритм уже закончил свою работу и не может больше присвоить метки ни одной вершине, так как дуга (Xi, Xi+1) годится для присвоения метки вершине Xi+1.

Что касается вершин, снабжённых метками, то каждая метка даёт минимальный из весов путей, соединяющих A С соответствующей вершиной. Действительно, предположим, что после окончания работы алгоритма для некоторой вершины C Имеется путь L=(X0, X1,…, Xk1, Xk), где X0=A, Xk=C, с весом W(L)< l(C). Обозначим через Li Начальную часть этого пути, заканчивающуюся в вершине Xi : Li =(X0, X1,…, Xi1, Xi). Пусть Xj — последняя из вершин Xi, для которых W(Li) =l(Xi). Тогда

W(Lj+1)= l(Xj)+ W((Xj, Xj+1))< l(Xj+1),

А это противоречит тому, что алгоритм уже закончил свою работу, так как не может больше сделать ни одного присвоения метки.

Замечания. 1. Если не требовать неотрицательности весов дуг, то может оказаться, что поставленная задача не имеет решения; при этом приведенный выше алгоритм никогда не прекратит свою работу. Поясним ситуацию на простейшем примере. Пусть граф G имеет всего две вершины A и B и две дуги: дугу (A, B) веса 1 и дугу (B, A) веса -2. Тогда цикл Z=(B, A, B) имеет Отрицательный вес, равный -1. Путь L=(A, B) имеет вес 1. Добавление к этому пути цикла Z даёт путь L+Z=(A, B, A, B) веса 1-2=-1, Меньшего, чем вес пути L. Повторяя эту процедуру N Раз, получим путь L+Nz веса -(2N-1)®-¥ при N®¥. Значит, в данном случае пути из A в B минимального веса не существует.

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

2. Для эффективного выполнения шага 5° можно при присвоении вершине Y Метки l(Y)=l(Y)+W((X, Y)) присвоить ей дополнительную метку w(Y)=X. Тогда вершины искомого пути L находятся по очереди, начиная с последней, из условия Xi-1=w(Xi), I=T, T-1,…, 1.

3. Для Неориентированного графа G Задача о пути минимального веса тоже имеет смысл и решается с помощью того же алгоритма, если неориентированный граф понимать как симметричный ориентированный граф. При этом веса дуг веса дуг удовлетворяют условию Симметричности: w(X, Y)=w(Y, X).

Пример. На рис. 10 изображён граф G; число, написанное около каждой дуги означает её вес. Мы видим, что представлять информацию о графе и весах его дуг в таком виде неудобно, особенно — если число вершин и дуг велико и предполагается использование компьютера для обработки этой информации (например, для решения задачи о пути минимального веса). Двумерный числовой массив — гораздо более удобный формат для этих целей. Этот массив называется матрицей весов. Уточним: матрицей весов ориентированного графа, дуги которого снабжены весами, называется матрица, строки и столбцы которой озаглавлены вершинами данного графа, а на пересечении строки X и столбца Y Стоит вес дуги (X, Y); если же дуга (X, Y) отсутствует в графе, то на это место можно поместить любой символ, который не воспринимается как вес дуги, например, — пробел. Подчеркнём, что матрица весов, кроме информации о весах дуг содержит Полную информацию о самом графе.

Матрица весов для рассматриваемого примера имеет вид:

X0

X1

X2

X3

X4

X5

X6

X7

X8

X9

X0

1

10

6

3

X1

1

10

10

X2

10

1

2

5

X3

10

10

1

4

4

1

X4

2

4

5

2

X5

6

4

3

2

X6

1

5

3

5

3

8

X7

3

2

5

8

X8

3

8

5

X9

5

2

8

5

Пусть начальной вершиной всех рассматриваемых путей является X0. Продемонстрируем начало работы алгоритма волны.

1) По матрице весов мы видим, что W((X0, X1))=1. Присваиваем вершине X1 метки l=1, w=X0. Аналогично, присваиваем вершине X3 метки l=10, w=X0, вершине X5 — метки l=6, w=X0 и вершине X7 — метки l=3, w=X0.

2) Пользуясь строкой X1 матрицы весов и учитывая метку l(X1)=1, присваиваем вершине X2 метки l=1+10=11, w=X1.

3) Пользуясь строкой X3 матрицы весов и учитывая метку l(X3)=10, присваиваем вершине X4 метки l=10+4=14, w=X3, а вершине X6 — метки l=10+1=11, w=X3.

4) Пользуясь строкой X5 матрицы весов и учитывая метку l(X5)=6, производим Переприсвоение меток для вершины X6; Новые метки в вершине X6: l=6+3=9, w=X5.

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

X1

X2

X3

X4

X5

X6

X7

X8

X9

1/0

10/0

6/0

3/0

11/1

14/3

11/3

9/5

5/7

8/7

11/7

13/2

16/2

9/5

15/4

10/3

12/2

14/4

Отсюда следует, что путь минимального веса, соединяющий вершины X0 и , имеет длину 14. С помощью меток w находим путь L Веса 14. В него входят дуги (X4, X9), (X2, X4), (X3, X2), (X5, X3), (X7, X5), (X0, X7): L=(X0, X7, X5, X3, X2, X4, X9). Отметим, что С помощью той же таблицы Можно найти пути минимального веса для любой конечной вершины.

3. Оптимизация путей для весов из упорядоченной полугруппы. Здесь мы обобщим задачу, рассмотренную в предыдущем пункте и алгоритм её решения. Во многих случаях вес пути составляется из весов дуг не с помощью сложения, а с помощью какой-нибудь другой операции, например,— умножения, а сравнение весов путей осуществляется не с помощью отношения £, а с помощью другого порядка (например,— ³). Кроме того, веса вообще могут быть не элементами не вещественной прямой R, а какого-либо другого множества. Эта ситуация охватывается понятием упорядоченной полугруппы.

Определение 3.16. Упорядоченной полугруппой называется алгебраическая система A=(A, *, ´), Где * — Ассоциативная бинарная операция на A, a ´ — Отношение порядка на A, Удовлетворяющее следующему Условию согласования с операцией *:

("CÎA) ((A´B) Þ ((C*A´C*B) & (A*C´B*C))).

Пусть каждой дуге U орграфа сопоставлен элемент W(UA упорядоченной полугруппы (A, *, ´). Этот элемент будем называть весом дуги. Весом пути L=(X0, X1,…, Xn-1, Xn) назовем Элемент W(L)=W((X0, X1))*W((X1, X2))*…*W((Xn-1, Xn)).

Задача об A-оптимальном пути: Найти в графе G такой путь, соединяющий вершину а с вершиной B, вес которого является минимальным (в смысле порядка в A) элементом множества весов всех путей из а в B.

Задача, рассмотренная в предыдущем пункте, является частным случаем только что сформулированной задачи, когда A=R+, операция * является сложением вещественных чисел и отношение ´ есть обычный порядок £ на множестве неотрицательных чисел. Типичные интерпретации задачи в этом случае: задача о кратчайшем пути, задача о быстрейшем пути, задача о самом дешёвом пути и т. п.

Практически важной является задача о пути Максимальной пропускной способности. Пропускная способность пути есть минимальная пропускная способность дуг этого пути, а отношение порядка нужно выбрать так, чтобы «лучше» означало «больше». В соответствии с этим для формализации задачи о пути максимальной пропускной способности как задачи об A-оптимальном пути упорядоченная полугруппа A=(A, *, ´) должна быть выбрана следующим образом:

A=R+, A*B=min(A, B), (A´B)Û(A³B).

Приведём пример задачи, для которой элементы упорядоченной полугруппы не являются числами. Предположим, что каждая дуга U обладает двумя характеристиками: пропускной способностью W1(U)ÎR+ и ценой W2(U)ÎR+. Мы хотели бы выбрать путь с наивысшей пропускной способностью и наименьшей ценой. Это ситуация типична для так называемых задач Многокритериальной оптимизации. Весами дуг и весами путей в данном случае являются пары чисел W=(W1, W2)Î(R+)2. Полугрупповую операцию *, очевидно, нужно определить следующим образом:

(A1, A2)*(B1, B2)=(min(A1, B1), A2+B2).

(3.1)

А вот ответ на вопрос о том, как упорядочить (R+)2 совсем не так ясен и зависит от уточнения постановки задачи. Действительно, требования максимальности пропускной способности и минимальности цены могут противоречить друг другу (это только в рекламе могут обещать и то, и другое одновременно). Нужно находить какой-то компромисс, и выбор отношения порядка как раз и определяет конкретный компромисс. Например, пусть для нас цена настолько важнее пропускной способности, что из двух путей Разной Цены мы готовы выбрать тот, у которого цена ниже, не взирая на пропускную способность. Такому намерению отвечает следующее отношение порядка ´ на (R+)2:

(A1, A2)´(B1, B2)

Û

(A2<B2)Ú((A2=B2)&(AB1).

(3.2)

Итак, задача о пути наименьшей цены и наименьшей — при равных ценах — пропускной способности формализуется как задача об A-оптимальном пути, если A=((R+)2, *, ´), где операция * и отношение порядка ´ определены формулами (3.1) и (3.2).

Алгоритм волны, решающий общую задачу об оптимальном пути буквально совпадает с алгоритмом волны из предыдущего пункта, если всюду + заменить на *, а < заменить на p, где p — строгий порядок, отвечающий нестрогому порядку ´.

Условие поглощения для задачи об A-оптимальном пути формулируется следующим образом: Для любого цикла Z в рассматриваемом графе и любого элемента AÎA выполняется соотношение A´A*W(Z). Для двух последних примеров упорядоченной полугруппы условие поглощения выполнено автоматически.

Примеры решения задачи об A-оптимальном пути с помощью алгоритма волны.

1. Рассмотрим снова граф, изображённый на рис. 10 и будем теперь считать, что веса дуг являются их пропускными способностями. Приведём протокол решения задачи о пути максимальной пропускной способности, соединяющем вершины X0 и X9 (сравните с аналогичным протоколом из пункта 2 настоящего параграфа).

X1

X2

X3

X4

X5

X6

X7

X8

X9

1/0

10/0

6/0

3/0

1/1

10/3

4/3

1/3

3/5

3/7

1/2

10/1

4/4

2/4

3/8

5/2

4/6

5/9

5/6

5/9

Из этой таблицы следует, что максимальная пропускная способность путей, соединяющих вершины X0 и X9, равна 5 и что путь (X0, X3, X1, X2, X9) имеет максимальную пропускную способность.

2. В том же графе с теми же весами дуг удалим дуги с концом в вершине X0 и рассмотрим задачу об A-оптимальном пути для упорядоченной полугруппы A=(A, min, £), где A={1, 2,…, 10} и min — бинарная операция на A, которая по двум числам находит минимальное из них. Эта задача может быть интерпретирована как задача о пути минимальной пропускной способности. Такая задача может возникнуть, например, если мы хотим минимизировать утечку информации, закрыв все пути, кроме одного (предположим, что по некоторым причинам все пути закрыть невозможно).

Условие поглощения для данной упорядоченной полугруппы сводится к тому, что вес каждого цикла должен быть равен 10. В рассматриваемом случае это условие не выполнено. Однако Оно является достаточным, а не необходимым условием разрешимости задачи, и если алгоритм волны заканчивает свою работу (не зацикливается), То результат даёт ответ на поставленный вопрос.

Приведём протокол работы алгоритма волны в этом случае:

X1

X2

X3

X4

X5

X6

X7

X8

X9

1/0

10/0

6/0

3/0

1/1

1/1

3/5

2/5

1/2

1/2

1/3

1/3

2/7

1/9

1/5

Итак, все пути из вершины X0 минимальной пропускной способности имеют пропускную способность 1. Путь минимальной пропускной способности из X0 в X8:

(X0, X1, X2, X9, X8).

3. В том же графе зададим дополнительно цены путей, так что каждая его дуга будет снабжена весом (W1, W2), где W1 — пропускная способность, а W2 — цена дуги. Представим эту информацию в виде следующей матрицы весов:

X0

X1

X2

X3

X4

X5

X6

X7

X8

X9

X0

1, 0

10, 1

6, 2

3, 3

X1

1, 4

10, 5

10,5

X2

10, 4

1, 3

2, 2

5, 1

X3

10, 0

10, 0

1, 1

4, 2

4, 3

1, 4

X4

2, 5

4, 5

5, 4

2, 3

X5

6, 2

4, 1

3, 0

2, 0

X6

1, 1

5, 2

3, 3

5, 4

3, 5

8, 5

X7

3, 4

2, 3

5, 2

8, 1

X8

3, 0

8, 0

5, 1

X9

5, 2

2, 3

8, 4

5, 5

Приведём протокол работы алгоритма волны для задачи о путях максимальной пропускной способности и минимальной цены при равных пропускных способностях:

X1

X2

X3

X4

X5

X6

X7

X8

X9

(1, 0)/0

(10, 1)/0

(6, 2)/0

(3, 3)/0

(1, 5)/1

(1, 2)/3

(4, 3)/3

(1, 5)/3

(3, 2)/5

(2, 2)/5

(1, 3)/2

(3, 7)/6

(2, 3)/7

В частности, оптимальный путь (X0, X5, X7) из вершины X0 в вершину X7 имеет пропускную способность 2 и цену 2.

Оставить комментарий