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

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

Содержание

Содержание

Введение

1. Постановка задачи

2. Теоретическая часть задания

3. Описание алгоритма поставленной задачи

4. Пример ручного расчёта задачи и вычислений

5. Описание программы

5.1 Общее описание

5.2 Функции программы

6. Тесты

6.1 О тестировании

6.2 Тестирование программы

6.3 Результаты тестирования

Список литературы

Листинг программы

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

Заключение



Введение

В данной курсовой работе необходимо составить программу нахождения максимального потока в транспортной сети, представленной орграфом. Сам алгоритм нахождения представлен единовременно двумя ученными и несет название «Алгоритм Форда - Фалкерсона». Алгоритм был представлен в 1956 году. В основном нахождение максимального потока в графе используется в инженерных задачах. Данный программный продукт позволяет автоматизировать расчёт максимального потока в транспортной, и призван упростить работу инженерам.



1. Постановка задачи

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

Задание для курсового проектирования заключается в создании программного продукта позволяющего находить максимальный поток в транспортной сети в ориентированном графе для заданных вершин (истока и стока). При том, одной из главных особенностей моего программного продукта является визуализация графа по средствам ручного ввода матрицы смежности или её случайная генерация.

Для удовлетворения требований задачи я выбрал язык C++. C++ широко используется для разработки программного обеспечения, являясь одним из самых популярных языков программирования. Область его применения очень широка. C++ оказал огромное влияние на другие языки программирования, в первую очередь на Java и C#. Синтаксис C++ унаследован от языка C. Также С++ является объектно-ориентированным языком программирования (ООП). Объектно-ориентированное программирование - это методология программирования, основанная на представлении программ в виде совокупности объектов, каждый из которых является экземпляром определённого класса, а классы образуют иерархию наследования.

С++ доступен для большинства операционных систем, включая Linux, многие модификации Unix, Microsoft Windows, Mac OS X, RISC OS, и многих других.

Преимущества С++:

· Большая безопасность

· Возможность писать обобщенный код с помощью шаблонов

· Возможность использовать объектно-ориентированный подход

· Управление ресурсами с помощью RAII

· Упрощение кода за счет перегрузки функций и операторов

· Более простая обработка ошибок за счет исключений

2. Теоретическая часть задания

Оптимальным алгоритмом для нахождения максимального потока в транспортной сети является алгоритм Форда - Фалкерсона. Проводится первоначальный выбор точки пути начала и конца (исток и сток транспортной сети). Далее для удобства представления разделим весь алгоритм на 3 этапа: этап инициализации, этап пересчета максимального потока всех путей и этап нахождения максимального потока всей транспортной сети.

В первом этапе происходит инициализация, т.е. для всех рёбер (i, j) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравниваем {} = {}. Назначаем и помечаем узел истока меткой [, 1].

Во втором этапе идет подсчёт значений максимального потока на всех возможных путях из истока в сток. Он делится на 5 шагов:

§ Шаг 1. Предполагаем, что i = 1 (i - текущий узел транспортной сети). Переходим к шагу 2.

§ Шаг 2. Определяем множества как множество узлов, в которые можно перейти из узла i по ребру с положительной остаточной пропускной спо - собностью (т.е. > 0 для всех j, принадлежащих ). При этом узел j дол жен быть не помеченным на текущей итерации. Если не пустое мно - жество, выполняем третий шаг, в противном случае переходим к шагу 4.

§ Шаг 3. Во множестве находим узел k такой, что для всех j, принадлежащих . Положим и пометим узел k меткой []. Если последней меткой помечен узел стока (т.е. k = n), сквозной путь найден, и мы переходим к пятому шагу, иначе полагаем i = k и переходим к шагу 2.

§ Шаг 4. (Откат назад) Если i = 1, то сквозной путь невозможен и мы переходим к третьему этапу. Если i ? 1, находим помеченный узел r, непосредственно предшествующий узлу i (смотрим по метке [), и удаляем узел i из множества узлов, смежных с узлом r. Полагаем i = r и переходим к шагу 2.

§ Шаг 5. (Определение остаточной сети) Пусть множество узлов, через которые проходит p - й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n). Тогда максимальный поток проходящий по этому пути, вычисляется как Остаточные пропускные способности рёбер, составляющих сквозной путь, уменьшается на величину в направлении движения потока и увеличиваются на эту же велечину в противоположном направлении. Таким образом, для ребра (i, j), входящего в сквозной путь, текущие остаточные стоимости {} изменяются следующим образом: если поток идёт от узла i к узлу j {}; если поток идёт от узла j к узлу i {}. Убираем метки со всех узлов кроме истока. Переходим на первый шаг для поиска нового сквозного пути.

