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

Этот путь не может состоять только из ребер остова, так как тогда в был бы цикл. Выбросим из такое ребро этого пути, которое не является ребром остова, и добавим рассматриваемое ребро с концами A и B. Новый остов не дороже остова, но имеет меньше ребер, не являющихся ребрами остова. Например, рассмотрим нагруженный граф, заданный таблицей смежности:

Расположим ребра в порядке возрастания:(E, C), (A, D), (B, C), (B, E),(C, D), (A, C), (A, B), (D, E), (B, D), (A, E).Их стоимости равны: 1, 2, 3, 3, 7, 16, 33, 77, 222, 719. Включаем в остов ребра:(E, C), (A, D), (B, C).Следующее ребро включать нельзя, так как появится цикл. Включаем в остов ребро (C, D). Получаем 4 ребра и заканчиваем построение остова. Рассмотрим еще один пример построения минимального остовного дерева. В начале процесса мы выберем произвольный узел A. Необходимо отметить, что в случае если минимальное остовное дерево единственно, при другом выборе начальной вершины результат будет тем же самым. Исходный граф изображен на рисунке 8.Рис. 8 Исходный граф Все вершины, непосредственно связанные с A, образуют исходную кайму. Выполним построение МОД: Ребро наименьшейцены связывает узлы A и B, поэтому к уже построенной части МОД добавляется вершина B вместе с ребром AB (Рис.9)Рис. 9 Добавление первой вершины.

При добавлении к дереву вершины B к кайме добавляются новые вершины E и G, т.к. они соединены только с вершиной B уже построенной части дерева, мы добавляем соединяющие ребра к списку рассматриваемых на следующем шаге (Рис .10). Рис. 10 Добавлена вторая вершина.

На данном шаге необходимо проверить, являются ли ребра, ведущие из вершины A в C, D и F, кратчайшими среди ребер, соединяющих эти вершины с деревом, или есть более удобные ребра, которые исходят из B. В исходном графе вершина B не соединена непосредственно ни с C, ни с F, поэтому для них ничего не меняется. А вот ребро BD короче ребра AD, и поэтому его необходимо заменить. Наименьший вес из пяти ребер, идущих в кайму, имеет ребро BE, поэтому к дереву нужно добавить его и вершину E (рис. 11). Вес ребра EG меньше веса ребра BG, поэтому оно замещает последнее. Рис. 11 Добавлениетретьейвершины.

Из четырех ребер, ведущих в кайму, наименьший вес имеет AC, поэтому следующим к дереву добавляется оно. Добавление к остовному дереву вершины C и ребра AC (рис. 12) не приводит к изменению списка ребер. Рис. 12 К дереву добавлена вершина СЗатем мы выбираем ребро AF и добавляем его к дереву вместе с вершиной F. Кроме того, мы меняем список связей, поскольку вес ребра FD меньше веса ребра BD, а вес ребра FG меньше веса ребра EG. В получившейся кайме (рис. 13) ребро FD имеет наименьший вес среди оставшихся, и оно добавляется следующим. Рис. 13 Добавлена вершина FТеперь осталось добавить к дереву всего один узел.

После этого процесс завершается, и мы построили МОД с корнем в вершине A (рис. 14).Рис. 14 Минимальное остовное дерево.

Корректность теоремы Дейкстры.

Рассмотрим ориентированные конечные нагруженные графы без петель. Пусть граф является сильно связным, т. е. таким, у которого любая вершина достижима из любой другой. При этом он содержит более одной вершины и задается таблицей смежности. Для упрощения восприятия предположим, что каждая вершина смежна с любой другой отличной от нее вершиной. Таким образом, в таблице смежности по диагонали стоят нули, а остальные элементы являются положительными целыми числами. Обозначим через p (A, B) стоимость ребра, идущего из A в B. Для решения вопроса построения кратчайшего пути используем алгоритм Дейкстры.

