Потоки в сетях

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

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

САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ ПОЛИТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ

ИПММ

Кафедра Телематики при ЦНИИ РТК

Курсовая работа по Теории графов

по теме «Потоки в сетях»



Содержание

Задание

Описание математической модели

Особенности реализации

Распределение Пойа-1

Формирование связного ациклического графа

Алгоритм поиска потока минимальной стоимости

Алгоритм Фалкерсона

Алгоритм Беллмана - Форда

Алгоритм Дейкстры

Результаты работы программы

Заключение

Список использованной литературы



Задание

Сформировать связный ациклический граф случайным образом в соответствии с заданным распределением (Пойа-1).

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

В качестве величины потока брать значение, равное [2/3*max], где max - максимальный поток.

Матрицы пропускных способностей и стоимости сгенерировать случайным образом.

Реализовать алгоритмы Фалкерсона, Дейкстры и Беллмана - Форда.



Описание математической модели

поток граф алгоритм матрица

Пусть - сеть, и - соответственно источник и сток сети. Дуги сети нагружены неотрицательными вещественными числами, Если и - узлы сети, то число - называется пропускной способностью дуги Пусть задана функция Дивергенцией функции в узле называется число , которое определяется следующим образом:

Функция  называется потоком в сети , если:

1. то есть поток через дугу неотрицателен и не превосходит пропускной способности дуги;

2.  то есть дивергенция потока равна нулю во всех вершинах, кроме источника и стока.

Число называется величиной потока f. Если то дуга называется насыщенной.

Пусть paзpeз, .

Всякий разрез определяется разбиением множества вершин V на два подмножества S и Т, так что , а в Р попадают все дуги, соединяющие S и Т. Тогда , где -- дуги от S к Т, -- дуги от Т к S.

Сумма потоков через дуги разреза Р обозначается F(P).

Сумма пропускных способностей дуг разреза Р называется пропускной способностью разреза и обозначается С(Р):



Аналогично, и суммы потоков через соответствующие части разрезов.

Для задач с потоками, граф G(V,E) должен удовлетворять условиям:

G - связный граф без петель.

Существует один исток.

Существует один сток.

Каждой дуге поставлена в соответствие пропускная способность дуги.

Теорема Фалкерсона. Максимальный поток в сети равен минимальной пропускной способности разреза:

Ищем максимальный поток минимальной стоимости: если , то решения нет (? - величина потока, который хотим найти).

Если наоборот, то минимизируем сумму:

Модификация сети относительно данного потока:

Модифицирующая относительно данного потока сеть строится следующим образом:

( - множество модифицированных вершин)

(- множество фиктивных дуг)

Если (u,v) Е и , то ; при этом (только для дуг, по которым проходит поток).

; и . (Только для всех ненасыщенных дуг, где нет противоположного потока, в том числе и для ненасыщенных дуг с потоком, относительно которого происходит модификация сети).

Для всех насыщенных дуг: ; полагают, что



Особенности реализации

Задача состоит в реализации вычисления потока минимальной стоимости для сформированного графа в соответствии с заданным распределением (Пойа-1). Вначале мной формируется связный граф в соответствии с распределением. Затем вычисляется максимальный поток, с помощью реализованного алгоритма Фалкерсона и, в конечном итоге, вычисляется поток минимальной стоимости, с помощью алгоритма Беллмана - Форда и Дейкстры.

Распределение Пойа-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<int> Valency(vector<int>vertex)

