Потоки в сетях - Программирование, компьютеры и кибернетика курсовая работа
Последовательность формирования связного ациклического графа случайным образом в соответствии с заданным распределением. Вычисление потока минимальной стоимости. Генерация матрицы пропускных способностей. Реализация алгоритмов Фалкерсона, Дейкстры.
посмотреть текст работы
скачать работу можно здесь
полная информация о работе
весь список подобных работ
Нужна помощь с учёбой? Наши эксперты готовы помочь!
Нажимая на кнопку, вы соглашаетесь с
политикой обработки персональных данных
Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru=
САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Формирование связного ациклического графа
Алгоритм поиска потока минимальной стоимости
Сформировать связный ациклический граф случайным образом в соответствии с заданным распределением (Пойа-1).
Для заданных графов вычислить поток минимальной стоимости.
В качестве величины потока брать значение, равное [2/3*max], где max - максимальный поток.
Матрицы пропускных способностей и стоимости сгенерировать случайным образом.
Реализовать алгоритмы Фалкерсона, Дейкстры и Беллмана - Форда.
Пусть - сеть, и - соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами, Если и - узлы сети, то число - называется пропускной способностью дуги Пусть задана функция Дивергенцией функции в узле называется число , которое определяется следующим образом:
Функция называется потоком в сети , если:
1. то есть поток через дугу неотрицателен и не превосходит пропускной способности дуги;
2. то есть дивергенция потока равна нулю во всех вершинах, кроме источника и стока.
Число называется величиной потока f. Если то дуга называется насыщенной.
Всякий разрез определяется разбиением множества вершин V на два подмножества S и Т, так что , а в Р попадают все дуги, соединяющие S и Т. Тогда , где -- дуги от S к Т, -- дуги от Т к S.
Сумма потоков через дуги разреза Р обозначается F(P).
Сумма пропускных способностей дуг разреза Р называется пропускной способностью разреза и обозначается С(Р):
Аналогично, и суммы потоков через соответствующие части разрезов.
Для задач с потоками, граф G(V,E) должен удовлетворять условиям:
Каждой дуге поставлена в соответствие пропускная способность дуги.
Теорема Фалкерсона. Максимальный поток в сети равен минимальной пропускной способности разреза:
Ищем максимальный поток минимальной стоимости: если , то решения нет (? - величина потока, который хотим найти).
Если наоборот, то минимизируем сумму:
Модификация сети относительно данного потока:
Модифицирующая относительно данного потока сеть строится следующим образом:
( - множество модифицированных вершин)
Если (u,v) Е и , то ; при этом (только для дуг, по которым проходит поток).
; и . (Только для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети).
Для всех насыщенных дуг: ; полагают, что
Задача состоит в реализации вычисления потока минимальной стоимости для сформированного графа в соответствии с заданным распределением (Пойа-1). Вначале мной формируется связный граф в соответствии с распределением. Затем вычисляется максимальный поток, с помощью реализованного алгоритма Фалкерсона и, в конечном итоге, вычисляется поток минимальной стоимости, с помощью алгоритма Беллмана - Форда и Дейкстры.
Распределение Пойа 1 - распределение случайной величины, принимающей целые неотрицательные значения, в соответствии с формулами:
Где n>0, b>0, r>0, c - целые числа. Параметр с может быть отрицательным, однако он должен удовлетворять условию b+ r+c(n-1) > 0.
Рис. 1 Пример Распределение Пойа 1 (Вадзинский Р.Н. Справочник по теории вероятности. Санкт-Петербург., 2001. с. 88)
(Вадзинский Р.Н. Справочник по теории вероятности. Санкт-Петербург., 2001. с. 88)
Алгоритм реализует стандартный способ имитации моделирования дискретных случайных величин. Вероятность p0 = P(X=0) вычисляется по формуле (1) ( оператор (*)). Функция б(х) вычисляется по формуле б(х) = (n - 1 - x)[b + (x-1)c]/{x[r+(n-x)c]} (оператор (**)).
Алгоритм реализован с учетом того, что степень вершины графа не может быть равной 0 или n, и что сумма всех степеней графа первоначально должна быть четной. В алгоритме проводится проверка, и если х=0, вершине присваивается степень 1, а максимальная степень изначально может быть только у одной (чаще всего средней вершины).
vector Valency(vectorvertex)
int n = vertex.size(); //n - кол-во вершин
int b = 3, c = 1, key = 0, sum = 0;
for (int i = 1; i <= n; i++) //генерирование р = ро
p0 = p0*(r + (i - 1)*c) / (b + r + (i - 1)*c);
double p = p0, be = (n+1)*100./(1.05+v);
p = p* (n - 1 - x)*(b + (x - 1)*c) / (x*(r + (n - x)*c));
if (!key) // чтобы был один максимум
Рис. 3 График функции вероятности распределения Пойа 1 для 100 вершин.
Формирование связного ациклического графа в соответствии с распределением Пойа 1
Граф называется связным, если для любой пары различных вершин этого графа существует цепь, соединяющая эти вершины. Циклом называют цепь, в которой первая и последняя вершины совпадают. Соответственно ацикличный граф тот, который не содержит циклов.
Функцией FindMax() выбирается вершина с наибольшей степенью на данный момент из массива степеней вершин (если степени равны, то берется та, чей номер меньше). Эта вершина вычеркивается из списка возможных связей. Из оставшихся вершин, не связанных еще с данной, функцией FindMax() выбирается вершина с максимальной степенью (если степени равны, то берется та, чей номер больше). Далее между собой сравниваются номера, выбранных для связи вершин, чей номер больше - от той вершины и будет исходить дуга. После каждой связи степень соединенных вершин уменьшается на 1. Алгоритм повторяется, до тех пор, пока все степени вершин не обнулятся.
Данный алгоритм создает граф с кратными ребрами, однако потом, при построении матрицы смежности, все кратные ребра исключаются.
Эта функция находит номер вершины с максимальной степенью, в массиве степеней вершин. При этом, можно контролировать поиск максимума: можно брать минимальный или максимальный номер если есть несколько вершин с максимальной степенью.
int FindMax (vectorvertex, bool MorD)
if (vertex.at(k) == vertex.at(j) && !MorD)
Реализация алгоритма построения связного ацикличного графа:
cout << endl << "Введите количество вершин (число должно быть целым, из промежутка [2;200]): ";
cout << endl << "\tНеправильно задано количество вершин! Введенное число меньше 2!"
<< "\n\t\t\t\tПопробуйте еще раз!\2\n\n";
cout << endl << "\tНеправильно задано количество вершин! Введенное число больше 200!"
<< "\n\t\t\t\tПопробуйте еще раз!\2\n\n";
for (int i = 0; i < graph.at(indexMax).size(); i++){
for (int j = 0; j < temp.size(); j++)
if (j == graph[indexMax][i] || j == -graph[indexMax][i])
for (int i = 0; i < temp.size(); i++) //проверка, не пустой ли темп
if (tS == temp.size()) //если пустой то делаем кратные связи
graph.at(indexMax).push_back(indexDn);graph.at(indexDn).push_back(-indexMax);
vector>graphMatr(n, vector(n));
for (int i = 0; i < graph.size(); i++) //легко переделать в матрицу смежности
for (int j = 0; j < graph.at(i).size(); j++)
Алгоритм поиска потока минимальной стоимости
Для нахождения минимальной стоимости заданного потока следует воспользоваться следующим алгоритмом:
Находим максимально возможный поток по теореме Фалкерсона, за исходный поток берем 2/3 максимального потока;
Находим минимальный путь из истока в сток сети в матрице стоимостей с помощью алгоритма Беллмана-Форда, в зависимости от чисел в матрице весов;
Пропускаем по найденному пути максимальный возможный поток для этого пути;
Из ребер матрицы пропускных способностей вычитаем величину потока, то есть устанавливаем остаточную пропускную способность этих ребер;
Для каждого обнуленного ребра в матрице пропускных способностей обнуляем ребро в матрице стоимостей;
Если текущий пропущенный поток меньше заданного переходим к шагу 1.
void pot_min_st(vector> propSpos, vector> price, vector s, vector t, int max)
int n = propSpos.size(), maxB = max;;
vector> rezult(n, vector(n));
vector> priceEtalon(price);
minPath = Deykstra(price, s[0], t[0]);
if (min(minPath, Deykstra(price, s[i], t[j])) != minPath)
minPath = Deykstra(price, s[i], t[j]);
minP = MakePath(price, minPath, s[ti], t[tj]);
temp = propSpos[*minP.begin()][*++minP.begin()];
for (list::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)
if (min(propSpos[*it][*jt], temp) != temp)
cout << endl << "Пускаем поток (" << temp << ")" << " по пути ";
for (it = minP.begin(); it != minP.end(); it++, ti++)
cout << ". Стоимость данного потока ";
for (list::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)
if (!propSpos[*jt][*it] && propSpos[*it][*jt])
price[*jt][*it] = -price[*it][*jt];
if (!propSpos[*it][*jt] && !rezult[*jt][*it])
cout << "Оставшийся поток равен " << max - temp << endl;
Save(price, "Промежуточная матрица стоимости");
Save(propSpos, "Промежуточная матрица пропускной способности");
rez += rezult[i][j] * priceEtalon[i][j];
cout << endl << "Минимальная стоимость потока " << maxB << " равна " << rez;
cout << endl << "Все промежуточные матрицы стоимости и потоков сохранены в файл graph.txt";
Print(rezult, "\n\t\tНовая матрица потоков");
cout << endl << "Новая матрица потоков сохранена в файл graph.txt\n" << endl;
Алгоритм Форда -- Фалкерсона решает задачу нахождения максимального потока в транспортной сети.
Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v)=0 для всех u,v ? V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.
Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.
В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.
Пускаем через найденный путь (он называется увеличивающим путём) максимально возможный поток:
На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .
Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему -- уменьшаем на .
Модифицируем остаточную сеть. Для всех рёбер на найденном пути, а также для противоположных им рёбер, вычисляем новую пропускную способность. Если она стала ненулевой, добавляем ребро к остаточной сети, а если обнулилась, стираем его.
Важно, что алгоритм не конкретизирует, какой именно путь мы ищем на шаге 2 или как мы это делаем. По этой причине алгоритм гарантированно сходится только для целых пропускных способностей, но даже для них при больших значениях пропускных способностей он может работать очень долго.
bool Svyazn(vector>& matr){
if (i != k && i != j && temp[j][i] != 0 && temp[i][k] != 0 && (min(temp[j][k], (temp[j][i] + temp[i][k])) != temp[j][k]))
temp[j][k] = temp[j][i] + temp[i][k];
int Falkerson(vector> propSpos, vector s, vector t){
int n = propSpos.size(), max = 0, ti = 0, tj = 0, minPath, temp;
vector> rezult(n, vector(n));
minPath = Bellman(propSpos, s[0], t[0]);//
if (min(minPath, Bellman(propSpos, s[i], t[j])) != minPath)//
minPath = Bellman(propSpos, s[i], t[j]);//
minP = MakePath(propSpos, minPath, s[ti], t[tj]);//
temp = propSpos[*minP.begin()][*++minP.begin()];
for (list::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)
if (min(propSpos[*it][*jt], temp) != temp)
for (list::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)
if (!propSpos[*jt][*it] && propSpos[*it][*jt])
if (!propSpos[*it][*jt] && !rezult[*jt][*it])
Алгоритм Беллмана-Форда -- алгоритм поиска кратчайшего пути во взвешенном графе. Он имеет сложность О(p*q) - это худший случай и сложность О(р) в лучшем случае. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом, но его ограничением является то, что на входе должен быть граф без циклов с отрицательным весом. В нашем случае на вход функции идет порядковый номер вершин, между которыми будет происходить поиск кратчайшего пути.
В отличие от алгоритма Дейкстры в этом алгоритме нет постоянных меток, но есть очередь. Сначала берется стартовая вершина и заносится в очередь. Расстояние до остальных вершин предполагается равным бесконечности (то есть константа LONG_MAX в нашей программе).
Шаг алгоритма. Удаляем вершину из начала очереди. Для каждой соседней вершины корректируем метку по формуле из шага алгоритма Дейкстры. Если при этом новое значение меньше старого, то корректируем очередь, иначе продолжаем перебор вершин и корректировку временных меток.
Корректировка очереди. Если раньше вершина не была в очереди, то ее ставим в конец, а если была или находится в данный момент, то ставим ее в начало очереди.
Алгоритм работает, пока очередь не станет пустой, т.е. пока из очереди можно взять вершину.
int Bellman(vector>& matr, int start, int end)
vector> temp(n, vector(2));
for (int i = 0; i < matr.size(); i++)
if (min(temp[i][0], min(temp[i][0], temp[t][0] + matr[t][i])) != temp[i][0])
temp[i][0] = temp[t][0] + matr[t][i];
queue.push_back(i);//Иначе - в конец
Алгоритм Дейкстры находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса (из-за этого перед началом работы алгоритма, все отрицательные веса в матрице берутся по модулю). Сложность - O(n).
Работу алгоритма можно разделить на два этапа:
Первый этап: Присвоение вершинам начальных меток.
Каждой вершине сопоставим метку - расстояние от этой вершины до начальной вершины. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.
Метка начальной вершины полагается равной 0, метки остальных вершин - бесконечности (роль бесконечности выполняет константа LONG_MAX, равная 2147483647L). Бесконечность значит, что расстояния от начальной вершины до других пока неизвестны. Все вершины графа, кроме начальной, помечаются как не посещённые.
Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Для каждой соседней вершины u, кроме посещённых, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с соседней вершиной. Если полученное значение длины меньше значения метки соседней вершины, заменим значение метки полученным значением длины. Рассмотрев все соседние вершины, пометим вершину u как посещенную и повторим шаг алгоритма. В нашем случае нужно найти кратчайшее расстояние между заданными вершинами, поэтому на входе две вершины, а не одна.
Второй этап: Построение кратчайшего пути.
Среди вершин, непосредственно предшествующих текущей, с постоянной меткой, ищем вершину, удовлетворяющую соотношению:
где метка вершины, вес ребра, текущая вершина, которая добавляется в маршрут.
int Deykstra(vector>& weight, int start, int end)
vector> temp (n, vector(2));
temp[start][1] = 1;//делаем постоянную метку в начале
void Work(vector>& matr, vector>& temp, int start, int end)
int m = LONG_MAX;if (temp[end][1] != 0) return;
for (int i = 0; i < matr.size(); i++)
temp[i][0] = min(temp[i][0], temp[st][0] + matr[st][i]);
for (int k = 0; k < temp.size(); k++)
if (temp[k][1] == 0 && temp[k][0] == min(temp[k][0], m))
void Path(vector>& matr, int lenght, int start, int end, list& path){//рекурсивное заполнение пути (1 шаг - одна вершина)
if (start==i&&matr[i][end]==lenght)return;
if((matr[i][end]!=0)&&(matr[i][end]!=lenght)&&(Bellman(tmatr,start,i)==lenght-matr[i][end]))
Path(tmatr ,lenght, start, end, path);
list MakePath(vector>& matr, int lenght, int start, int end)
if (start==end) return list(0);
Path(matr,lenght, start, end, path);
Пример работы программы будет приводиться на связном ориентированном графе, сформированным по распределению Пойа-1.
Рис1. Пример работы программы: вывод распределения и матрицы получившегося графа.
Рис2. Пример работы программы: вывод матрицы стоимости вершин, полученной случайным образом
Рис3. Пример работы программы: вывод матрицы пропускной способности, полученной случайным образом
Рис4. Пример работы программы: вывод результата работы алгоритма Фалкерсона.
Рис5. Пример работы программы: вычисление потока минимальной стоимости.
Рис6. Пример работы программы: вывод матрицы потоков, полученной после пропускания потока заданной стоимости.
В данной работе был сформирован связный ациклический граф в соответствии с распределением Пойа-1. Матрицы стоимости и пропускной способности реализованы путем замены единиц в матрице смежности на числа, полученные случайным образом. Для полученного графа был найден максимальный поток с помощью теоремы Форда-Фалкерсона. Максимальный поток ищется при помощи алгоритма Беллмана - Форда, что отличается от классического метода, использующего поиск в глубину.
Далее был реализован поиск минимальной стоимости для заданного потока в сети. Такой поиск минимальной стоимости актуален для решения многих задач на логистику, например для решения задач, связанных с транспортной сетью.
В качестве величины потока брали 2/3 от максимального потока. Поиск минимальных по стоимости путей производился с помощью алгоритмов Беллмана - Форда и Дейкстры. Алгоритм Дейкстры лучше использовать при условии, что граф не имеет отрицательные веса, так как он работает быстрее, чем алгоритм Беллмана-Форда. Для более общего решения нужно использовать алгоритм Беллмана-Форда. С каждым шагом происходит модификация сети с учетом пропустившегося потока. Модификация заключается в изменении матриц стоимостей и пропускных способностей после каждой итерации.
В результате работы программы мы получаем матрицу потоков, из которой видно по какому ребру какой поток прошел. Общая сумма потока вычисляется с помощью матрицы потоков и первоначальной матрицы стоимости и также выводится на экран.
В графе может быть несколько истоков и стоков, а нужно по одному, поэтому используются фиктивные исток и сток, объединяющие в себя реальные стоки и истоки.
Так как поиск алгоритм поиска потока минимальной стоимости получился как комплекс алгоритмов с уже известными сложностями, то мы можем приблизительно оценить и его сложность. Его приблизительная точность будет равна в худшем случае и в лучшем.
Чтобы модифицировать эту программу, можно добавить визуализацию графа и каждого изменения матриц стоимости и пропускной способности, прослеживая распределения потоков. В программе мы пропускаем 2/3 от максимального потока, а можно предоставить выбор пропускаемого потока пользователю, не допуская возможность пустить поток больше максимального.
Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. - СПБ.: Питер, 2009. - 384 с.
Вадзинский Р.Н. Справочник по вероятностным распределениям. - СПб.: Наука, 2001. - 295 с.
Использование понятий из теории графов при разработке сетей и алгоритмов маршрутизации. Построение матрицы смежности и взвешенного ориентировочного графа. Результаты работы алгоритмов Дейкстры и Беллмана-Форда. Протоколы обмена маршрутной информацией. курсовая работа [334,1 K], добавлен 20.01.2013
Теоретическое исследование вопроса и практическое применение. Общие сведения о графах. Алгоритм Дейкстры. Особенности работы в среде. Программная реализация. Описание алгоритма и структуры программы. Описание программных средств. Текст программы. курсовая работа [1,0 M], добавлен 27.11.2007
Корректность определения кратчайших путей в графе и рёбра отрицательной длины. Анализ алгоритмов Дейкстры, Беллмана-Форда, Флойда-Уоршелла. Вычисление кратчайших расстояний между всеми парами вершин графа. Топологическая сортировка ориентированного графа. презентация [449,3 K], добавлен 19.10.2014
Реализация алгоритмов Краскала и Прима для построения минимального остовного дерева взвешенного связного неориентированного графа. Анализ трудоемкости алгоритмов, их псевдокоды и тестирование. Применение алгоритма Краскала на практике в работе авиалиний. курсовая работа [142,0 K], добавлен 25.12.2012
Реализация программы для решения матричных игр. Задание матрицы игры вручную и случайным образом, нахождение оптимальных стратегий игроков итерационным и методом чистых стратегий. Проектирование и листинг программного кода, сохранение матрицы игры. контрольная работа [716,7 K], добавлен 11.06.2011
Программа формирования матрицы смежности по заданному списку окрестностей вершин ориентированного графа. Формирование динамического списка дуг ориентированного графа по заданному списку окрестностей. Анализ временной и емкостной сложности алгоритма. курсовая работа [8,1 M], добавлен 07.09.2012
Определение понятия квадротомического дерева. Рассмотрение основных примеров квадродерева, его достоинств и недостатков. Визуализация квадротомированного изображения. Создание программы разбора бинарной, заполненной случайным образом, матрицы N на M. курсовая работа [392,3 K], добавлен 09.08.2015
Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д. PPT, PPTX и PDF-файлы представлены только в архивах. Рекомендуем скачать работу .
© 2000 — 2021
Потоки в сетях курсовая работа. Программирование, компьютеры и кибернетика.
Реферат по теме Местное управление в России в 19 веке
Реферат На Тему История Развития Анатомии
Отчет По Логопедической Педагогической Практике В Доу
Курсовая работа по теме История развития бухгалтерского учета в России
Курсовая работа по теме Волоконно-оптическая линия передачи
Контрольная работа: Мировые рынки труда
Дипломная работа по теме Фрахтование трампового тоннажа
Реферат по теме Концепция трансакционных затрат, природа внутренней и внешней интеграции фирмы: Рональд Коуз и его последователи
Реферат: Представители греческой философской мысли. Скачать бесплатно и без регистрации
Реферат: Развитие английского костюма в период эпохи Возрождения
Наружная Реклама Для Турфирмы Курсовая Работа
Переводная Контрольная Работа 2 Класс Петерсон
Курсовая работа по теме Активные операции банков
Реферат по теме Острый перитонит при гинекологических заболеваниях
Сочинение Описание По Картине Золотая Осень Поленова
Контрольная работа по теме Взаимосвязь технико-экономических показателей работы предприятия и фондоотдачи
Дипломная работа: Модернизация лабораторных стендов и наладка новых лабораторных комплексов лаборатории измерительной
Требования К Реферату В Школе
Реферат На Тему Эмфизема Легких
Курсовая Работа На Тему Понятие Брака По Семейному Праву Украины
Особенности предвыборной борьбы непарламентских партий - Политология курсовая работа
Конфликты между кредиторами и гражданами-должниками, связанные с процедурой банкротства физических лиц - Государство и право курсовая работа
Диеты для больных животных - Медицина презентация