Надежость сети
Вместе с тем известно, что это NP-полная задача. Для таких задач не известно эффективных алгоритмов, а накопленный к настоящему времени опыт делает правдоподобным предположение о том, что таких алгоритмов и не существует. Тем не менее, алгоритмы для подобных задач разрабатывались и продолжают разрабатываться, и в некоторых случаях они могут быть полезны. Все эти алгоритмы в той или иной форме… Читать ещё >
Надежость сети (реферат, курсовая, диплом, контрольная)
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего и профессионального образования
«Магнитогорский Государственный Технический Университет им. Г.И.Носова»
Институт энергетики и автоматики Кафедра вычислительной техники и программирования
Курсовая работа
по дисциплине: «Алгоритмы на сетях и графах»
на тему: «Надежность сети»
Исполнитель студент группы АВБ-12 Картавцев Е.П.
Проверил Файнштейн С.И.
Магнитогорск 2014
- Введение
- 1. Теоретическая часть
- 1.1 Понятия графа
- 1.2 Виды графов
- 1.3 Кратчайший путь в графе
- 1.4 Задача о кратчайшем пути с учетом дополнительных ограничений
- 1.5 Алгоритмы
- 2. Практическая часть
- 2.1 Постановка задачи
- 2.2 Алгоритм решения
- 2.3 Код программы
- Заключение
- Литература
- Введение
Курсовая работа — самостоятельно выполненная работа с элементами научного исследования.
Целью моей курсовой работы является углубление знаний по дисциплине, изучить тему «Графы», а так же «Алгоритмы на сетях и графах».
Вместе с тем известно, что это NP-полная задача. Для таких задач не известно эффективных алгоритмов, а накопленный к настоящему времени опыт делает правдоподобным предположение о том, что таких алгоритмов и не существует. Тем не менее, алгоритмы для подобных задач разрабатывались и продолжают разрабатываться, и в некоторых случаях они могут быть полезны. Все эти алгоритмы в той или иной форме осуществляют перебор вариантов (число которых может быть очень большим). Далее рассмотрим один из способов такого перебора для задачи о вершинном покрытие.
В курсовой работе будет рассмотрен точный алгоритм решения задачи о вершинном покрытии, а так же нахождение минимального покрытия. Помимо алгоритма будет освещены понятия графа, его виды и вершинного покрытия.
1. Теоретическая часть
1.1 Понятия графа
Для описания строения различных систем, состоящих из связанных между собой элементов, часто используют графические схемы, изображая элементы точками (кружками, прямоугольниками и т. д.), а связи между ними — линиями или стрелками, соединяющими элементы.
Термин «граф» неоднозначен, это легко обнаружить, сравнивая приводимые в разных книгах определения графа. Однако во всех этих определениях есть и общее. В любом случае граф состоит из двух множеств — множества вершин и множества ребер, причем для каждого ребра указанапара вершин, которые это ребро соединяет. Вершины и ребра называютсяэлементами графа[3].
1.2 Виды графов
Выделяют следующие виды графов.
Ориентированный граф (сокращённо орграф) 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) — ориентированный псевдограф.
1.3 Кратчайший путь в графе
Задача поиска кратчайшего пути на графе может быть определена для неориентированного, ориентированного или смешанного графа. Далее будет рассмотрена постановка задачи в самом простом виде для неориентированного графа. Для смешанного и ориентированного графа дополнительно должны учитываться направления ребер.
Граф представляет собой совокупность непустого множества вершин и ребер (наборов пар вершин). Две вершины на графе смежны, если они соединяются общим ребром. Путь в неориентированном графе представляет собой последовательность вершин, таких что смежна с для. Такой путь называется путем длиной из вершины в (указывает на номер вершины пути и не имеет никакого отношения к нумерации вершин на графе).
Пусть — ребро соединяющее две вершины: и. Дана весовая функция, которая отображает ребра на их веса, значения которых выражаются действительными числами, и неориентированный граф. Тогда кратчайшим путем из вершины в вершину будет называться путь (где и), который имеет минимальное значение суммы Если все ребра в графе имеют единичный вес, то задача сводится к определению наименьшего количества обходимых ребер.
Существуют различные постановки задачи о кратчайшем пути:
· Задача о кратчайшем пути в заданный пункт назначения. Требуется найти кратчайший путь в заданную вершину назначения t, который начинается в каждой из вершин графа (кроме t). Поменяв направление каждого принадлежащего графу ребра, эту задачу можно свести к задаче о единой исходной вершине (в которой осуществляется поиск кратчайшего пути из заданной вершины во все остальные).
· Задача о кратчайшем пути между заданной парой вершин. Требуется найти кратчайший путь из заданной вершины u в заданную вершину v.
· Задача о кратчайшем пути между всеми парами вершин. Требуется найти кратчайший путь из каждой вершины u в каждую вершину v. Эту задачу тоже можно решить с помощью алгоритма, предназначенного для решения задачи об одной исходной вершине, однако обычно она решается быстрее.
В различных постановках задачи, роль длины ребра могут играть не только сами длины, но и время, стоимость, расходы, объем затрачиваемых ресурсов (материальных, финансовых, топливно-энергетических и т. п.) или другие характеристики, связанные с прохождением каждого ребра. Таким образом, задача находит практическое применение в большом количестве областей (информатика, экономика, география и др.).
1.4 Задача о кратчайшем пути с учетом дополнительных ограничений
Задача о кратчайшем пути очень часто встречается в ситуации, когда необходимо учитывать дополнительные ограничения. Наличие их может значительно повысить сложность задачи[2]. Примеры таких задач:
1. Кратчайший путь, проходящий через заданное множество вершин. Можно рассматривать два ограничения: кратчайший путь должен проходить через выделенное множество вершин, и кратчайший путь должен содержать как можно меньше невыделенных вершин. Первое из них хорошо известна в теорииисследования операций[3].
2. Минимальное покрытие вершин ориентированного графа путями. Осуществляется поиск минимального по числу путей покрытия графа, а именно подмножества всех s-t путей, таких что, каждая вершина ориентированного графа принадлежит хотя бы одному такому пути[4].
3. Задача о требуемых путях. Требуется найти минимальное по мощности множество s-t путей такое, что для любого найдется путь, накрывающий его. — множество некоторых путей в ориентированном графе G[5].
4. Минимальное покрытие дуг ориентированного графа путями. Задача состоит в отыскании минимального по числу путей подмноржества всех путей, такого, что каждая дуга принадлежит хотя бы одному такому пути. При этом возможно дополнительное требование о том, чтобы все пути исходили из одной вершины[6].
1.5 Алгоритмы
В связи с тем, что существует множество различных постановок данной задачи, есть наиболее популярные алгоритмы для решения задачи поиска кратчайшего пути на графе:
· Алгоритм Дейкстры находит кратчайший путь от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса[7].
· Алгоритм Беллмана — Форда находит кратчайшие пути от одной вершины графа до всех остальных во взвешенном графе. Вес ребер может быть отрицательным.
· Алгоритм поиска A* находит маршрут с наименьшей стоимостью от одной вершины (начальной) к другой (целевой, конечной), используя алгоритм поиска по первому наилучшему совпадению на графе.
· Алгоритм Флойда — Уоршелла находит кратчайшие пути между всеми вершинами взвешенного ориентированного графа[7].
· Алгоритм Джонсона находит кратчайшие пути между всеми парами вершин взвешенного ориентированного графа.
· Алгоритм Ли (волновой алгоритм) основан на методе поиска в ширину. Находит путь между вершинами s и t графа (s не совпадает с t), содержащий минимальное количество промежуточных вершин (ребер). Основное применение — трассировки электрических соединений на кристаллах микросхем и на печатных платах. Так же используется для поиска кратчайшего расстояния на карте в стратегических играх.
· Поиск кратчайшего пути на основе алгоритма Килдала[8].
В работе (Черкасский и др., 1993)[9] представлено ещё несколько алгоритмов для решения этой задачи.
2. Практическая часть
2.1 Постановка задачи
УСЛОВИЕ. Заданы граф G=(V, E), подмножество V' э V, для каждого eэ E рациональное число p (e), 0 — вероятность исправности, положительное рациональное число q.
ВОПРОС. Верно ли, что с вероятностью, не меньшей q, любые две вершины из V соединены хотя бы одним путем, не содержащим неисправных рёбер?
2.2 Алгоритм решения
Задаем граф. Составляем список инцидентности. С главной программы вызываем рекурсивную функцию поиска минимального пути с наибольшей надежностью (P). Проходя по вершинам каждыйi-ый объект проверяется на допустимость. Затем внутри одной процедуры допустимая вершина включается в выборку, и с этой вершиной рекурсивно генерируются всевозможные решения и лучшее запоминается как оптимальное. После этого происходит возврат и i-уювершина удаляется из выборки. Но, прежде чем пытаться получить решения без i-ой вершины, проверим можно ли, не включив эту вершину, получить решение лучше, чем найденное оптимальное с i-ой. Если нет — то не стоит пытаться.
2.3 Код программы
Код программы, решающий поставленную задачу представлен ниже. На рисунке 2 показан результат выполнения программы.
//—————————————————————————————————————;
#include
#include «File1.h»
#pragma hdrstop
//—————————————————————————————————————;
externint N = 0;
externbool *nov = NULL;
externint *OptX = NULL;
externint *X = NULL;
extern float OptCost = 0;
extern float cost = 1;
#pragma argsused
//—————————————————————————————————————-;
void P (int v, int f, std: vector>vq)
{
for (inti=0; i
{
if (v == f)
{
OptX = X;
OptCost = cost;
return;
}
else
if ((nov[v]) && (nov[vq[v][i]. numb-1]) && (cost*vq[v][i]. ves>OptCost))
{
X[v+1] = vq[v][i]. numb;
nov[v] = false;
cost = cost*vq[v][i]. ves;
P (vq[v][i].numb — 1, f, vq);
/**************************/
nov[v] = true;
cost = cost/vq[v][i]. ves;
}
}
}
//—————————————————————————————————————-;
int main (intargc, char* argv[])
{
//—————————————————————————————————————-;
Vertmp;
ifstream source;
source.open («Input.txt»);
try
{
if (!source.is_open ()) throw sException («Source not exist!»);
}
catch (sException e)
{
cout<
cin.get ();
return 0;
}
char temp[80];
source.getline (temp, 2);
N = atoi (temp);
cout<
//—————————————————————————————————————-;
std:vector>vq (N);
while (!source.eof ())
{
int number, count;
if (source.getline (temp, sizeof (temp)))
{
char *tok;
tok = strtok (temp, ««);
number = StrToInt (tok);
—number;
tok = strtok (NULL, ««);
count = StrToInt (tok);
for (inti=0; i
{
tok = strtok (NULL, ««);
tmp.numb = StrToInt (tok);
tok = strtok (NULL, ««);
tmp.ves = StrToFloat (tok);
vq[number]. push_back (tmp);
}
}
}
source.close ();
//—————————————————————————————————————-;
nov = new bool[N];
X = new int[N];
OptX = new int[N];
int s = 0; int f = 0;
for (inti=0;i
cout<<" Input START: «;
cin>>s;
cout<<" Input FINISH: «;
cin>>f;
cout<
—s;
—f;
P (s, f, vq);
//—————————————————————————————————————-;
system («Pause»);
inti = 0;
//while (OptX[i]≠f) {cout<<<" «; ++i;}
cout<<" Optimal way («<<») :" <
system («Pause»);
return 0;
}
//—————————————————————————————————————;
Решение задачи
Заключение
В курсовой работе был рассмотрен точный алгоритм решения задачи о надёжности сети. Алгоритм был реализован на языке TurboC++. В теоретической части рассмотрены понятия графа, виды графа и понятие вершинного покрытия.
сеть надежность алгоритм
1. В. Е. Торчинский, С. И. Файнштейн Структуры и алгоритмы обработки данных на ЭВМ: Учеб. пособие. Магнитогорск: ГОУ ВПО «МГТУ», 2007. 139 с.
2. Алексеев В. В., Гаврилов Г. П., Сапоженко А. А. (ред.) Теория графов. Покрытия, укладки, турниры. Сборник переводов — М.: Мир, 1974 — 224 с.
3. Алексеев В. Е., Таланов В. А. Графы. Модели вычислений. Структурыданных: Учебник. — Нижний Новгород: Изд-во ННГУ, 2005. 307 с.