В третьем этапе вычисляется максимальный поток всей транспортной сети. При m найденных сквозных путях максимальный поток вычисляется по формуле . Имея значения начальных {} и конечных {} пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим (a, b) = {}. Если a > 0, то поток, проходящей через ребро (i, j), равен a. Если же b > 0, тогда поток равен b. (Случай, когда одновременно a > 0 и b > 0, невозможен).

3. Описание алгоритма поставленной задачи

Описание формального алгоритма находится в приложении «А», листинг 1 (а так же пояснительные комментарии к коду основных функций алгоритма программы). Основные переменные программы также представлены в приложении «А», листинг 2.

Для примера расчёта решим задачу в виде нахождения максимального потока для графа, матрицей смежности которого будет являться матрица m строк и n столбцов (где m и n - это вершины ориентированного графа D{V, E} (рисунок 1), а элементы матрицы будут выражать пропускную способность ребра, т.е. создадим матрицу пропускных способностей). Для наглядности и относительной простоты, я выберу небольшой орграф, где количество вершин будет равно пяти:

Далее зададим пропускные способности рёбер (обозначаемые как ), исток и сток (выберем истоком, а стоком), и сформируем матрицу про - пускных способностей (рисунок 2):



D {V, E} =

Рисунок 2 - Помеченный орграф D{V, E}.

Рисунок 3 - Результат программного расчёта транспортной сети D{V, E}.D{V, E}

Результатом выполнения программы является максимальный поток равный 60 (рисунок 3). Далее мы проверим правильность алгоритма ручным расчётом данной транспортной сети.



4. Пример ручного расчёта задачи и вычислений

Для ручного расчёта решим задачу в виде нахождения максимального потока для графа, матрицей смежности которого будет являться матрица из пункта (*3) пояснительной записки курсовой работы (рисунок 2).

Для начала нужно выполнить инициализацию транспортной сети (рисунок 4). Для всех рёбер (i, j) положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем {} = {}. Пометим узел 1 меткой [?, -].

Рисунок 4 - Инициализированный орграф D{V, E}

Все подготовки для начала нахождения максимального потока выполнены, приступаем к самому алгоритму его нахождения (используем алгоритм Форда - Фалкерсона).

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

Итерация *1 :

· Шаг 1: Полагаем i = 1 и переходим ко второму шагу.

· Шаг 2: .

· Шаг 3: k = 3, т.к.

Назначаем и помечаем узел 3 меткой [30, 1]. Полагаем i = 3 и переходим к шагу 2 (рисунок 5).

Рисунок 5 - Выполнение алгоритма Форда-Фалкерсона, итерация (*1). Орграф D{V, E}

· Шаг 2:

· Шаг 3: k = 5, т.к.

Помечаем узел 5 меткой [20, 3] (рисунок 6). Поскольку k = 5 переходим к шагу 5

Рисунок 6 - Выполнение алгоритма Форда-Фалкерсона, итерация (*1). Орграф D{V, E}

· Шаг 5: сквозной путь определяем по меткам, начиная с узла 5 заканчивая узлом 1: (5) < [20, 3] < (3) < [30, 1] < (1).

Таким образом, Вычисляем остаточные пропускной способности вдоль пути (рисунок 7):

{} = {30 - 20, 0 + 20} = {10 , 20};

{} = {20 - 20, 0 + 20} = {0 , 20}.

Итерация *2:

Рисунок 7 - Выполнение алгоритма Форда-Фалкерсона, итерация (*2). Орграф D{V, E}

· Шаг 1: i = 1.

· Шаг 2: .

· Шаг 3: k = 2, назначаем и помечаем узел 2 меткой [20, 1] (рисунок 8). Полагаем i = 2 и переходим к шагу 2



Рисунок 8 - Выполнение алгоритма Форда-Фалкерсона, итерация (*2). Орграф D{V, E}

· Шаг 2:

Рисунок 9 - Выполнение алгоритма Форда-Фалкерсона, итерация (*2). Орграф D{V, E}

· Шаг 3: k = 5, назначаем и помечаем узел 5 меткой [20, 4] (рисунок 10). Переходим к шагу 5.



Рисунок 10 - Выполнение алгоритма Форда-Фалкерсона, итерация (*2). Орграф D{V, E}

· Шаг 5. Сквозной путь:

; ;

Остаточные пропускные способности пути :

{} = {20 - 10, 0 + 10} = {10 , 10},

