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

Алгоритмы на графахПоиск по графу Задан граф 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 организовано в виде очереди: первым пришел — первым ушел. 1524763vПоиск в ширину Множество Q организовано в виде очереди: первым пришел — первым ушел.1524763vПоиск в ширину Множество Q организовано в виде очереди: первым пришел — первым ушел.1524763vПоиск в ширину Множество Q организовано в виде очереди: первым пришел — первым ушел.1524763vПоиск в ширину Множество Q организовано в виде очереди: первым пришел — первым ушел.1524763vПоиск в ширину Множество Q организовано в виде очереди: первым пришел — первым ушел.1524763vПоиск в глубину Множество Q организовано в виде стека: последним пришел — первым ушел.1524763vПоиск в глубину Множество Q организовано в виде стека: последним пришел — первым ушел.1524763vПоиск в глубину Множество Q организовано в виде стека: последним пришел — первым ушел.1524763vПоиск в глубину Множество Q организовано в виде стека: последним пришел — первым ушел.1524763vПоиск в глубину Множество Q организовано в виде стека: последним пришел — первым ушел.1524763vЗадача о кратчайшем пути Задан ориентированный граф G=(V, E), we ≥ 0, eE — вес дуги. Найти кратчайшие расстояния от заданной вершины v до остальных вершин.vG = (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) Утверждение. Алгоритм Дейкстры находит кратчайшие пути из вершины 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 := dikdik := min { dik; dij + djk } если dik Время 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. Алгоритмы на графах. Динамическое программирование