Учебная работа № 6184. «Курсовая Применение метода Форда-Фалкерсона для выделения Web-групп в WWW
Учебная работа № 6184. «Курсовая Применение метода Форда-Фалкерсона для выделения Web-групп в WWW
Содержание:
Введение 3
1. Теоретическая часть 5
1.2 Основные определения и теоремы 5
1.2 Нахождение максимального пропускного потока 8
1.3 Сводимость некоторых задач о максимальном потоке в сети к рассматриваемой 10
1.4 Алгоритм Форда-Фалкерсона 12
2. Практическая часть 16
2.1 Алгоритм решения 16
2.2 Работа с программой 18
2.3 Расчёт потока 20
2.4 Тестирование 22
Заключение 26
Введение
Задача о максимальном потоке в сети изучается уже более 60 лет. Интерес к ней подогревается огромной практической значимостью этой проблемы. Методы решения задачи применяются на транспортных, коммуникационных, электрических сетях, при моделировании различных процессов физики и химии, в некоторых операциях над матрицами, для решения родственных задач теории графов, и даже для поиска Web-групп в WWW. Исследования данной задачи проводятся во множестве крупнейших университетов мира.
60 лет назад, эта задача решалась simplex методом линейного программирования, что было крайне не эффективно. Форд и Фалкресон предложили рассматривать для решения задачи о максимальном потоке ориентированную сеть и искать решение с помощью итерационного алгоритма. В течение 20 лет, все передовые достижения в исследовании данной задачи базировались на их методе. В 1970г. наш соотечественник, Диниц, предложил решать задачу с использованием вспомогательных бесконтурных сетей и псевдомаксимальных потоков, что намного увеличило быстродействие разрабатываемых алгоритмов. А в 1974 Карзанов улучшил метод Диница, введя такое понятие как предпоток. Алгоритмы Диница и Карзанова, как и исследования Форда и Фалкерсона, внесли огромный вклад в решение данной проблемы. На основе их методов 15 лет достигались наилучшие оценки быстродействия алгоритмов. В 1986г. появился третий метод, который также без раздумий можно отнести к фундаментальным. Этот метод был разработан Голдбергом и Таряном, и получил название Push-Relabel метода. Для нахождения максимального потока, он использует предпотоки и метки, изменяемые во время работы алгоритма. Push-Relabel алгоритмы очень эффективны, и исследуются до сих пор. И, наконец, в 1997г. Голдберг и Рао предложили алгоритм, присваивающий дугам неединичную длину. Это самый современный из всех известных мне алгоритмов. Асимптотическая оценка его быстродействия превзошла O(nm), о такой скорости многие годы можно было только мечтать. Уверен, что за прошедшие годы алгоритм Голдберга и Рао тщательно изучался и улучшался.
К сожалению, в России, в настоящее время, передовые алгоритмы освещаются слабо. Во всех русскоязычных учебниках, рассматривающих задачу о максимальном потоке в сети, вы вряд ли встретите что-либо, кроме метода пометок Форда-Фалкерсона 60-летней давности. В то время как в зарубежной литературе им редко ограничиваются.
В этой работе рассматривается и применение метода Форда-Фалкерсона для выделения Web-групп в WWW.
Выдержка из похожей работы
При подготовке
реферата необходимо сначала изучить
теоретический материал по заданной
теме, а затем четко изложить суть
рассматриваемых вопросов, Для защиты
реферата подготовить презентацию в
среде PowerPoint, Ориентировочное время для
защиты реферата — 7-10 минут,
Реферат должен
быть оформлен в электронном и бумажном
варианте, При разработке реферата
обязательно использовать различные
возможности оформления документов
(внедрение объектов, колонтитулы, работу
со стилями и т,д,)
По остальным темам
подготовить по одному вопросу для
обсуждения при защите реферата,Вопрос 2, Необходимо решить оптимизационную задачу средствами Microsoft Excel, Решение задачи представить в электронном и бумажном варианте,
Вопрос 3, Необходимо
перевести каждое из исходных чисел в
двоичную систему счисления, Выполнить
действия в двоичной системе счисления,
Результат перевести в десятичную систему
счисления, Проверить правильность
решения в десятичной системе счисления,
Требования к
оформлению отчета по домашней контрольной
работе,
Результаты
выполнения ДКР оформляются в виде
бумажного и электронного варианта
отчета,
Структура бумажного
варианта отчета (формат А4):
— титульный лист;
— теоретическая
часть (реферат);
— практическая
часть (задачи);
— список использованной
литературы и электронных образовательных
ресурсов,
Электронный вариант
контрольной работы ‑ диск с файлами:
— файл с текстом
отчета, соответствующий бумажному
варианту;
— презентация для
защиты реферата,
— вопросы по другим
темам рефератов,
Задания для домашней контрольной работы
Вариант 1
1
