Нахождение максимального потока в сети
Курсовая по предмету:
"Высшая математика"
Название работы:
"Нахождение максимального потока в сети"
Автор работы: Юлия
Страниц: 19 шт.
Год:2010
Краткая выдержка из текста работы (Аннотация)
Введение
Бурное развитие дискретной математики обусловлено прогрессом компьютерной техники, необходимостью создания средств обработки и передачи информации, а также представления различных моделей на компьютерах, являющихся по своей природе конечными структурами. Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира. 60 лет назад, задача о максимальном потоке решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения этой задачи ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов.
Содержание работы
Содержание
Введение 3
1. Теория и основные понятия 4
2. Поток в транспортной сети 6
3. Постановка задачи 9
4. Сети, потоки в сетях. Теорема Форда – Фалкерсона 10
5. Реализация 14
6. Постановка задачи 16
Заключение 18
Список литературы 19
Использованная литература
- М.О. Осанов, В.А. Баранский, В.В. Расин, Дискретная математика: графы, матроиды, алгоритмы – Ижевск, НИЦ «Регулярная и хаотическая динамика»; 2001.
- А.И. Белоусов, С.Б. Ткачев, Дискретная математика: учебник для вузов – Изд – во МГТУ им. Н.Э. Баумана;2004.
- В.Н. Нефедов, В.А. Осипова «Курс дискретной математики» М. 1992
- С.В. Судоплатов, Е.В. Овчинникова «Элементы дискретной математики» М. 2002
- \"Алгоритмы. Построение и анализ\" Т. Кормен, Ч. Лейзерсон, Р. Ривест (\"Introduction to Algorithms\" Thomas Cormen, Charles Leiserson, Roland Rivest) , стр. 536 - 573.
- Методическое пособие - Элементы теории множеств и теории графов. Сборник задач и упражнений по курсу Дискретная математика, М. 1992