Задача о гамильтоновом цикле состоит в выяснении, имеет ли заданный граф G гамильтонов цикл относится к NP-классу.

NP-gлные задачи:::::

__Наиболее серьезная причина полагать, что P ≠ NP — существование NP полных задач.

__Неформально!!!, задача Q сводится к задаче Q ′, если задачу Q можно решить за полиномиальное время для любого входа, считая известным решение задачи Q ′ для какого-то другого входа. Например, задача решения линейного уравнения сводится к задаче решения квадратного уравнения.

__NP-полная задача — это такая задача из класса NP, к которой можно свести любую другую задачу из класса NP.

__NP-полные задачи образуют подмнож. «самых сложных» задач в классе NP. Если для любой NP-полной задачи будет найден полиномиальный алгоритм решения, то и любая другая задача из класса NP может быть решена за полиномиальное время.

__Все перечисленные NP- задачи явл. NP-полными. В том числе задача о цикле Гамильтона.

СООТНОШЕНИЕ P и NP:::::

__Всякая задача из P принадлежит NP.

__Таким образом, класс NP включает в себя класс P. В данное время, неизвестно совпадают ли классы P и NP, но большинство специалистов полагает, что нет.

__Если окажется, что Р= NP

1) NP задачи окажутся решаемы за разумное время.

2) Существует ряд задач, которые намеренно используют задачи экспоненциальной сложности (т.е. предполагая, что задачу решить не возможно). Например, В криптографии существует раздел о шифровании с открытым ключом, расшифровать которые практически не возможно. Если вдруг P = NP, то многие секреты перестанут быть таковыми.

33. Необхдимое и Достаточное условия для определения дерева. Задача построения минимального остовного дерева. Алгоритм Краскала. Алгоритм Прима. Оценка вычислительной сложности.

__Граф G = <V, E> называется деревом, если он связен и ацикличен.

__Необходимые и достаточные условия определения дерева G =<V, E>:

1)Любая пара вершин в G соединена единственным путем

2)G связен и m = n – 1, где n – число вершин, m- число ребер

3)G связен и удаление хотя бы одного его ребра нарушает связность графа

4)G ацикличен, но если добавить хотя бы одно ребро, то в G появится цикл.

ЗАДАЧА ПОСТРОЕНИЯ::::

_В полном графе с n-вершин, существует n^{n –2} возможных остовных деревьев.

__Задача о проведении дорог. Для каждой пары городов А и В известна стоимость С (А, В) строительства дорог между ними (вес ребра). Нужно построить самую дешевую сеть дорог из всех n^{n –2} возможных. Если имеется 10 городов (n=10), то всего 10⁸ возможных сетей дорог

___Искомый граф должен быть экономическим деревом, т.е. обладать наименьшей длиной (длина – сумма весов ребер). Перебор не пригоден.

__Задача построения минимального остовного дерева — это одна из немногих задач теории графов, которую можно считать полностью решенной.

АЛГОРИТМ КРУСКАЛА:::

_Пусть есть связный граф, имеющий n вершин.

__Шаг 1. Упорядочим ребра графа в порядке их неубывания их весов.

__Шаг 2. Начиная с первого ребра в этом списке, добавлять ребра в графе, соблюдая условие: такое добавление не должно приводить к появлению цикла.

__Шаг 3. Повторять Шаг 2 до тех пор, пока число ребер в графе не станет равно n – 1. Получившееся дерево явл. минимальным остовным деревом графа.

АЛГОРИТМ ПРИМА::::

Для полных графов более эффективный алгоритм был предложен Примом и Дейкстрой, который можно реализовать со сложностью n log₂n

__Шаг 1. Выбрать произвольную вершину и ребро, соединяющее ее с ближайшим по весу соседом.

__Шаг 2. Найдите не присоединенную (еще) вершину, ближе всего лежащую к одной из присоединенных, и соедините с ней.

__Шаг 3. Повторять Шаг 2 до тех пор, пока все вершины не будут присоединены.

34. Взвешенные графы и орграфы. Длина пути в обычном и во взвешенном орграфе, расстояние между вершинами. Практическая интерпретация весов. Принцип оптимальности Беллмана. Алгоритм нахождения кратчайшего пути в ориентированном графе и его вычислительная сложность.

__Знаковый граф — каждому ребру которого приписан некоторый знак.