{

int n = vertex.size(); //n - кол-во вершин

int b = 3, c = 1, key = 0, sum = 0;

double r = 20, p0 = 1;

for (int i = 1; i <= n; i++) //генерирование р = ро

p0 = p0*(r + (i - 1)*c) / (b + r + (i - 1)*c);

for (int v = 0; v < n; v++)

{

double p = p0, be = (n+1)*100./(1.05+v);

int x = 0, rafiky = be;

r = (rand()%rafiky)/100.;

r = r - p;

while (r > 0)

{

if (x < n - 1)

{

x++;

p = p* (n - 1 - x)*(b + (x - 1)*c) / (x*(r + (n - x)*c));

r = r - p;

}

else

{

vertex[v] = (n-2);break;

}

}

if (x == n-1)

{

if (!key) // чтобы был один максимум

{

vertex[v] = n-2;

key++;

}

}

if (x == 0)

vertex[v] = 1;

else if(x != 0 || x < n-2)

vertex[v] = x;

// проверка на четность

sum += vertex[v];

}

while(sum & 1)

{

sum -= vertex[n/2];

if(!key)

{

vertex[n/2] = n-1;

sum += vertex[n/2];

key++;

}

else

{

vertex[n/2]=rand()%(n-2)+1;

sum += vertex[n/2];

}

}

return vertex;}

Рис. 3 График функции вероятности распределения Пойа 1 для 100 вершин.

Формирование связного ациклического графа в соответствии с распределением Пойа 1

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

Принцип построения графа:

Граф строится ориентированный.

Функцией FindMax() выбирается вершина с наибольшей степенью на данный момент из массива степеней вершин (если степени равны, то берется та, чей номер меньше). Эта вершина вычеркивается из списка возможных связей. Из оставшихся вершин, не связанных еще с данной, функцией FindMax() выбирается вершина с максимальной степенью (если степени равны, то берется та, чей номер больше). Далее между собой сравниваются номера, выбранных для связи вершин, чей номер больше - от той вершины и будет исходить дуга. После каждой связи степень соединенных вершин уменьшается на 1. Алгоритм повторяется, до тех пор, пока все степени вершин не обнулятся.

Данный алгоритм создает граф с кратными ребрами, однако потом, при построении матрицы смежности, все кратные ребра исключаются.

Функция FindMax()

Эта функция находит номер вершины с максимальной степенью, в массиве степеней вершин. При этом, можно контролировать поиск максимума: можно брать минимальный или максимальный номер если есть несколько вершин с максимальной степенью.

int FindMax (vector<int>vertex, bool MorD)

{

int k = 0;

int n = vertex.size();

if (!vertex.at(k)) k++;

for (int j = 0; j < n; j++)

{

if(vertex.at(j) && k != j)

{

if(vertex.at(k) < vertex.at(j))

k = j;

if (vertex.at(k) == vertex.at(j) && !MorD)

k = j;

}

}

return k;

}

Реализация алгоритма построения связного ацикличного графа:

vector<vector<int>> MakeGraph()

{

int n = 1;

cout << endl << "Введите количество вершин (число должно быть целым, из промежутка [2;200]): ";

while (n < 2 || n > 200)

{

n = Check(n);

if (n < 2)

cout << endl << "\tНеправильно задано количество вершин! Введенное число меньше 2!"

<< "\n\t\t\t\tПопробуйте еще раз!\2\n\n";

if(n > 200)

cout << endl << "\tНеправильно задано количество вершин! Введенное число больше 200!"

<< "\n\t\t\t\tПопробуйте еще раз!\2\n\n";

}

vector<int>vertex(n);

vertex = Valency(vertex);

vector<vector<int>>graph(n);

int indexMax = FindMax(vertex, 1);

cnt=0;

while(vertex.at(indexMax) > 0)

{

vector<int>temp = vertex;

temp[indexMax] = 0;

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])

{

temp[j] = 0;

break;

}

}

}

int tS = 0;

for (int i = 0; i < temp.size(); i++) //проверка, не пустой ли темп

{

if (temp[i] == 0)

tS++;

}

if (tS == temp.size()) //если пустой то делаем кратные связи

{

temp = vertex;

temp[indexMax] = 0;

}

int indexDn = FindMax(temp, 0);

if (indexMax > indexDn)

swap (indexMax, indexDn);

graph.at(indexMax).push_back(indexDn);graph.at(indexDn).push_back(-indexMax);