В нем вершинам приписываются неотрицательные целые числа в качестве меток, которые задают верхнюю границу для кратчайшего расстояния помеченной вершины от выбранной. Следует учесть, что метки бывают временными и постоянными. Временные метки уменьшаются в ходе работы алгоритма до тех пор, пока не становятся постоянными. На одном шаге работы алгоритма единственная из временных меток становится постоянной. Постоянная метка равна кратчайшему расстоянию помеченной вершины от выбранной. Метка вершины A обозначается через n (A).При этом вершинам присваиваются пути из выбранной вершины в рассматриваемую. Следует учесть, что в случае смены метки, меняется и приписанный путь. Алгоритм Дейкстры работает по шагам:

Шаг 0. Выбираем вершину Си присваиваем ей 0. Эта метка объявляется постоянной. Выбранный путь из С в С не содержит ребер. Каждая другая вершина Вв качестве временной метки получает стоимость ребра, идущего из выбранной вершины С в помечаемую вершину В.

Выбранный путь из С в В состоит из одного этого ребра. Шаг Iдля любого i>0. Среди вершин с временными метками находим вершины с наименьшей меткой. Среди таких вершин берем одну. Метку этой вершины, А объявляем постоянной. В случае, если все вершины получили постоянные метки, заканчиваем работу алгоритма.

Метки оставшихся вершин с временными метками заменяем по следующему правилу:

метку B не меняем, если не меньше ;метку вершины B меняем на.

Если, если меньше Если. Выбранный путь из С в В меняем на выбранный путь из С в А, дополненный ребром из, А в В. Переходим на шаг i+1.Согласно алгоритму Дейкстры сначала выполняется инициализация (шаг 0), а потом выполняются шаги 1,2…до тех пор, пока еще есть временные метки. Рассмотрим теорему о корректности алгоритма Дейкстры. Теорема 2. Постоянная метка вершины, А равна кратчайшему расстоянию этой вершины, А от выбранной вершины С.Доказательство. Легко заметить, что метка вершины равна стоимости выбранного пути из C в эту вершину. Кроме того, для вершины с постоянной меткой выбранный путь проходит через вершины с постоянными метками, полученными на предыдущих шагах алгоритма. Покажем, что для вершины, А с постоянной меткой выбранный путь из С в, А является самым дешёвым. Докажем этоиндукцией по номеру шага алгоритма, на котором вершина, А получает постоянную метку. Предположим, что имеется более дешевый путь из C в A. Если путь не проходит только через вершины с постоянными метками на шаге, на котором A получает постоянную метку, пусть D — первая вершина этого пути, которая не получила постоянной метки до рассматриваемого шага, аЕ — предыдущая вершина.Тогда.

Тем более стоимость пути не меньше стоимости пути. Значит, путь проходит только через вершины, получившие постоянные метки до рассматриваемого шага. Рассмотрим предпоследние вершины и путей и. Так как, то стоимость пути не может быть меньше стоимости пути. Рассмотрим пример применения алгоритма Дейкстры для построения самого дешевого пути из вершины, А в вершину Е в ориентированном нагруженном графе, стоимости ребер которого заданы таблицей:

Выполним алгоритм по шагам:

Шаг 0. Шаг 1. Постоянную метку получает D. Выбранный путь есть (A, D).Шаг 2. Постоянную метку получает B. Выбранный путь — (A, D), (D, B).Шаг 3. Постоянную метку получает С. Выбранный путь есть (A, С).Шаг 4. Постоянную метку получает Е. Выбранный путь есть (A, D), (D, B), (B, E).Глава 2. Оценка сложности алгоритма на графах.

Оценка сложности алгоритма построения минимального остова.

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

По описанию алгоритма в операциях над графамиA=A (OP (G1)), OP (G2),…, OP (Gr)), Определить множество операций OP (Gi) над каждым графом Gi: где — j-я операция над графами, а — количество таких операций. Определить множество операций над множеством, p=1,, представляющим граф: где — совокупность t-x операций над p-м множеством, представляющим i-й граф, которая выполняется при реализации всех операций над этим графом. Построить модель модели структур данных, выбранных для представления совокупности множеств каждого графа, и определить их емкостную сложность:

