оценка сложности алгоритма построения графа

Теория алгоритмов - это наука, которая изучает общие свойства и закономерности алгоритмов и разнообразные формальные модели их представления. На основе формализации понятия алгоритма существует возможность их сравнения по эффективности, проверка их эквивалентности, определение областей применимости.
В 1930-х годах были разработаны разнообразные формальные модели алгоритмов (Пост, Тьюринг, Черч). Данные модели, также как и предложенные в 1950-х годах Колмогоровым и Марковым, оказались эквивалентными. Их эквивалентность определяется тем, что любой класс проблем, разрешимых в одной модели, разрешимы и в другой.
В настоящее время всё большее распространение в области проектирования и разработки программных систем получают практические рекомендации, полученные на основе теории алгоритмов.
Одной ...

ВВЕДЕНИЕ 2
Глава 1. Графы и способы их задания 4
1.1. Основные понятия теории графов 4
1.2. Область применения графов 9
1.3. Теоретические основы теории сложности вычислений 12
1.3.1. Основные понятия и принципы теории сложности вычислений 12
1.3.2. Сложностные классы задач 15
3. Проблема P NP 16
4. Класс NPC (NP – полные задачи) 17
1.3.3. Временная и емкостная сложности 18
1.4. Алгоритмы на графах и порядок оценки их сложности 19
1.4.1. Алгоритм построения минимального остова 19
1.4.2. Корректность теоремы Дейкстры 26
Глава 2. Оценка сложности алгоритма на графах 30
2.1. Оценка сложности алгоритма построения минимального остова 30
2.2. Оценка сложности алгоритма Дейкстры 32
Заключение 34
Список литературы 35

Традиционно понятие сложности алгоритма связано с использованием временных ресурсов и ресурсов памяти, т.е. насколько много необходимо времени для реализации алгоритма, насколько много при этом расходуется память? Учет памяти при этом ведется по объему данных и не принимается во внимание память, расходуемая для записи и выбора команд. Необходимо отметить, что время рассчитывается в относительных единицах так, чтобы эта оценка, по возможности, была одинаковой при различных незначительнымх вариациях.
Такой подход сложился исторически и ориентируется, прежде всего, на инженерные и научные теории алгоритмов, где объемы данных в несколько раз превышают размеры самого алгоритма, а алгоритм, в свою очередь, может выполняться несколько часов. В этом случае следует учесть вид и назначение приложени я, для которого применяется алгоритм. Например, в научных и инженерных приложениях большое время вычислений может доставить неудобство только пользователям, а в то в ряде других областей ресурсы настолько принципиальны, что может возникнуть вопрос о целесообразности всего проекта из-за неэффективной работы алгоритма. В частности, к таким областям можно отнести системы реального времени (real-time systems). Это, основанные на компьютерах, системы, которые управляют процессами в реальном мире или обрабатывают информацию, которая служит для принятия оперативных решений.
Объект исследования: алгоритмы на графах.
Предмет исследования: оценка сложности алгоритмов на графах.
Цель исследования: на основе теоретического анализа временной и емкостной сложности алгоритмов на графах математически обосновать применение формул оценки сложности для алгоритма построения минимального остовного дерева.
Для достижения поставленной цели были сформулированы следующие задачи:
1. На основе теоретического анализа литературы сформулировать основные понятия теории графов, рассмотреть способы их задания.
2. Изучить сложностные классы задач, а также особенности оценки временной и емкостной сложности алгоритмов на графах.
3. Математически обосновать оценку сложности алгоритма минимального остовного дерева и алгоритма Дейкстры.
 

