Нахождение максимального потока в графе. Метод Форда-Фалкерсона.

Работа защищена на оценку "Отлично" без каких либо замечаний по содержанию. Программный продукт работоспособен на 100% (в работе приведены расчёты). ...

Пояснительная записка
Введение 3
1. Постановка задачи 7
1.1. Экономическая сущность задачи 8
1.2 Математическая модель задачи 9
1.3. Входные данные программного продукта 10
1.4. Выходные данные программного продукта 10
1.5. Организация диалога 10
1.6. Функциональные тесты 14
1.6.1 Задача №1 14
1.6.1 Задача №2 16
1.6.1 Задача №3 17
2. Выбранный метод решения 19
3. Структурное проектирование задачи 21
4. Тестирование 23
5. Анализ надежности и качества 26
Заключение 27
Список литературы 28
Приложения

Бурное развитие дискретной математики обусловлено прогрессом компьютерных технологий. Огромные потоки данных передаются на расстоянии. Эти достижения стали возможными во многом благодаря дискретной математике, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами.
На первый взгляд, для успешного написания программ достаточно знаний устройства компьютера, процессов обмена данных с оперативной памятью и основных языков программирования. На практике необходимы готовые алгоритмы для работы с различными структурами данных.
Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения зад ачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.

Рисунок 13. Начальный граф
Итерация 1.
h1 = min (4-5-3-2)=0, gmax=0
Рисунок 14. Итерация №1
Путей ведущих из вершины 4 в 2 больше нет, следовательно, решение окончено и максимальный поток из начальной вершины в конечную равен gmax = 0.
1.6.3 Задача №3
Найти максимальный поток в графе из вершины 2 в вершину 5.
Рисунок 15. Начальный граф
Рисунок 16. Итерация №1
Итерация 1.
h1 = min (2-1-4-3-5)=1
Рисунок 16. Итерация №2
Итерация 2.
h2 = min (2-4-3-5)=2, gmax=2+1=3
Путей ведущих из вершины 2 в 5 больше нет, следовательно, решение окончено и максимальный поток из начальной вершины в конечную равен gmax = 3.
2. Выбранный метод решения
Существующие методы решения делятся на классы:
1)математические программы MATLAB, MATHCAD, MS EXCEL. Однако данные программы предполагают формулировку исходной задачи в форме задачи математического программирования, что снижает наглядность представления исходных данных и результата. Кроме того, с помощью сетевого подхода описываются очень масштабные реальные ситуации, а эти программы не позволяют обрабатывать большое количество переменных и ограничений;
2)специальные точные алгоритмы, которые учитывают специфические особенности объектов графа. Именно к таким алгоритмам относится алгоритм пометок Форда-Фалкерсона. Он является одним из наиболее эффективных методов решения задачи;
3)алгоритмы нахождения приближенного решения – генетические и нейросетевые. Полученное решение будет лишь близким к оптимальному.
Таким образом, алгоритм Форда-Фалкерсона позволяет найти точное решение задачи.
Алгоритм Форда-Фалкерсона2 начинает работу с начального допустимого потока. Затем осуществляются попытки увеличить величину потока с помощью систематического поиска всех возможных цепей из s в t, на которых можно увеличить величину потока (дополняющие цепи).
Поиск дополняющих цепей производится путем расстановки меток, которые указывают, на каких дугах и насколько можно увеличить поток. Когда найдена одна из таких цепей, поток вдоль нее увеличивается. После чего все метки стираются, и вновь полученный поток используется в качестве исходного при новой расстановке меток.
Алгоритм заканчивает работу, когда нельзя найти ни одну дополняющую цепь. Последний найденный поток является максимальным.
Важной частью алгоритма является этап расстановки меток. Каждая вершина может находиться в одном из трех состояний:
вершина помечена и просмотрена (т.е. вершина имеет метку и все смежные с ней вершины «обработаны»);
вершина помечена, но не просмотрена (т.е. вершина имеет метку, но смежные с ней вершины не «обработаны»);
вершина не помечена;
Метка некоторой вершины  имеет вид . Часть меткиозначает, что поток может быть увеличен вдоль дуги . Часть метки означает, что поток может быть уменьшен вдоль дуги . В обоих случаях показывает максимальную величину, на которую можно увеличить поток от к вдоль дополняющей цепи.
Сначала все вершины не имеют меток.
Шаг 0. Инициализация.
Положим все дуговые потоки равными нулю: .
Шаг 1. Назначить вершине метку .
Теперь вершина помечена, но не просмотрена. Все остальные вершины не помечены.
Шаг 2. Просмотр помеченных вершин.
Выбрать некоторую помеченную, но не просмотренную вершину ; пусть ее метка будет .
1. Каждой непомеченной вершине , для которой , назначить метку , где .
2. Каждой непомеченной вершине , для которой назначить метку , где .
Теперь вершина помечена и просмотрена, а вершина , метка которой назначена в пунктах 1 или 2, помечена, но не просмотрена. Каким-либо образом отмечается, что вершина просмотрена.
Шаг 3. Проверка.
Если на Шаге 2 какая-либо вершина помечена, то:
если помечена вершина , то на Шаг 4;
если помечена любая другая вершина, то на Шаг 2.
Если на Шаге 2 нельзя назначить никаких меток, то алгоритм заканчивает работу с некоторым максимальным потоком.
Шаг 4. Выбрать вершину ; на Шаг 5.
Шаг 5. Увеличение потока.
1. Если метка вершины имеет вид , то изменить поток вдоль дуги с на .
2. Если метка вершины имеет вид , то изменить поток вдоль дуги с на .
Шаг 6. Если , то стереть все метки и вернуться к Шагу 1. При этом используется уже увеличенный поток, найденный на Шаге 5.
Если , то положить ; на Шаг 5.
3. Структурное проектирование задачи
На рисунке 17 представлена общая схема работы программы.
Рисунок 17. Общая схема работы программы
Алгоритм Форда-Фалекрсона работает пока можно найти хотя бы один путь из источника в сток, итеративно увеличивая поток на минимальную величину. На рисунке 18 представлена детальная блок-схема алгоритма Форда-Фалкерсона.
Рисунок 18. Расширенная блок-схема алгоритма Форда-Фалкерсона
4. Тестирование
В качестве тестирования, проведем вычисленные ранее контрольные расчеты (пункт 1.6)
В первом тесте максимальный поток равнялся 10.(начальный граф представлен на рисунке 7). Тестирование показало что пример решеный ранее имеет такой же ответ как и в программе (рисунок 19).
Рисунок 19. Тестовый пример №1
Во втором тесте максимальный поток равнялся 0.(начальный граф представлен на рисунке 13). Тестирование показало, что пример решеный ранее имеет такой же ответ, как и в программе (рисунок 20).
Рисунок 20. Тестовый пример №2
В третьем тесте максимальный поток равнялся 3.(начальный граф представлен на рисунке 15). Тестирование показало, что пример решеный ранее имеет такой же ответ, как и в программе (рисунок 21).
Рисунок 21. Тестовый пример №3
5. Анализ надежности и качества
Если в результате выполнения программы пользователь ошибочно ввел данные, то программа выведет следующее сообщение.
Рисунок 22. Сообщение об ошибке
Данное сообщение оповещает о том что:
данные небыли введены в поля ввода данных;
введены отрицательные данные;
введены не числовые данные;
исток или сток больше чем количество вершин.
Заключение
Работа над курсовым проектом позволила расширить знания по практическому применению алгоритма Форда-Фалкерсона, рассмотрена экономическая сущность данной задачи, а также методы её решения. После чего произведено проектирование и реализация на языке программирования высокого уровня. Так же произведено тестирование и получены анализы надежности качества результате тестирования разработанного программного обеспечения.
Получены новые знания и навыки применять теоретические и практические знания, полученные при изучении курса, для разработки программного обеспечения на языке Delphi и была разработана программа, реализующие вычисление максимального потока в графе методом Форда-Фалкерсона. К данной программе прилагается пояснительная записка, содержащая метод решения, разработанный алгоритм, а так же текст программы с комментариями и результаты тестов. В программу могут внести изменения и дополнения программисты, владеющие языком Delphi.
Так же курсовая работа имеет открытый код программы, поэтому любой программист владеющий навыками программирования в Delphi может изменить программу.
Для проверки качества работы программы было решено 3 задачи, в результате решения их решения все 3 решения совпали и программа показала 100% результат решения задач по нахождению максимального потока в графе методом Форда-Фалкерсона.
В тестировании программы недостатков не обнаружено, программный продукт работает и выполняет все поставленные функции.
Таким образом, поставленные задачи выполнены. Цель проекта достигнута.
Список литературы
1. Беляева И. В. Основы программирования на языке Turbo Pascal. Ульяновск.:УлГТУ, 2011. 266 с
2. Ставровский А.Б. Турбо Паскаль 7.0. Учебник. К.: Издательская группа BHV, 2000. 400 с.
3. Фаронов В.В. Турбо Паскаль 7.0. Учебное пособие.- М.: “Нолидж”, 2003. 576 с..
4. Немнюгин С.А. Turbo Pascal:Практикум. Питер,2002. 256 с.
5. Материал из Википедии: «Алгоритм Форда-Фалкерсона». URL: http://ru.wikipedia.org/wiki/Алгоритм_Форда_—_Фалкерсона (дата обращения: 26.03.2014)
6. Алексеев, Е.Р. Самоучитель по программированию на Free Pascal и Lazarus. - Донецк.:ДонНТУ, Технопарк УНИТЕХ, 2009.503 с.
7. Меженный, О. А. Turbo Pascal. Самоучитель. Вильямс.: Диалектика, 2011. 366 с.
8. Нил Дж. Рубенкинг. Delphi для "чайников". Вильямс.: Диалектика, 2011. 336 с.
Приложения
Листинг программы
unit UnFord;
interface
uses
Windows, Messages, SysUtils, Variants, Classes, Graphics, Controls, Forms,
Dialogs, StdCtrls, Grids, ComCtrls, Spin, Menus,unit2;
type
TForm1 = class(TForm)
grp1: TGroupBox;
strngrd1: TStringGrid;
lbl2: TLabel;
lbl3: TLabel;
lbl5: TLabel;
lbl6: TLabel;
edt1: TEdit;
edt2: TEdit;
Button1: TButton;
se1: TSpinEdit;
grp2: TGroupBox;
mmo1: TMemo;
mm1: TMainMenu;
cvcx1: TMenuItem;
N1: TMenuItem;
Button2: TButton;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure se1Change(Sender: TObject);
procedure N1Click(Sender: TObject);
procedure cvcx1Click(Sender: TObject);
procedure FormShow(Sender: TObject);
procedure Button2Click(Sender: TObject);
private
{ Private declarations }
public
{ Public declarations }
end;
const beskonechnost = 10000;
var
Form1: TForm1;
f:array[0..100,0..100]of longint; // f[i][j] - поток, текущий от вершины i к j
c:array[0..100,0..100]of longint; // c[i][j] - максимальная величина потока, способная течь по ребру (i,j)
NN:longint; // число вершин в графе
// набор вспомогательных переменных, используемых функцией FindPath - обхода в ширину
zhach_pot:array[0..100]of longint; // zhach_pot - значение потока через данную вершину на данном шаге поиска
pred_vresh:array[0..100]of longint; // pred_vresh[i] хранит номер предыдущей вешины на пути i -> исток
ochered:array[0..100]of longint; // очередь
n_ochered, k_ochered:longint; // n_ochered - указатель начала очереди и k_ochered - число эл-тов в очереди
implementation
{$R *.dfm}
// поиск пути, по которому возможно пустить поток алгоритмом обхода графа
// функция ищет путь из истока в сток, по которому еще можно пустить поток,
// считая вместимость ребера (i,j) равной c[i][j] - f[i][j]
function Poisk_puti(sou:longint; tar:longint): longint; // source - исток, target - сток