vertex.at(indexMax)--;

vertex.at(indexDn)--;

indexMax = FindMax(vertex, 1);}

vector<vector<int>>graphMatr(n, vector<int>(n));

for (int i = 0; i < graph.size(); i++) //легко переделать в матрицу смежности

{

for (int j = 0; j < graph.at(i).size(); j++)

{

int l = rand()%2;

if (graph[i][j] > 0)

graphMatr[i][graph[i][j]] = 1;

}

int h = 0;

for (int e = 0; e < i; e++)

if (graphMatr[e][i])

{

h=1;

break;

}

if (i > 0 && !h)

{

h = rand()%i;

graphMatr[h][i] = rand() % 19 - 8;

}

}

return graphMatr;

}

Алгоритм поиска потока минимальной стоимости

Для нахождения минимальной стоимости заданного потока следует воспользоваться следующим алгоритмом:

Находим максимально возможный поток по теореме Фалкерсона, за исходный поток берем 2/3 максимального потока;

Находим минимальный путь из истока в сток сети в матрице стоимостей с помощью алгоритма Беллмана-Форда, в зависимости от чисел в матрице весов;

Пропускаем по найденному пути максимальный возможный поток для этого пути;

Из ребер матрицы пропускных способностей вычитаем величину потока, то есть устанавливаем остаточную пропускную способность этих ребер;

Для каждого обнуленного ребра в матрице пропускных способностей обнуляем ребро в матрице стоимостей;

Если текущий пропущенный поток меньше заданного переходим к шагу 1.

Реализация алгоритма:

void pot_min_st(vector<vector<int>> propSpos, vector<vector<int>> price, vector<int> s, vector<int> t, int max)