Задача заключается в определении цепочки обменов, оптимальной с точки зрения, например, организатора обмена и согласованной с интересами участников цепочки и существующими ограничениями [6, 9, 17].Управление проектами С точки зрения теории графов проект - совокупность операций и зависимостей между ними (сетевой график - см. ниже). Хрестоматийным примером является проект строительства некоторого объекта. Совокупность моделей и методов, использующих язык и результаты теории графов и ориентированных на решение задач управления проектами, получила название календарно-сетевого планирования и управления (КСПУ) [7, 10]. В рамках КСПУ решаются задачи определения последовательности выполнения операций и распределения ресурсов между ними, оптимальных с точки зрения тех или иных критериев (времени выполнения проекта, затрат, риска и др.).Модели коллективов и групп, используемые в социологии, основываются на представлении людей или их групп в виде вершин, а отношений между ними (например, отношений знакомства, доверия, симпатии и т.д.) - в виде ребер или дуг. В рамках подобного описания решаются задачи исследования структуры социальных групп, их сравнения, определения агрегированных показателей, отражающих степень напряженности, согласованности взаимодействия и др.Модели организационных структур, в которых вершинами являются элементы организационной системы, а ребрами или дугами - связи (информационные, управляющие, технологические и др.) между ними [13, 18].Способы задания графовРассмотрим основные способы задания графа.Перечисление (список) вершин и ребер (дуг). Геометрический способ. Граф может быть задан с помощью его диаграммы. Например, пусть граф G = (S,U) задан списком вершин и ребер: S={x1, x2,x3,x4,x5,x6},U={x1,x2, x1,x3, x1,x6,x2,x3, x2,x5,x3,x4, x3,x5, x3,x6, (x4,x5)}.Тогда граф можно задать с помощью диаграммы, представленной на рисунке. 2. Рис.2 Геометрический способ задания графаМатричный способ. Этот способ задания используется наиболее часто.Рассмотрим задание графа матрицей смежности вершин, матрицей смежности дуг, матрицей инциденций и матрицей Кирхгофа. Матрицей смежности вершин графа G = (S,U) порядка n называется квадратная матрица P(G) порядка n, строки и столбцы которой соответствуют вершинам графа, где элементы pijравны числу дуг, идущих из i-й вершины в j-ю. Для неориентированного графа матрица смежности вершин является симметричной относительно главной диагонали.Матрицей смежности дуг графа G = (S,U), где U=m, называется квадратная матрица QG=qijпорядка m, элементы qij которой равны единице, если дуга uiнепосредственно предшествует дуге ui, и равны нулю в остальных случаях. В случае неориентированного графа элемент qij равен единице, если ui и uj смежны, и нулю, если эти дуги не смежны. Матрицей инциденций мультиграфа G = (S,U), где S=n иU=m, называется прямоугольная матрица R(G) = размерности n × m. Элементы rijэтой матрицы равны 1, если дуга uj исходит из i-й вершины; –1, если дуга uj входит в i-ю вершину; 0, если дуга uj не инцидентна i-й вершине. Для неориентированного мультиграфа элемент rijравен единице, если вершина xi инцидентна ребру uj , и нулю, если вершина xi не инцидентна ребру uj . Матрицей Кирхгофа графа G = (S,U), где S=n называется матрица B(G) = порядка n, где bij=-1, если i≠j и xi смежна с xj;0, если i≠j и xi не смежна с xj;degxi, если i=j.Очевидно, что сумма элементов в каждой строке и каждом столбце матрицы B(G) равна нулю. Кроме того, из этого следует, что алгебраические дополнения всех элементов матрицы Кирхгофа равны между собой.Теоретические основы теории сложности вычисленийОсновные понятия и принципы теории сложности вычисленийМатематика разрабатывает эффективные методы решения широких классов задач. Развитие теории и практики решения дискретных и комбинаторных задач показали, что общность метода и его эффективность находятся в известном противоречии. Важно знать, можно ли в принципе надеяться на создание достаточно общих и эффективных методов или нужно идти по пути разбиения задач на все более узкие классы и для этих классов разрабатывать эффективные алгоритмы.Неудачи исследователей на этом пути привели к необходимости анализа сложности задач. Возникло интенсивно развивающееся «сложностное» направление исследований. Число публикации в этой области быстро растет и проблематика эта весьма актуальна, ибо такие задачи часто возникают на практике и их решение средствами ЭВМ наталкивается на трудности больших затрат машинного времени.Рассматривая некоторую алгоритмически разрешимую задачу, и анализируя один из алгоритмов ее решения, мы можем получить оценку трудоемкости этого алгоритма в худшем случае. Такие же оценки мы можем получить и для других известных алгоритмов решения данной задачи. Рассматривая задачу с этой точки зрения, возникает вопрос – существует ли алгоритм, решающий задачу с такой трудоемкостью в худшем случае.Другая, более точная формулировка, имеет следующий вид: какова оценка сложности самого «быстрого» алгоритма решения данной задачи в худшем случае? Очевидно, что это оценка самой задачи, а не какого либо алгоритма ее решения. Анализ трудностей, встретившихся на пути создания эффективных методов решения дискретных задач, привел к постановке центральной теоретико-методологической проблемы - можно ли исключить перебор при решении дискретных задач. Речь идет о принципиальной возможности найти нужное решение, не перебирая всех или почти всех вариантов в задаче. Эта проблема имеет не только чисто математическое, но и глубокое познавательное значение. Оно заключается в том, что при поиске эффективных точных методов решения широкого класса дискретных задач надо учитывать возможность отсутствия таких методов признав, что существуют «труднорешаемые задачи». До настоящего времени эта проблема остается открытой.Феномен труднорешаемых задач не нов для математики. После уточнения понятия алгоритма было обнаружено наличие алгоритмически неразрешимых проблем.В переборных задачах имеется конечное множество вариантов, среди которых нужно найти решение. Но с ростом n число вариантов часто быстро растет и задача становится труднорешаемой, т. е. практически неразрешимой. Поэтому в конечной области аналогом алгоритмической неразрешимости является перебор экспоненциального числа вариантов, а аналогом алгоритмической разрешимости существование алгоритма существенно более экономичного, чем перебор. Переборная задача решаема эффективно, если имеется алгоритм, решающий ее за время, ограниченное полиномом от «размера задачи».Концепция эффективной (полиномиальной) сводимости переборных задач была развита в работах С. Кука, Р. Карпа, JI. Левина. Роль основного инструмента играет понятие сводимости задач, возникшее в математической логике. Переборная задача П1 сводится к переборной задаче П2, если метод решения задачи Г1 можно преобразовать в метод решения задачи Г2. Сводимость называется полиномиальной, если подобное преобразование можно осуществить за полиномиальное время.Массовой задачей (или просто задачей) называется некоторый общий вопрос, на который следует дать ответ. Обычно задача содержит ряд параметров, или свободных переменных, конкретные значения которых не определены. Задача П определяется следующей информацией:общим списком всех ее параметров;заданием тех свойств, которым должно удовлетворять решение задачи.Индивидуальная задача I получается из массовой задачи П, если всем параметрам задачи П присвоить конкретные значения.Алгоритм -это общая, выполняемая шаг за шагом процедура решения задачи (можно считать ее программой для ЭВМ, написанной на формальном машинном языке). Говорят, что алгоритм решает массовую задачу П, если он применим к любой индивидуальной задаче I из П и обязательно дает решение задачи I. Термин «решение» понимается здесь строго в соответствии с данным выше определением. Нельзя сказать, например, что алгоритм решает задачу о коммивояжере, если он не выдаст маршрут минимальной длины хотя бы для одной индивидуальной задачи.Вообще говоря, нужен наиболее эффективный алгоритм решения задачи. В широком смысле понятие эффективности связано с вычислительными ресурсами, необходимыми для работы алгоритма. Однако обычно под самым эффективным алгоритмом понимается самый быстрый. Поскольку ограничения по времени часто являются доминирующим фактором, определяющим пригодность данного алгоритма, основное внимание будет сосредоточено на этом виде ресурсов.Время работы алгоритма удобно выражать в виде функции от одной переменной, характеризующей размер индивидуальной задачи, т. е. объем входных данных, требуемых для описания задачи. Такой подход удобен, т.к. в дальнейшем сравнительная сложность задач будет оцениваться через их размеры.Сложностные классы задачВ начале 1960-х годов, в связи с началом широкого использования вычислительной техники для решения практических задач, возник вопрос о границах практической применимости данного алгоритма решения задачи в смысле ограничений на ее размерность. Какие задачи могут быть решены на ЭВМ за реальное время?Ответ на этот вопрос был дан в работах Кобмена и Эдмнодса, где были введены сложностные классы задач.Рассмотрим основные из них.Класс P (задачи с полиномиальной сложностью).Задача называется полиномиальной, т.е. относится к классу P, если существует константа k и алгоритм, решающий задачу с Fan=0(nk), где n - длина входа алгоритма в битах n=D/Задачи класса P – это интуитивно, задачи, решаемые за реальное время.К преимуществам алгоритмов из этого класса относятся:для большинства задач из класса P константа k меньше 6;класс P инвариантен по модели вычислений (для широкого класса моделей);класс P обладает свойством естественной замкнутости (сумма или произведение полиномов есть полином).Таким образом, задачи класса P есть уточнение определения «практически разрешимой» задачи.Класс NP (полиномиально проверяемые задачи)Пусть некоторый алгоритм получает решение некоторой задачи – соответствует ли полученный ответ поставленной задаче, и насколько быстро мы можем проверить его правильность?Формально: ∀ D∈DA, D=n поставим в соответствие сертификат S∈SA, такой что D=O(nk) и алгоритм As=As(D,S), такой, что он выдает «1», если решение правильно, и «0», если решение неверно. Тогда задача принадлежит классу NP, если FAs=O(nm).Содержательно задача относится к классу NP, если ее решение некоторым алгоритмом может быть быстро (полиномиально) проверено.Проблема P = NPПосле введения в теорию алгоритмов понятий сложностных классов Эдмондсом была поставлена основная проблема теории сложности – P = NP. Словесная формулировка проблемы имеет вид: можно ли все задачи, решение которых проверяется с полиномиальной сложностью, решить за полиномиальное время?Очевидно, что любая задача, принадлежащая классу P, принадлежит и классу NP, т.к. она может быть полиномиально проверена – задача проверки решения может состоять просто в повторном решении задачи.На сегодня отсутствуют теоретические доказательства как совпадения этих классов (P=NP), так и их несовпадения. Предположение состоит в том, что класс P является собственным подмножеством класса NP, т.е. NP \ P не пусто (рис/ 3)Рис.3 Соотношение классов P и NPКласс NPC (NP – полные задачи)Понятие NP – полноты было введено независимо Куком и Левиным и основывается на понятии сводимости одной задачи к другой.Сводимость может быть представлена следующим образом: если мы имеем задачу 1 и решающий эту задачу алгоритм, выдающий правильный ответ для всех конкретных проблем, составляющих задачу, а для задачи 2 алгоритм решения неизвестен, то если мы можем переформулировать (свести) задачу 2 в терминах задачи 1, то мы решаем задачу 2.Таким образом, если задача 1 задана множеством конкретных проблем DA1, а задача 2 – множеством DA2, и существует функция fs (алгоритм), сводящая конкретную постановку задачи 2 (dA2) к конкретной постановке задачи 1(dA1): fsd2∈DA2=d(1)∈DA1, то задача 2 сводима к задаче 1.Если при этом Fafs=O(nk), т.е. алгоритм сведения принадлежит классу P, то говорят, что задача 1 полиномиально сводится к задаче 2.Принято говорить, что задача задается некоторым языком, тогда если задача 1 задана языком L1, а задача 2 – языком L2, то полиномиальная сводимость обозначается следующим образом: L2 ≤ pL1.Определение класса NPC (NP-complete) или класса NP-полных задач требует выполнения следующих двух условий: задача должна принадлежать классу NP (L є NP);к задаче полиномиально должны сводиться все задачи из класса NP (Lx≤pL, для каждого Lx є NP), что схематично представлено на рис 4.Рис. 4 Сводимость задач класса NP к классу NPCВременная и емкостная сложностиТеория сложности вычислений возникла из потребности сравнивать быстродействие алгоритмов, четко описывать их поведение (время исполнения и объем необходимой памяти) в зависимости от размера входа.Количество элементарных операций, затраченных алгоритмом для решения конкретного экземпляра задачи, зависит не только от размера входных данных, но и от самих данных. Например, количество операций алгоритма сортировки вставками значительно меньше в случае, если входные данные уже отсортированы. Чтобы избежать подобных трудностей, рассматривают понятие временной сложности алгоритма в худшем случае.Временная сложность алгоритма (в худшем случае) — это функция от размера входных данных, равная максимальному количеству элементарных операций, проделываемых алгоритмом для решения экземпляра задачи указанного размера.Аналогично понятию временной сложности в худшем случае определяется понятие временная сложность алгоритма в наилучшем случае. Также рассматривают понятие среднее время работы алгоритма, то есть математическое ожидание времени работы алгоритма. Иногда говорят просто: «Временная сложность алгоритма» или «Время работы алгоритма», имея в виду временную сложность алгоритма в худшем, наилучшем или среднем случае (в зависимости от контекста).По аналогии с временной сложностью, определяют емкостную сложность алгоритма, только здесь говорят не о количестве элементарных операций, а об объеме используемой памяти.Алгоритмы на графах и порядок оценки их сложностиАлгоритм построения минимального остоваРассмотрим некоторый связный неоринтированный взвешенный граф. Каркасом или остовным деревом для этого графа называется связный подграф этого графа, содержащий все вершины графа и не имеющий циклов. Количество ребер в каркасе связного графа всегда на единицу меньше количества вершин графа.557783214561055557Назовем стоимостью остова сумму весов ребер, входящих в него. На рисунках 5 и 6 изображен граф и два его остова соответственно. Остов стоимости 40 является минимальным.Рис. 5 Неориентированный граф G557783214561055557Стоимость 44557783214561055557Стоимость 40Рис.6 Остовы неориентированного граф GУ графа может быть несколько остовов. Например, различные остовы можно построить, запуская поиск в глубину от разных вершин графа. Поиском в глубину называется способ обхода вершин графа, который, начавшись от какой-либо вершины, рекурсивно применяется ко всем вершинам, в которые можно попасть из текущей. Пусть граф с N вершинами задан матрицей смежности A[N][N].Рассмотрим поиск в глубину на примере графа рис.5Движение начинаем с вершины 1 и перебираем все вершины, куда можно попасть из текущей (из первой). Получим следующие пути прохода:1-2-3-6;1-4-5;1-4-7-8.557783214561055557Результат применения поиска в глубину представлен на рисунке 7.Рис. 7 Результат работы поиска в глубинуМинимальным остовным деревом (МОД) связного взвешенного графа называется его связный подграф, состоящий из всех вершин исходного дерева и некоторых его ребер, причем сумма весов ребер минимально возможная. Если исходный граф несвязен, то описываемую ниже процедуру можно применять поочередно к каждой его компоненте связности, получая тем самым минимальные остовные деревья для этих компонент.Так как множество ребер МОД является подмножеством в множестве ребер исходного графа, можно просто перебрать все возможные подмножества и найти среди них МОД. Нетрудно видеть, что это чрезвычайно трудоемкий процесс. В множестве из N ребер имеется 2N подмножеств. Для каждого из этих подмножеств мы должны будем проверить, что оно задает связный подграф, охватывающий все вершины исходного, и не содержит циклов, а затем сосчитать его вес. Процесс можно ускорить после того, как найдено первое остовное дерево. Никакое подмножество ребер, полный вес которого больше, чем у уже найденного наилучшего остовного дерева, не может нам подойти, поэтому нет необходимости проверять связность, ацикличность и охват всех вершин. Однако даже и при этом улучшении сложность метода грубой силы будет порядка O(2N).Для получения остова ребра можно удалять разными способами, однако общее число удаленных ребер не зависит от способа удаления ребер. Так как в результате число вершин должно быть на одну больше числа ребер, число удаленных ребер равно числу ребер минус число вершин плюс один.Располагаем все ребра в порядке возрастания их стоимостей (группы ребер с одинаковой стоимостью можно выписывать в произвольном порядке).Выбираем первое ребро и включаем его в остов.Пусть уже рассмотрены некоторые ребра и некоторые из них включены в остов.Рассмотрим следующее ребро. Если вместе с уже включенными в остов ребрами оно образует граф без циклов, то включаем его в остов, иначе отбрасываем это ребро и переходим к рассмотрению следующего ребра.Алгоритм заканчивает работу, когда в остов будет включено столько ребер, что их число на одно меньше числа вершин.Рассмотрим теорему о корректности алгоритма построения минимального остовного дерева.Теорема 1. Алгоритм действительно строит минимальный остов.Доказательство. Надо доказать, что построенный остов D1 не дороже любого другого остова. Пусть D2— самый дешевый остов. Индукцией по числу ребер в D2, не являющихся ребрами остова Di докажем, что D1 не дороже D2Рассмотрим первое ребро (в порядке их включения в D1) остовa D1, не входящее в D2. Пусть A и B — концы этого ребра. Эти вершины в дереве D2 соединены некоторым элементарным путем. Этот путь не может состоять только из ребер остова D1, так как тогда в D1был бы цикл.