Читать курсовая по математике: "Задачи и алгоритмы дискретной математики" Страница 1

(Назад) (Cкачать работу)

КУРСОВАЯ РАБОТА

Задачи и алгоритмы дискретной математики

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

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

алгоритм программный дискретный математика 1. Потоки в сетях: алгоритм Форда-Фалкерсона .1 Формулировка задания ­ изучить теоретические аспекты вопроса построения алгоритма Форда-Фалкерсона;

­ ручная реализация решения задачи нахождения максимального потока в транспортной сети;

­ по средствам выбранного мною языка программирования C# осуществить программную реализацию алгоритма Форда-Фалкерсона. .2 Изучение алгоритма Так как алгоритм Форда-Фалкерсона решает задачу нахождения максимального потока в транспортной сети, следует ввести несколько понятий.

Транспортная сеть - это ориентированный граф, ребра которого имеют определенную не отрицательную пропускную способность и поток. Выделяют две такие вершины s (исток) и t (сток), что любые другие вершины находятся на пути из s в t.

Целочисленная транспортная сеть - транспортная сеть, все пропускные способности ребер которой - целые числа.

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

Идея алгоритма Форда-Фалкерсона заключается в том, чтобы выбрать произвольный путь от источника (s) к стоку (t), найти на этом пути минимальное значение остаточных пропускных способностей и увеличиваем поток на каждом ребре этого пути на найденное значение. Такие действия проделываются для всех возможных путей.

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

Пошаговое описание алгоритма:

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

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

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

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

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

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

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

Для поиска

Похожие работы