__Нагруженным (взвешенный) называется граф G = < V, E > дугам (ребрам) которого приписаны веса. Каждой дуге < u, v > Î E поставлено в соответствие некоторое вещественное число a (u, v), называемое весом данной дуги.

_В компьютерном представлении веса задаются матрицей.

_Если вершины u и v не связаны дугой, то вес a (u, v) = ¥.

__Если последовательность вершин v ₀, v ₁,..., v_p определяет путь в G, то длина пути определяется как сумма

Веса могут быть отрицательны.

Практическая интерпретация: Если передвижение груза рассм. с точки зрения безопасности (веса — безопасности), то безопасность всего пути будет определяться как произведение весов дуг.

Принцип оптимальности Беллмана: если существует кратчайший путь между двумя точками, то длина пути между любыми двумя точками кратчайшего пути тоже будет минимальна.

35. Алгоритм нахождения кратчайшего расстояния от источника до всех верши в общем случае – алгоритм Форда-Беллмана. Сложность алгоритма

__Кратчайшим путем между двумя вершинаминазывается путь имеющий минимальную дину.

__Кратчайшим расстоянием между двумя вершинаминазывается длина кратчайшего пути.

__Данные: Ориентированный граф < V, E > с n вершинами с выделенным источником s Î V, матрица дуг A [ u, v ], u, v Î V (граф не содержит контуров отрицательной длины).

__Результаты: Расстояния от источника до всех вершин графа: D [ v ]= d (s, v), v Î V.

__В каждой итерации (верхний цикл) производится новая оценка расстояния для всех вершин v_i (средний цикл) кроме источника.

__Оценка расстояния для каждой вершины v_i, происходит путем сравнения расстояния через все вершины u_i существующие в этом графе, кроме источника (внутренний цикл): NО = D[v] и D[u]+A[u,v]

В наихудшем случае, за каждую итерацию найденные минимальные пути включают 1 промежуточную вершину. Кратчайший путь между двумя вершинами в графе с n вершинами может содержать n-2 промежуточные вершины. Тогда в наихудшем случае потребуется n-2 итерации.

СЛОЖНОСТЬ АЛГОРИТМА:

__Очевидно, что временная сложность алгоритма есть O(n ³). Три вложенных друг в друга цикла.

___Можно, закончить вычисления, когда выполнение очередной итерации не вызывает изменения ни одной из переменных D [ v ], v Î V. Это может наступить для k < n – 2, однако такая модификация алгоритма не изменяет существенным образом его сложности.

___Для редких графов (m << n ²) удобнее представлять граф списками предшествующих вершин ПРЕДШ [ v ], v Î V. Заменяя строку 5 на

for u Î ПРЕДШ [ v ] do D [ v ]:=min(D [ v ], D [ u ] + A [ u, v ]),

получаем алгоритм со сложностью O(nm).

36. Алгоритм Дейкстры — алгоритм нахождения кратчайшего расстояния от источника до всех верши в случае неотрицательных весов. Сложность алгоритма.

Данные: орграф <V, E> с n вершинами с выделенным источником s Î V, матрица весов A[u, v], u, v Î V (без отрицательных весов).

Результат: определены расстояния от источника до всех вершин графа: , .

Сложность алгоритма — .

Алгоритм:

· Находится минимальное расстояние от источника до какой-либо вершины.

· Найденное минимальное расстояние для этой вершины больше не изменяется.

· Вершина с минимальным расстоянием исключается из множ. вершин, для которых ищут минимальное расстояние.

· Расстояние до этой вершины используется для оценки кратчайших расстояний до других вершин.

· Процесс повторяется, пока для каждой вершины не будет найдено минимальное расстояние.

37. Лемма о перенумерации вершин. Алгоритм перенумерации вершин графа.

Лемма. В произвольном бесконтурном графе вершины можно перенумеровать так, что каждая дуга будет иметь вид , где .

Данные: бесконтурный орграф < V, E >, определяемый списками смежности ЗАПИСЬ [ v ], v Î V.

Результаты: Определен номер NR [ v ] для каждой вершины v Î V такой, что для произвольной дуги á u, v ñ Î E выполняется нер-во NR [ u ] < NR [ v ].

NUM – номер последней пронумерованной вершины.

ЧЗАХ [ v ] – массив с числом дуг, вход. в каждую вершину.