{

int n = propSpos.size(), maxB = max;;

int minPath, ti, tj, temp;

bool temps, tempt;

vector<vector<int>> rezult(n, vector<int>(n));

vector<vector<int>> priceEtalon(price);

list<int> minP;

while (max)

{

minPath = Deykstra(price, s[0], t[0]);

ti = 0;

tj = 0;

for (int i = 0; i < s.size(); i++)

for (int j = 0; j < t.size(); j++)

if (min(minPath, Deykstra(price, s[i], t[j])) != minPath)

{

minPath = Deykstra(price, s[i], t[j]);

ti = i;

tj = j;

}

minP = MakePath(price, minPath, s[ti], t[tj]);

temp = propSpos[*minP.begin()][*++minP.begin()];

for (list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{

jt++;

if (min(propSpos[*it][*jt], temp) != temp)

temp = propSpos[*it][*jt];

}

if (temp > max) temp = max;

cout << endl << "Пускаем поток (" << temp << ")" << " по пути ";

ti = 0;

list<int>::iterator it;

for (it = minP.begin(); it != minP.end(); it++, ti++)

{

cout << *it + 1;

if (ti < minP.size()-1)

cout << "-";

}

ti = 0;

cout << ". Стоимость данного потока ";

for (list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{

jt++;

ti += price[*it][*jt] * temp;

propSpos[*it][*jt] -= temp;

rezult[*it][*jt] += temp;

if (!propSpos[*jt][*it] && propSpos[*it][*jt])

{

propSpos[*jt][*it] += temp;

price[*jt][*it] = -price[*it][*jt];

}

if (!propSpos[*it][*jt] && !rezult[*jt][*it])

price[*it][*jt] = 0;

}

cout << ti << endl;

if(max - temp)

cout << "Оставшийся поток равен " << max - temp << endl;

Save(price, "Промежуточная матрица стоимости");

Save(propSpos, "Промежуточная матрица пропускной способности");

for (int i = 0; i < n; i++)

for (int j = i; j < n; j++)

if (price[i][j] < 0)

price[i][j] = 0;

max -= temp;

}

int rez = 0;

for (int i = 0; i < n; i++)

for (int j = i; j < n; j++)

if (rezult[i][j])

rez += rezult[i][j] * priceEtalon[i][j];

cout << endl << "Минимальная стоимость потока " << maxB << " равна " << rez;

cout << endl << "Все промежуточные матрицы стоимости и потоков сохранены в файл graph.txt";

if(rezult.size() < 25)

Print(rezult, "\n\t\tНовая матрица потоков");

else

cout << endl << "Новая матрица потоков сохранена в файл graph.txt\n" << endl;

}

Алгоритм Фалкерсона

Алгоритм Форда -- Фалкерсона решает задачу нахождения максимального потока в транспортной сети.

Идея алгоритма заключается в следующем. Изначально величине потока присваивается значение 0: f(u,v)=0 для всех u,v ? V. Затем величина потока итеративно увеличивается посредством поиска увеличивающего пути (путь от источника s к стоку t, вдоль которого можно послать больший поток). Процесс повторяется, пока можно найти увеличивающий путь.

Обнуляем все потоки. Остаточная сеть изначально совпадает с исходной сетью.

В остаточной сети находим любой путь из источника в сток. Если такого пути нет, останавливаемся.

Пускаем через найденный путь (он называется увеличивающим путём) максимально возможный поток:

На найденном пути в остаточной сети ищем ребро с минимальной пропускной способностью .

Для каждого ребра на найденном пути увеличиваем поток на , а в противоположном ему -- уменьшаем на .

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

Возвращаемся на шаг 2.

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

Реализация алгоритма

#include "main.h"

int min(int a, int b){

if (a == 0) return b;

if (b == 0) return a;

return (a < b) ? a : b;}

bool Svyazn(vector<vector<int>>& matr){

vector<vector<int>> temp(matr);

int n = matr.size();

for (int i = 0; i < n; i++)

for (int j = 0; j < n; j++)

for (int k = 0; k < n; k++)

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];

for (int i = 1; i < n; i++)

if (!temp[0][i]) return false;

return true;}

int Falkerson(vector<vector<int>> propSpos, vector<int> s, vector<int> t){

int n = propSpos.size(), max = 0, ti = 0, tj = 0, minPath, temp;

vector<vector<int>> rezult(n, vector<int>(n));

list<int> minP;

do {

minPath = Bellman(propSpos, s[0], t[0]);//

ti = 0;

tj = 0;

for (int i = 0; i < s.size(); i++)

for (int j = 0; j < t.size(); j++)

if (min(minPath, Bellman(propSpos, s[i], t[j])) != minPath)//

{

minPath = Bellman(propSpos, s[i], t[j]);//

ti = i;

tj = j;

}

minP = MakePath(propSpos, minPath, s[ti], t[tj]);//

temp = propSpos[*minP.begin()][*++minP.begin()];

for (list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{

jt++;

if (min(propSpos[*it][*jt], temp) != temp)

temp = propSpos[*it][*jt];

}

ti = 0;

for (list<int>::iterator it = minP.begin(), jt = minP.begin(); it != --minP.end(); it++, jt = it)

{

jt++;

ti += propSpos[*it][*jt] * temp;//

propSpos[*it][*jt] -= temp;

rezult[*it][*jt] += temp;

if (!propSpos[*jt][*it] && propSpos[*it][*jt])

propSpos[*jt][*it] += temp;

if (!propSpos[*it][*jt] && !rezult[*jt][*it])

propSpos[*it][*jt] = 0;

}

max += temp;

}while (Svyazn(propSpos));//

return max;

}

Алгоритм Беллмана - Форда

Алгоритм Беллмана-Форда -- алгоритм поиска кратчайшего пути во взвешенном графе. Он имеет сложность О(p*q) - это худший случай и сложность О(р) в лучшем случае. Алгоритм находит кратчайшие пути от одной вершины графа до всех остальных. В отличие от алгоритма Дейкстры, алгоритм Беллмана-Форда допускает рёбра с отрицательным весом, но его ограничением является то, что на входе должен быть граф без циклов с отрицательным весом. В нашем случае на вход функции идет порядковый номер вершин, между которыми будет происходить поиск кратчайшего пути.

В отличие от алгоритма Дейкстры в этом алгоритме нет постоянных меток, но есть очередь. Сначала берется стартовая вершина и заносится в очередь. Расстояние до остальных вершин предполагается равным бесконечности (то есть константа LONG_MAX в нашей программе).

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

Корректировка очереди. Если раньше вершина не была в очереди, то ее ставим в конец, а если была или находится в данный момент, то ставим ее в начало очереди.

Алгоритм работает, пока очередь не станет пустой, т.е. пока из очереди можно взять вершину.

Реализация алгоритма:

int Bellman(vector<vector<int>>& matr, int start, int end)

{

int n = matr.size();

int t;

vector<vector<int>> temp(n, vector<int>(2));

for (int i = 0; i < n; i++)

temp[i][0] = LONG_MAX;

vector<int> queue;

queue.push_back(start);

temp[start][1] = 1;

temp[start][0] = 0;

while (queue.size() != 0)

{

t = *queue.begin();

queue.erase(queue.begin());

for (int i = 0; i < matr.size(); i++)

{//для каждой вершины

if (matr[t][i] != 0)

{

temp[i][0];

temp[t][0] + matr[t][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];

if (temp[i][1])

queue.insert(queue.begin(),i);

else

{

queue.push_back(i);//Иначе - в конец

temp[i][1] = 1;

}}}}}

return temp[end][0];}

Алгоритм Дейкстры

Алгоритм Дейкстры находит кратчайшее расстояние от одной из вершин графа до всех остальных. Алгоритм работает только для графов без рёбер отрицательного веса (из-за этого перед началом работы алгоритма, все отрицательные веса в матрице берутся по модулю). Сложность - O(n).

Работу алгоритма можно разделить на два этапа:

Первый этап: Присвоение вершинам начальных меток.

Каждой вершине сопоставим метку - расстояние от этой вершины до начальной вершины. Алгоритм работает пошагово - на каждом шаге он «посещает» одну вершину и пытается уменьшать метки. Работа алгоритма завершается, когда все вершины посещены.

Метка начальной вершины полагается равной 0, метки остальных вершин - бесконечности (роль бесконечности выполняет константа LONG_MAX, равная 2147483647L). Бесконечность значит, что расстояния от начальной вершины до других пока неизвестны. Все вершины графа, кроме начальной, помечаются как не посещённые.

Шаг алгоритма.

Если все вершины посещены, алгоритм завершается. В противном случае, из ещё не посещённых вершин выбирается вершина u, имеющая минимальную метку. Мы рассматриваем всевозможные маршруты, в которых u является предпоследним пунктом. Для каждой соседней вершины u, кроме посещённых, рассмотрим новую длину пути, равную сумме значений текущей метки u и длины ребра, соединяющего u с соседней вершиной. Если полученное значение длины меньше значения метки соседней вершины, заменим значение метки полученным значением длины. Рассмотрев все соседние вершины, пометим вершину u как посещенную и повторим шаг алгоритма.
В нашем случае нужно найти кратчайшее расстояние между заданными вершинами, поэтому на входе две вершины, а не одна.

Второй этап: Построение кратчайшего пути.

Среди вершин, непосредственно предшествующих текущей, с постоянной меткой, ищем вершину, удовлетворяющую соотношению:

где метка вершины, вес ребра, текущая вершина, которая добавляется в маршрут.

Реализация алгоритма:

Первый этап

int Deykstra(vector<vector<int>>& weight, int start, int end)

{

vector<vector<int>> matr = weight;

int n = matr.size();

for (int p = 0; p < n; p++)

for (int m = 0; m < n; m++)

if(matr[m][p]<0)

matr[m][p]= -matr[m][p];

vector<vector<int>> temp (n, vector<int>(2));

for (int i = 0; i < n; i++)

temp[i][0] = LONG_MAX;

temp[start][1] = 1;//делаем постоянную метку в начале

temp[start][0] = 0;// значение

Work(matr, temp, start, end);

returntemp[end][0];

}

где функция Work:

void Work(vector<vector<int>>& matr, vector<vector<int>>& temp, int start, int end)

{

int st = start;

while (st != end)

{

int m = LONG_MAX;if (temp[end][1] != 0) return;

for (int i = 0; i < matr.size(); i++)

{

CountN++;

if (matr[st][i] != 0)

if (temp[i][1] == 0)

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))

{

st = k;m = temp[k][0];

}

}

temp[st][1] = 1;

}}