Используя те же модели определить функциональную вычислительную сложностьвыполнения основных операций над элементами структуры данных: где D — мощность множества основных операций. Построить модель выполнения каждой операции над множеством в основных операциях над элементами структуры данных. Используя полученные в п. 4 вычислительные сложности реализации основных операций над элементами структур данных и формулы временной и вычислительной сложности:

получить функциональную вычислительную ложность ее выполнения, т. е. определить.

Построить модель выполнения каждой операции над графом в элементарных операциях над множествамии, используя полученные в п. 5 вычислительные сложности реализации элементарных операций над множествами и формулы временной и вычислительной сложности из п. 5, получить функциональную сложность ее выполнения, т. е. определить {{Построить математическую модель алгоритма в элементарных операциях над графами и, используя формулы временной и вычислительной сложности из п. 5, получить функциональную вычислительную сложность этого алгоритма. Рассчитать емкостную сложность алгоритма как сумму емкостных сложностей структур данных, представляющих графовые модели: Так как вычислительная и временная сложности по определению пропорциональны, расчетные соотношения пп. 4−7 позволяют также оценить время выполнения алгоритма. Оценка сложности алгоритма Дейкстры.

Сложность алгоритма Дейкстры зависит от способа, который выбран для нахождения вершины, а также способа хранения множества непосещенных вершин и способа обновления меток. Рассмотрим оценку сложности для алгоритма Дейкстры. Обозначим через n количество вершин, а через — m количество ребер в графе G. В простейшем случае, когда для поиска вершины с минимальным d[v] просматривается все множество вершин, а для хранения величин d — массив, время работы алгоритма есть .При этом основной цикл алгоритма выполняется порядка n раз, в каждом из них на нахождение минимума тратится порядка n операций, плюс количество релаксаций (смен меток), которое не превосходит количества ребер в исходном графе. Для разреженных графов (т.е. таких, для которых m меньше n2) непосещенные вершины можно хранить в двоичной куче, а в качестве ключа использовать значения d[i], тогда время извлечения вершины из U станет logn, при том, что время модификации d[i] возрастет до logn. Так как цикл выполняется порядка n раз, а количество релаксаций не больше m, скорость работы такой реализации.

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

Заключение

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

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

Список литературы

Ахо А., Хопкрофт Дж., Ульман Дж. Структуры данных и алгоритмы: Пер. с англ.: — М.: Издательский дом «Вильямс», 2001 г.

— 384 с., ил. Вирт Н. Алгоритмы и структуры данных: Пер. с англ. — 2-ое изд., испр.

— СПб.: Невский диалект, 2001 г. — 352 с., ил. Иванова Г. С. Математические модели структур данных. Информационные технологии, 2008б № 9б с. 44−52.Иванова Г. С. Автоматизация анализа вычислительной и емкостной сложности алгоритмов на множествах и графах. Инженерный журнал: наука и инновации, 2013, вып.

№ 11.Карпов Ю. Г. Теория автоматов — СПб.: Питер, 2002 г. — 224с., ил. Кормен Т., Лейзерсон Ч., Риверст Р., Штайн К. Алгоритмы: построение и анализ. Москва, Вильямс, 2011, 1296 с. Кнут Д.

Искусство программирования. Тома 1, 2, 3. 3-е изд. Пер. с англ.: Уч.

пос. — М.: Изд. дом & quot;Вильямс", 2001 г. Кормен Т., Лейзерсон Ч., Ривест Р.

Алгоритмы: построение и анализ. — М.: МЦНМО, 2001 г. -.

960 с., 263 ил. Макконнел Дж. Анализ алгоритмов. Вводный курс. -.

М.: Техносфера, 2002 г. — 304 с. Новиков Ф. А. Дискретная математика для программистов.

— СПб.: Питер, 2001 г. — 304 с., ил. Романовский И. В. Дискретный анализ.

Учебное пособие для студентов, специализирующихся по прикладной математике. — Издание 2-ое, исправленное. -.

СПб.; Невский диалект, 2000 г. — 240 с., ил. Успенский В. А. Машина Поста. — М.: Наука, 1999 г.

— 96 с.