Реферат: Алгоритмы на графах Поиск по графу

Алгоритмы на графах


Поиск по графу

Задан граф G = (V, E), A(v), vV — списки смежности

Найти компоненты связности.

Алгоритм ПОИСК(v)

Q := {v}, пометить v.

До тех пор пока Q   выполнять

Пусть x  Q; удалить x из Q;

Для всех y  A(x) :
если y не помечена, то добавить y в Q и пометить y

Утверждение. Алгоритм ПОИСК помечает все вершины графа,
достижимые из v, за время O(|E|).

Доказательство. Пусть V1 — множество вершин, достижимых из v

Для записи v требуется время O(1).

Работа с множеством Q. Добавление и удаление элементов
производится 2|V1| раз. Если Q — очередь или стек, то каждое включение или исключение требует O(1) времени.

Поиск по спискам смежности. Каждый элемент в списке
просматривается не более одного раза. Всего 2|E| элементов.

Суммарная оценка — O(|E|).

^ Поиск в ширину

Множество Q организовано в виде очереди:

первым пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в ширину

Множество Q организовано в виде очереди:

первым пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в ширину

Множество Q организовано в виде очереди:

первым пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в ширину

Множество Q организовано в виде очереди:

первым пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в ширину

Множество Q организовано в виде очереди:

первым пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в ширину

Множество Q организовано в виде очереди:

первым пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в глубину

Множество Q организовано в виде стека:

последним пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в глубину

Множество Q организовано в виде стека:

последним пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в глубину

Множество Q организовано в виде стека:

последним пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в глубину

Множество Q организовано в виде стека:

последним пришел — первым ушел.



1

5



2

4

7

6

3

v


Поиск в глубину

Множество Q организовано в виде стека:

последним пришел — первым ушел.



1

5



2

4

7

6

3

v


Задача о кратчайшем пути

Задан ориентированный граф G=(V, E), we ≥ 0, eE — вес дуги.

Найти кратчайшие расстояния от заданной вершины v до остальных вершин.


v

G = (V, E)

we ≥ 0


Алгоритм Дейкстры

Положить W={v};  (x) = 0; p(v) = .

Для всех y V \ {v}:

 (y) := wvy;

p(y) := v;

До тех пор пока W  V выполнять

Найти такую вершину xV \W, что  (x)= min {  (y) | yV \W };

Положить W := W {x};

Для всех yV \W

{ z :=  (y);

 (y) := min { (y),  (x) + wxy };

если  (y) < z, то p(y) := x }.


Утверждение. Алгоритм Дейкстры находит кратчайшие пути из
вершины v до каждой из остальных вершин за время O(|V|2).


Доказательство. Покажем, что на каждой итерации:

а) xV величина  (x) равна длине кратчайшего из путей от v до x, все промежуточные вершины которых принадлежат W.

б) yW величина  (y) равна длине кратчайшего из путей от v до y.

Так как в конце работы алгоритма W = V, то из б) следует, что  (x) — вектор кратчайших расстояний.

Проводим индукцию по числу шагов алгоритма

При W = {v} утверждения а), б) верны.

Пусть а), б) верно для некоторого шага.

На шаге 3.1. мы выбираем xV \W такую, что  (x) = min { (y)| yV \W}.

Предположим, что  путь (v, v1, …, vt, x), длина которого меньше  (x). Тогда из а) следует, что в этом пути есть вершина vi W. Если таких несколько, выберем вершину с наименьшим номером. Тогда

 (vi) ≤ длина (v, v1, …, vi) ≤ длина (v, v1, …, vt) ≤  (x), что противоречит выбору x. Значит  (x) — длина кратчайшего пути от v до x и б) будет выполняться после добавления x к W.

На шаге 3.3 после пересчета  (y) = min { (y),  (x) + wxy} получим а), так как любой путь в y идет либо через x, либо мимо x.

Итак а), б) верно. Оценим трудоемкость. Цикл 3 требует O(|V|) итераций. На каждой итерации 3.1 — O(|V|); 3.2 — O(1); 3.3 — O(|V|).

Итого: O(|V|2). ∎

Алгоритм Флойда – Уоршелла

Задан ориентированный граф G=(V, E), we ≥ 0, eE.

Найти кратчайшее расстояние для каждой пары вершин.

Определение. Для квадратной матрицы (dij) операцией треугольника относительно j называется пересчет dik = min {dik, dij+ djk} по всем i,k  j.


Утверждение. Пусть cij — длина дуг орграфа G=(V, E) и

.

Если выполнить над матрицей (dij) операцию треугольника последовательно для j =1, 2,…,|V|, то в полученной матрице каждый элемент dik равен длине кратчайшего пути из i в k.

Доказательство. Покажем, что для каждого j после выполнения операций треугольника t = 1, 2, …, j элемент dik i, k равен длине кратчайшего пути из i в k среди всех путей, промежуточные вершины которых имеют номера не больше j.

Для j = 1 утверждение очевидно.

Пусть оно верно для j = t – 1, и проводится операция для t:
dik = min {dik, dit+ dtk}. Рассмотрим подграф G’ орграфа G на вершинах {1, 2,…, t, i, k}. Если кратчайший путь из i в k в G’ не проходит через t, то минимум достигается на первом аргументе и утверждение верно. Если же он проходит через t, то dit + dtk ≤ dik, а по предыдущему предположению dit и dtk — длины кратчайших путей из i в t и из t в k по вершинам с номерами не более t. ∎

Алгоритм

Для всех i j : dij := cij;