{} = {40 - 10, 0 + 10} = {30 , 10},

{} = {10 - 10, 0 + 10} = {0 , 10},

{} = {20 - 10, 0 + 10} = {10 , 10}.



Итерация *3 (рисунок 11):

Рисунок 11 - Выполнение алгоритма Форда-Фалкерсона, итерация (*3). Орграф D{V, E}

· Шаг 1: i = 1.

· Шаг 2.

· Шаг 3: k = 2, назначаем и помечаем узел 2 меткой [10, 1] (рисунок 12). Полагаем i = 2 и переходим к шагу 2.

Рисунок 12 - Выполнение алгоритма Форда-Фалкерсона, итерация (*3). Орграф D{V, E}

· Шаг 2.

· Шаг 3: k = 3, назначаем и помечаем узел 3 (рисунок 13). Полагаем i = 3 и переходим к шагу 2.

-

Рисунок 13 - Выполнение алгоритма, итерация (*3). Орграф D{V, E}

· Шаг 2: Переходим к шагу 4.

· Шаг4: Метка [30, 2] узла 3 показывает номер предшествующего узла r = 2. Но на этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем (рисунок 14). Полагаем i = r = 2, переходим к шагу 2.

Рисунок 14 - Выполнение алгоритма Форда-Фалкерсона, итерация (*3). Орграф D{V, E}

· Шаг 2:

· Шаг 3: k = 5, назначаем и помечаем узел 5 меткой

[30, 2]. Переходим к шагу 5.

· Шаг 5: Сквозной путь: ; ;

Остаточные пропускные способности пути (рисунок 15):

{} = {10 - 10, 10 + 10} = {0, 20},

{} = {30 - 10, 0 + 10} = {20, 10}.

Рисунок 15 - Выполнение алгоритма Форда-Фалкерсона, итерация (*3). Орграф D{V, E}



Итерация 4 (рисунок 16):

Рисунок 16 - Выполнение алгоритма Форда-Фалкерсона, итерация (*4). Орграф D{V, E}

Пропустим итерацию 4 и 5 т.к. они выполняется аналогично предыдущим (согласно алгоритму Форда - Фалкерсона).

Итерация *6 (финальная на рисунке 17):

Рисунок 17 - Выполнение алгоритма Форда-Фалкерсона, итерация (*6). Орграф D{V, E}

· Шаг 1: i = 1.

· Шаг 2: .

· Шаг 4: i = 1, сквозной путь невозможен, переходим к шагу 6.

· Шаг 6 (Решение): Максимальный объем потока равен:

.

Значения потоков по рёбрам:

Ребро		Величина потока	Направление
{1, 2}	{20,0} - {0, 20} = {20, -20}	20	1 > 2
{1, 3}	{30, 0} - {0, 30} = {30, -30}	30	1 > 3
{1, 4}	{10, 0} - {0, 10} = {10, -10}	10	1 > 4
{2, 3}	{40, 0} - {40, 0} = {0, 0}	0	-
{2, 5}	{30, 0} - {10, 20} = {20, -20}	20	2 > 5
{3, 4}	{10, 5} - {0, 15} = {10, -10}	10	3 > 4
{3, 5}	{20, 0} - {0, 20} = {20, -20}	20	3 > 5
{4, 5}	{20, 0} - {0, 20} = {20, -20}	20	4 > 5

5. Описание программы

5.1 Общее описание

Задание для курсового проектирования заключается в создании своего программного продукта, позволяющего найти максимальный поток в заданной транспортной сети.

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

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

5.2 Функции программы

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

Функция «FindPath»

Функция включает в себя: нахождение отличного от найденных путей из истока в сток (методом обхода графа в ширину), подсчет максимального потока в текущем пути и возвращение максимальный поток в числовом виде в функцию «MaxFlow».

Функция «MaxFlow».

Возвращенный результат из функции функция «FindPath» складывает с текущим значением суммы максимального потока, и возвращается в функцию «FindPath» (далее ищет новый путь, пока такие существуют). В конце выводится результат суммы, что и является ответом на задачу.

Пользователь задаёт размер матрицы транспортной сети (рисунок 18) в окошке (*1) «Кол-во размерность матрицы». Далее осуществляется ввод желаемого номера истока и стока в текстовые окна(*2) «исток» и «сток». В правом окошке появляются поля для ввода значений пропускной способности ребра (в каждая позиция соответствует каждому ребру). После чего пользователь может вручную задать пропускные способности(*3) (нажав флаг «вручную») или же случайным образом (нажав флаг «рандом»). Для стабильной и быстрой работы, максимальная размерность транспортной сети ограничена (максимальное количество узлов равно сорока). После заполнение полей и нажатия кнопки «рассчитать», программа рисует граф в левой части окна и выводит ответ рядом с надписью(*4) «максимальный поток:».

