Надежость сети - Программирование, компьютеры и кибернетика курсовая работа
Общее понятие графа, его виды и сущность вершинного покрытия. Написание точного алгоритма решения задачи о надежности сети, нахождение минимального покрытия. Реализация данного алгоритма на языке TurboC++. Код программы, решающий поставленную задачу.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Министерство образования и науки Российской Федерации
Федеральное государственное бюджетное образовательное учреждение высшего и профессионального образования
«Магнитогорский Государственный Технический Университет
Кафедра вычислительной техники и программирования
по дисциплине: « Алгоритмы на сетях и графах »
Исполнитель студент группы АВБ-12 Картавцев Е.П.
Курсовая работа - самостоятельно выполненная работа с элементами научного исследования.
Целью моей курсовой работы является углубление знаний по дисциплине, изучить тему «Графы», а так же «Алгоритмы на сетях и графах».
Вместе с тем известно, что это NP-полная задача. Для таких задач не известно эффективных алгоритмов, а накопленный к настоящему времени опыт делает правдоподобным предположение о том, что таких алгоритмов и не существует. Тем не менее, алгоритмы для подобных задач разрабатывались и продолжают разрабатываться, и в некоторых случаях они могут быть полезны. Все эти алгоритмы в той или иной форме осуществляют перебор вариантов (число которых может быть очень большим). Далее рассмотрим один из способов такого перебора для задачи о вершинном покрытие.
В курсовой работе будет рассмотрен точный алгоритм решения задачи о вершинном покрытии, а так же нахождение минимального покрытия. Помимо алгоритма будет освещены понятия графа, его виды и вершинного покрытия.
Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками, прямоугольниками и т.д.), а связи между ними - линиями или стрелками, соединяющими элементы.
Термин «граф» неоднозначен, это легко обнаружить, сравнивая приводимые в разных книгах определения графа. Однако во всех этих определениях есть и общее. В любом случае граф состоит из двух множеств - множества вершин и множества ребер, причем для каждого ребра указанапара вершин, которые это ребро соединяет. Вершины и ребра называютсяэлементами графа[3].
Ориентированный граф (сокращённо орграф) G . Это упорядоченная пара G := (V, A), для которой выполнены следующие условия:
1. V -- это непустое множество вершин или узлов,
2. A -- это множество (упорядоченных) пар различных ребер, называемых дугами или ориентированными рёбрами.
Дуга - это упорядоченная пара вершин (v, w), где вершину v называют началом, а w - концом дуги. Можно сказать, что дуга vw ведёт от вершины v к вершине w.
Смешанный граф G. это граф, в котором некоторые рёбра могут быть ориентированными, а некоторые - неориентированными. Записывается упорядоченной тройкой G := (V, E, A), где V, E и A определены так же, как выше.
Ориентированный и неориентированный графы являются частными случаями смешанного.
Изоморфные графы. Граф G называется изоморфным графу H, если существует биекция f из множества вершин графа G в множество вершин графа H, обладающая следующим свойством: если в графе G есть ребро из вершины A в вершину B, то в графе H должно быть ребро из вершины f(A) в вершину f(B) и наоборот -- если в графе H есть ребро из вершины A в вершину B, то в графе G должно быть ребро из вершины в вершину
В случае ориентированного графа эта биекция также должна сохранять ориентацию ребра. В случае взвешенного графа биекция также должна сохранять вес ребра.
Двудольный граф.Двудольный граф (или биграф, или чётный граф) ? это граф G(V,E), такой что множество вершин V разбито на два непересекающихся подмножества V1 и V2, причём всякое ребро E инцидентно вершине из V1 и вершине из V2 (то есть соединяет вершину из V1 с вершиной из V2).
Мультиграф.Граф, в котором имеются кратные (параллельные) ребра.Мультиграф- это псевдограф без петель. Пример: пусть D=(V,X) - ориентированный граф,V={V1,V2},X={x1={V1,V2},x2={V1,V2}}. Тогда D=(V,X)-ориентированный мультиграф.
Простые графы ? не имеющие петель и кратных рёбер.
Полный граф. Простой граф, в котором каждая пара различных вершин смежна. Полный граф с n вершинами имеет n(n ? 1) / 2 рёбер и обозначается Kn. Является регулярным графом степени n ? 1 (Рис.7).
Псевдограф. Граф с кратными ребрами и петлями. Пример : пусть D=(V,X) - ориентированный граф, V={V1,V2},X={x1={V1,V2},x2={V1,V2},x3={V1,V2},x4={V2,V2}. Тогда D=(V,X) - ориентированный псевдограф.
Задача поиска кратчайшего пути на графе может быть определена для неориентированного, ориентированного или смешанного графа. Далее будет рассмотрена постановка задачи в самом простом виде для неориентированного графа. Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.
Граф представляет собой совокупность непустого множества вершин и ребер (наборов пар вершин). Две вершины на графе смежны, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин , таких что смежна с для . Такой путь называется путем длиной из вершины в ( указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).
Пусть -- ребро соединяющее две вершины: и . Дана весовая функция , которая отображает ребра на их веса, значения которых выражаются действительными числами, и неориентированный граф . Тогда кратчайшим путем из вершины в вершину будет называться путь (где и ), который имеет минимальное значение суммы Если все ребра в графе имеют единичный вес, то задача сводится к определению наименьшего количества обходимых ребер.
Существуют различные постановки задачи о кратчайшем пути:
· Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
· Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
· Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).
Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи[2]. Примеры таких задач:
1. Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теорииисследования операций[3].
2. Минимальное покрытие вершин ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути[4].
3. Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей такое, что для любого найдется путь , накрывающий его. -- множество некоторых путей в ориентированном графе G[5].
4. Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмноржества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины[6].
В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе:
· Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса[7].
· Алгоритм Беллмана -- Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
· Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
· Алгоритм Флойда -- Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа[7].
· Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
· Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение -- трассировки электрических соединений на кристаллах микросхем и на печатных платах. Так же используется для поиска кратчайшего расстояния на карте в стратегических играх.
· Поиск кратчайшего пути на основе алгоритма Килдала[8].
В работе (Черкасский и др., 1993)[9] представлено ещё несколько алгоритмов для решения этой задачи.
Задаем граф. Составляем список инцидентности. С главной программы вызываем рекурсивную функцию поиска минимального пути с наибольшей надежностью (P). Проходя по вершинам каждыйi-ый объект проверяется на допустимость. Затем внутри одной процедуры допустимая вершина включается в выборку, и с этой вершиной рекурсивно генерируются всевозможные решения и лучшее запоминается как оптимальное. После этого происходит возврат и i-уювершина удаляется из выборки. Но, прежде чем пытаться получить решения без i-ой вершины, проверим можно ли, не включив эту вершину, получить решение лучше, чем найденное оптимальное с i-ой. Если нет - то не стоит пытаться.
//---------------------------------------------------------------------------
//---------------------------------------------------------------------------
//----------------------------------------------------------------------------
void P(int v, int f, std::vector>vq)
if ((nov[v]) && (nov[vq[v][i].numb-1]) && (cost*vq[v][i].ves>OptCost))
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
if (!source.is_open()) throw sException("Source not exist!");
//----------------------------------------------------------------------------
std::vector>vq(N);
if (source.getline(temp, sizeof(temp)))
//----------------------------------------------------------------------------
//----------------------------------------------------------------------------
//while(OptX[i]!=f) {cout<Надежость сети курсовая работа. Программирование, компьютеры и кибернетика.
Курсовая работа по теме Воєнна безпека як елемент національної безпеки України
Контрольная работа по теме Проблема происхождения права
Контрольная Работа По Химии 10 Алканы
Реферат: Право в системе социального регулирования 2
Курсовая работа по теме Закон вартості: сутність і основні функції
Курсовая работа по теме Государственный бюджет: структура, значение, особенности в переходной экономике
Реферат: Культура речи и эффективность общения. Скачать бесплатно и без регистрации
Реферат: Управление производством и повышение его эффективности 3 Глава Анализ эффективности производства и путей его повышения на предприятии зао ростов-Ла
Реферат: Він критик.Він письменник-парадокс.Він Оскар Уальд
Реферат: Питание с учетом различных вероисповеданий
Реферат: Plato Republic 2 Essay Research Paper The
Доклад: Понятие заработной платы
Сочинение: Своеобразие темы любви в прозе А. И. Куприна
Реферат по теме Философия и образы будущего
Реферат: Define And Explain The Concepts Of Price
Реферат: Технология консервирования фруктов в масштабах предприятия. Скачать бесплатно и без регистрации
Сочинение На Английском Языке Про Распорядок Дня
Курсовая работа: Методика контроля знаний по русскому языку младших школьников. Скачать бесплатно и без регистрации
Сочинение Описание Госпожи Простаковой Из Комедии Недоросль
Контрольная работа по теме Влияние условий эксплуатации на экологическую безопасность автотранспортных средств
Промышленный маркетинг - Маркетинг, реклама и торговля курсовая работа
Теоретический анализ ценностных ориентаций студентов первого курса заочной формы обучения - Педагогика курсовая работа
Искусство управления и урегулирования конфликтов - Менеджмент и трудовые отношения курсовая работа