CTEK – вершины, в которые не заходит ни одна дуга.

Сложность — О(m), т. к. каждая дуга анализир. 1 раз.

Алгоритм:

· Алгоритм основывается на том, что в произвольном (непустом) бесконтурном графе существует вершина, в которую не заходит ни одна дуга. Такие вершины накапливаются в стеке.

· В строке 10 выбирается верхний эл-т стека u и этой вершине присваивается самый маленький из еще неиспользованных номеров. Т.е. все дуги, выходящие из этой вершины, ведут к вершине с большими номерами.

· Затем вершина u вместе с выходящими из нее дугами удаляется из графа. Это приводит к уменьшению на единицу числа дуг, заходящих в каждую вершину v и выходящую из u.

· Если для какой-нибудь вершины v число заходящих дуг сводится к нулю, то v помещается в стек.

· Опустошение стека, вызывающее окончание выполнения алгоритма (цикл 9), наступает не раньше, чем после присвоения номеров всем вершинам графа.

1. Begin

2. for v Î V do ЧЗАХ [v]:= 0; ЧЗАХ [v] - число дуг, заходящих в v

3. for u Î V do

4. for v Î ЗАПИСЬ [u] do ЧЗАХ [v]:= ЧЗАХ [v] + 1; // подсчет дуг в вершинах

5. СТЕК:= Æ;

6. for v Î V do

7. if ЧЗАХ [v] = 0 then СТЕК Ü v; //если в v не заходят дуги, то она в СТЕК

8. num:= 0; //обнуляем присваиваемый номер

9. while СТЕК ¹ Æ do

10. begin u Ü СТЕК; // достаем вершину из СТЕКа

11. num:= num + 1; NR[u]:= num; //присваиваем ей следующий номер

12. for v Î ЗАПИСЬ [u] do

13. begin ЧЗАХ [v]:= ЧЗАХ [v] – 1; // уменьшаем на 1 число зах. в смеж. вер.

14. if ЧЗАХ [v] = 0 then СТЕК Ü v; //если в v нет дуг, вставляется в СТЕК

15. end

16. end

17. End

38. Алгоритм нахождения кратчайшего расстояния от источника до всех верши в случае бесконтурных графов. Сложность алгоритма.

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

Данные: ориентированный граф < V, E >, где для произвольной дуги имеем . Этот граф определен списками ПРЕДШ[ v ], v Î V.

Результаты: Расстояния от v ₁ до всех вершин графа: D [ v_i ] = d (v ₁, v_i), i = 1,..., n.

Сложность алгоритма порядка O(m), т. к. каждая дуга анализируется (стр. 6) в точности 1 раз.

Алгоритм:

· Выбир. вершина-источник.

· Вып. первонач. оценка кратчайших расстояний.

· Вып. оценка расстояний ч/з верш., предшеств. текущей — выбир. мин. между найденным расстоянием до текущей и расстоянием до нее ч/з предшествующие.

1. Begin

2. D [ v s]:= 0; // выбор источника

3. for j:= 2 to n do D [ vj ]:= ¥; первоначальная оценка

4. for j:= 2 to n do // цикл по всем вершинам

5. for vi Î ПРЕДШ [ vj ] // вершины, предшествующие текущей

6. do D [ vj ]:= min(D [ vj ], D [ vi ] + A [ vi, vj ]); // оценка расстояния через предшествующие

7. End

39. Система PERT. Алгоритм топологической сортировки. Критический путь и способ его нахождения.

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

В задаче о планировании заданий соответствующий бесконтурный граф имеет название «система PERT».

Предположим, что необходимо определить порядок, в котором следует изучать предметы, учитывая их зависимость друг от друга. Это позволяет сделать алгоритм топологической сортировки (по сути аналогич. алгоритму перенумерации вершин).

Алгоритм генерир. послед-ть согласованных меток для вершин бесконтурного графа таким образом, что каждая дуга будет иметь вид , где . В начале работы алгоритма значение A(v) равно кол-ву дуг входящих в данную вершину // аналог ЧЗАХ

Алгоритмы находят применения в методах PERT или CPM. Эти методы основываются на построении графа (сети PERT или сети CPM), дуги кот. соответствуют элементарным задачам, составляющим проект, а их веса указывают на время, необходимое для решения отдельных задач.

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

Дата добавления: 2015-11-16