Для всех i : dii := 0;

Для всех i j : eij := 0;

Для всех j :

для всех i j и для всех k  i, k  j :

z := dik

dik := min { dik; dij + djk }

если dik< z, то eik := j.

Время O(|V|3).

Алгоритм работает корректно, даже если есть дуги отрицательной
длины, но нет контуров отрицательной длины.


^ Распределительная задача

Задано:

n — число предприятий;

Y — количество единиц некоторого ресурса;

fk(x) — количество продукции, которое будет произведено на k-м предприятии, если в него будет вложено x единиц ресурса (монотонно неубывающая функция).

Требуется: максимизировать объем продукции

f1(x1) +…+ fn(xn)  max

(1)

x1+…+ xn Y

(2)

xi  0, целые, i = 1,…n.

(3)



Идея динамического программирования (ДП)

Метод ДП (Р. Беллман, В.С. Михалевич, Н.З. Шор ) можно трактовать как алгоритмическую версию рассуждений по индукции.

Пусть sk(y), 1 £ k £ n, 0 £ y £ Y, — оптимальное значение целевой функции задачи (1) – (3), где n заменено на k, Y заменено на y.

Требуется найти sn(Y) и набор переменных, на котором достигается это значение.

Теорема 1. Пусть f1, … , fn ­— монотонно неубывающие функции.

Тогда справедливы следующие рекуррентные соотношения:

s1(y) = f1(y), 0 £ y £ Y;

(4)

sk(y) = max {sk-1(y - x) + fk(x) | 0 £ x £ y}, 2 £ k £ n, 0 £ y £ Y,

(5)



Доказательство: Соотношение (4) очевидно. По определению

sk(y) ³ max {sk-1(y - x) + fk(x) | 0 £ x £ y}.

Пусть теперь — такой вектор, что и

.

Поскольку имеем

.∎

Алгоритм ДП вычисляет множество Sk = {sk(y) | 0  y  Y}, k =1,…, n,
с помощью соотношений (4) и (5), где на каждом шаге оптимизируется ровно одна переменная.



Процесс вычисления S1, …, Sn называется прямым ходом алгоритма.

Число операций 

Память  Y n .




y

S1(y)

S2(y)

…

Sn(y)

0













1













2




























Y










Sn(Y)



При обратном ходе алгоритма вычисляются значения ,
с учетом того, что уже известны Sk(y). Например, определяется из уравнения и так далее.

Число операций  Y n. Память  Y n.

^ Характеристики алгоритмов

Для оценки качества алгоритмов будем использовать два параметра:

TA — трудоемкость (число элементарных операций алгоритма A);

ПА — требуемый объем памяти.

Элементарная операция — одна из арифметических операций: сложение, вычитание, умножение, деление или логическая операция сравнение двух чисел.

Нас будет интересовать зависимость параметров алгоритма от длины записи исходных данных задачи с точностью до порядка величин.

Пример: При Т = 3/2 n2 , будем писать T = O(n2) или T  n2.

Полиномиальные алгоритмы

Определение. Алгоритм A называют полиномиальным, если его трудоемкость TA ограничена полиномом от длины записи исходных данных, то есть существует константа c > 0 и натуральное число k такие, что TA  c Lk, где L — длина записи исходных данных.

Пример: Пусть fi (xi) = ai  xi, тогда ,

но TДП = O(Y2n), то есть алгоритм ДП не является полиномиальным.


Обобщим задачу (1)–(3):

f1(x1) +…+ fn(xn)  max

(1)

h1(x1) +…+ hn(xn) Y

(2)

ai  xi  0, целые, i = 1,…n.

(3)

Если hi(x) — целочисленные монотонно неубывающие функции,
то вместо (4)–(5) можно использовать следующие
рекуррентные соотношения:

s1(y) = f1(x*), где x* = max{x  a1 | h1(x)  y}, 0 £ y £ Y;

(4)

s(y) =

(5)



Упражнение 1. Доказать справедливость соотношений (4)–(5).


^ Обратная задача — поиск наименьших затрат на получение заданного количества продукции:



h1(x1) +…+ hn(xn)  min

(6)

f1(x1) +…+ fn(xn)  D

(7)

ai  xi  0, целые, i = 1,…n.

(8)



Если fk(x) — целочисленные монотонно неубывающие функции, то для решения задачи (6)–(8) можно использовать идеи динамического программирования.

Пусть

Для 1 k  n, 0  d  D обозначим через tk(d) — оптимальное решение задачи (6)–(8), в которой n заменено на k, а D заменено на d.

Требуется найти tn(D).

Рекуррентные соотношения

0  d  D,

(9)

tk(d) = min{tk–1(d – fk(x)) + hk(x)| 0  x  ak, x },

k  2, 0  d  D.

(10)

Упражнение 2. Доказать справедливость соотношений (9)–(10).

Теорема 2: Предположим, что D — наибольшее число, для которого оптимальное значение целевой функции задачи (6)–(8) не превосходит Y. Тогда оптимальное значение целевой функции задачи (1’)–(3’) равно D.

Доказательство: Пусть D удовлетворяет условию теоремы

и — соответствующее решение задачи (6)–(8).

Значит

и


Следовательно, D не превосходит оптимального решения D1 задачи
(1’)–(3’). Если бы D1было больше D, то решение задачи (6)–(8), в
которой D заменено на D1, тоже не превышало бы Y, что противоречит максимальности D. ∎




Лекция 2. Алгоритмы на графах. Динамическое программирование