Второй этап.

void Path(vector<vector<int>>& matr, int lenght, int start, int end, list<int>& path){//рекурсивное заполнение пути (1 шаг - одна вершина)

int n=matr.size(), tmp;

vector<vector<int>> tmatr (matr);

bool b=true, tp=false;

for (int i=0; b; i++)

{

if (start==i&&matr[i][end]==lenght)return;

tmp = tmatr[end][i];

tmatr[end][i]=0;

if((matr[i][end]!=0)&&(matr[i][end]!=lenght)&&(Bellman(tmatr,start,i)==lenght-matr[i][end]))

{

path.push_front(i);

lenght -= matr[i][end];

end = i;

b = false;

}

else tmatr[end][i] = tmp;

}

Path(tmatr ,lenght, start, end, path);

}

list<int> MakePath(vector<vector<int>>& matr, int lenght, int start, int end)

{

if (start==end) return list<int>(0);

list<int> path;

Path(matr,lenght, start, end, path);

path.push_front(start);

path.push_back(end);

return path;

}



Результаты работы программы

Пример работы программы будет приводиться на связном ориентированном графе, сформированным по распределению Пойа-1.

Рис1. Пример работы программы: вывод распределения и матрицы получившегося графа.

Рис2. Пример работы программы: вывод матрицы стоимости вершин, полученной случайным образом

