Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное государственное бюджетное образовательное учреждение высшего и профессионального образования

«Магнитогорский Государственный Технический Университет

им. Г.И.Носова»

Институт энергетики и автоматики

Кафедра вычислительной техники и программирования

Курсовая работа

по дисциплине: «Алгоритмы на сетях и графах»

на тему: «Надежность сети»

Исполнитель студент группы АВБ-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 <vcl.h>

#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<std::vector<Ver>>vq)

{

for(inti=0; i<vq[v].size();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<<e.mes<<endl;

cin.get();

return 0;

}

char temp[80];

source.getline(temp, 2);

N = atoi(temp);

cout<<N<<endl<<endl;

//----------------------------------------------------------------------------

std::vector<std::vector<Ver>>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<count; 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<N;i++) nov[i]= true;

cout<<"Input START: ";

cin>>s;

cout<<endl<<"Input FINISH: ";

cin>>f;

cout<<endl;

--s;

--f;

P(s,f,vq);

//----------------------------------------------------------------------------

system("Pause");

inti = 0;

//while(OptX[i]!=f) {cout<<OptX[i]<<" "; ++i;}

cout<<"Optimal way ("<<OptCost<<") :"<<endl;

system("Pause");

return 0;

}

//---------------------------------------------------------------------------

Решение задачи

Заключение

В курсовой работе был рассмотрен точный алгоритм решения задачи о надёжности сети. Алгоритм был реализован на языке TurboC++. В теоретической части рассмотрены понятия графа, виды графа и понятие вершинного покрытия.

сеть надежность алгоритм

Литература

1. В.Е. Торчинский, С.И. Файнштейн Структуры и алгоритмы обработки данных на ЭВМ: Учеб. пособие. Магнитогорск: ГОУ ВПО «МГТУ», 2007. 139 с.

2. Алексеев В.В., Гаврилов Г.П., Сапоженко А.А. (ред.) Теория графов. Покрытия, укладки, турниры. Сборник переводов - М. : Мир, 1974 - 224 с.

3. Алексеев В.Е., Таланов В.А. Графы. Модели вычислений. Структурыданных: Учебник. - Нижний Новгород: Изд-во ННГУ, 2005. 307 с.

Размещено на Allbest.ru