Нахождение максимального потока в сети

Содержание

Содержание

Введение3

1.Теория и основные понятия4

2.Поток в транспортной сети6

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

4.Сети, потоки в сетях. Теорема Форда – Фалкерсона10

5.Реализация14

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

Заключение18

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

Выдержка из текста

Введение

Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира. 60 лет назад, задача о максимальном потоке решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения этой задачи ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов.

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

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

1.М.О. Осанов, В.А. Баранский, В.В. Расин, Дискретная математика: графы, матроиды, алгоритмы – Ижевск, НИЦ «Регулярная и хаотическая динамика»; 2001.

2.А.И. Белоусов, С.Б. Ткачев, Дискретная математика: учебник для вузов – Изд – во МГТУ им. Н.Э. Баумана;2004.

3.В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992

4.С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002

5.»Алгоритмы. Построение и анализ» Т. Кормен, Ч. Лейзерсон, Р. Ривест («Introduction to Algorithms» Thomas Cormen, Charles Leiserson, Roland Rivest) , стр. 536 — 573.

6.Методическое пособие — Элементы теории множеств и теории графов. Сборник задач и упражнений по курсу Дискретная математика, М. 1992

Похожие записи