Рис3. Пример работы программы: вывод матрицы пропускной способности, полученной случайным образом

Рис4. Пример работы программы: вывод результата работы алгоритма Фалкерсона.

Рис5. Пример работы программы: вычисление потока минимальной стоимости.

Рис6. Пример работы программы: вывод матрицы потоков, полученной после пропускания потока заданной стоимости.

Заключение

В данной работе был сформирован связный ациклический граф в соответствии с распределением Пойа-1. Матрицы стоимости и пропускной способности реализованы путем замены единиц в матрице смежности на числа, полученные случайным образом. Для полученного графа был найден максимальный поток с помощью теоремы Форда-Фалкерсона. Максимальный поток ищется при помощи алгоритма Беллмана - Форда, что отличается от классического метода, использующего поиск в глубину.

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

В качестве величины потока брали 2/3 от максимального потока. Поиск минимальных по стоимости путей производился с помощью алгоритмов Беллмана - Форда и Дейкстры. Алгоритм Дейкстры лучше использовать при условии, что граф не имеет отрицательные веса, так как он работает быстрее, чем алгоритм Беллмана-Форда. Для более общего решения нужно использовать алгоритм Беллмана-Форда. С каждым шагом происходит модификация сети с учетом пропустившегося потока. Модификация заключается в изменении матриц стоимостей и пропускных способностей после каждой итерации.

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

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

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

Чтобы модифицировать эту программу, можно добавить визуализацию графа и каждого изменения матриц стоимости и пропускной способности, прослеживая распределения потоков. В программе мы пропускаем 2/3 от максимального потока, а можно предоставить выбор пропускаемого потока пользователю, не допуская возможность пустить поток больше максимального.



Список использованной литературы

Новиков Ф.А. Дискретная математика для программистов: Учебник для вузов. 3-е изд. - СПБ.: Питер, 2009. - 384 с.

Вадзинский Р.Н. Справочник по вероятностным распределениям. - СПб.: Наука, 2001. - 295 с.

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