Рисунок 18 - Описание полей взаимодействия с пользователем



6. Тесты

6.1 О тестировании

Любая достаточно объемная программа требует отладки, а в дальнейшем и тестирования, состоящей в поиске и устранении ошибок. Как говорится: в программах не делал ошибок только тот, кто никогда не писал их. Итак, ошибки - это объективная неизбежность или реальное воплощение этой неизбежности.

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

§ Ошибки при выполнении проявляются на стадии выполнения программы. К таким ошибкам, как правило, относятся недопустимые математические операции (деление на ноль, вычисление логарифма отрицательного числа или нуля, вычисление квадратного корня отрицательного числа), некорректные данные, введенные пользователем, и им подобные.

§ Логические ошибки обусловлены нарушением логики решения той или иной задачи. Например, искажением метода решения задачи, ошибочной записью математической функции и другие. Эти ошибки не мешают выполнению программы (не приводят к её прерыванию или вывода ошибки). Их проявление можно обнаружить по результатам решения задачи, ибо они будут неверными.

6.2 Тестирование программы

Для тестирования используем 2 различных по типам наборов данных:

§ Цифры (Исток = 0, Сток = 4, Размерность матрицы = 5).

§ Любые другие символы кроме цифр;

Результаты тестирования представлены на рисунках 19-20.

6.3 Результаты тестирования

Рисунок 19 - Результат тестирования программы с тестируемым набором «цифры».

Рисунок 20 - Результат тестирования программы с тестовым набором «Любые символы»

Список литературы

1. Электронный ресурс: https://msdn.microsoft.com Дата обращения: 05.11.2017.

2. Электронный ресурс: https://ru.wikipedia.org/wiki/ (Дата обращения: 05.11.2017).

3. Электронный ресурс: http://www.cyberforum.ru/ Дата обращения: 05.11.2017.

4. Дискретная математика для программистов, Р. Хаггарти ISBN 5-94836-016-4, 0-201-73047-2, 2005.

5. Discrete Mathematics with Combinatorics, Джеймс Андерсон -- 2-е изд., 2004. -- ISBN 978-5-9775-0445-4.

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

Листинг программы

Функция FindPath

int FindPath(int source, int target){

QP = 0; QC = 1; Queue[0] = source;

Link[target] = -1;

int i;

int CurVertex;

memset(Flow, 0, sizeof(int)*NUM_VERTICES);

Flow[source] = INFINITY;

while (Link[target] == -1 && QP < QC)

{

CurVertex = Queue[QP];

for (i=0; i<NUM_VERTICES; i++)

if ((c[CurVertex][i] - f[CurVertex][i])>0 && Flow[i] == 0)

{

Queue[QC] = i; QC++;

Link[i] = CurVertex;

if (c[CurVertex][i]-f[CurVertex][i] < Flow[CurVertex])

Flow[i] = c[CurVertex][i];

else

Flow[i] = Flow[CurVertex];

}

QP++;

}

if (Link[target] == -1) return 0;

CurVertex = target;

while (CurVertex != source) {

f[Link[CurVertex]][CurVertex] +=Flow[target];

CurVertex = Link[CurVertex];

}

return Flow[target];

}

Листинг 1 - Листинг основной функции FindPath.

Функция MaxFlow

int MaxFlow(int source, int target) {

memset(f, 0, sizeof(int)*MAX_VERTICES*MAX_VERTICES);

int MaxFlow = 0;

int AddFlow;

do {

AddFlow = FindPath(source, target);

MaxFlow += AddFlow;

} while (AddFlow >0);

return MaxFlow;

}

Листинг 2 - Листинг функции MaxFlow.



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

На рисунках 21 - 23 представлена работа программы в 3 фазах: запуск, ввод данных и вывод результата.

Рисунок 21 - Состояние программы при запуске

Рисунок 22 - Состояние программы при вводе данных

Рисунок 23 - Состояние программы после её выполнения



Заключение

В ходе работы был реализован алгоритм для нахождения максимального потока в транспортной сети. Для решения поставленной задачи был выбран алгоритм Форда - Фалкерсона. Были использованы возможности языка программирования C++ и фреймворка windows forms, базированного на visual studio 10. Были применены многие методы и особенности языковой структуры си++. Поставленная задача была полностью реализована.

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

...