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

АННОТАЦИЯ 2
ВВЕДЕНИЕ 5
ГЛАВА 1 ПОСТАНОВКА ЗАДАЧИ НА ИССЛЕДОВАНИЕ 7
1.1 Описание задачи о максимальном потоке 7
1.2 Математическая модель задачи о максимальном потоке 8
1.3 Приложения задачи о максимальном потоке 10
ГЛАВА 2 АЛГОРИТМЫ ПОИСКА МАКСИМАЛЬНОГО ПОТОКА 13
2.1 Алгоритм Форда-Фалкерсона 13
2.2 Алгоритм Эдмондса-Карпа 17
2.3 Алгоритм Диница 22
2.4 Метод масштабирования потока 26
2.5 Сравнение алгоритмов поиска максимального потока 29
ГЛАВА 3 ТЕСТИРОВАНИЕ АЛГОРИТМОВ ПОИСКА МАКСИМАЛЬНОГО
ПОТОКА 32
3.1 Исходные данные для тестирования 32
3.2 Тестирование алгоритмов 36
3.2.1 Тестирование на случайных графах 36
3.2.2 Тестирование на ациклических разреженных графах 39
3.2.3 Тестирование на полных графах 41
3.2.4 Тестирование на двудольных графах 43
3.2.5 Тестирование на графах решётках 45
3.3 Выводы по тестированию 49
ЗАКЛЮЧЕНИЕ 52
СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ 53


Купить

АННОТАЦИЯ
Тема бакалаврской работы: «Сравнительный анализ алгоритмов поиска максимального потока». Актуальность работы заключается в том, что при решении различных практических задач возникает необходимость переслать что-либо из одной точки в другую. Для решения данной проблемы может использоваться модель задачи о максимальном потоке. Поэтому выбор правильного алгоритма поиска максимального потока имеет большое значение, так как это чревато неэффективным или неточным решением исходной проблемы. Также, к задаче поиска максимального потока сводятся и другие важные оптимизационные практические задачи.
Объект исследования: процесс поиска максимального потока.
Предмет исследования: алгоритмы Форда-Фалкерсона, Эдмондса-Карпа, Диница поиска максимального потока.
Цель: выявление преимуществ и недостатков алгоритмов поиска
максимального потока для их правильного использования на практике.
Первая глава работы посвящена описанию задачи о максимальном потоке, ее математической модели и применениях.
Во второй главе описываются алгоритмы Форда-Фалкерсона, Эдмондса- Карпа, Диница, а также приведены доказательства корректности и сложности данных алгоритмов.
Третья глава посвящена тестированию алгоритмов и их сравнительному анализу.
Бакалаврская работа выполнена на 52 страницах, состоит из введения, трёх глав, заключения, списка литературы, состоящего из 22 литературных источников, 31 рисунка и 2 таблиц.
Задача максимального потока была решена еще в середине прошлого века, но несмотря на это, она до сих пор не теряет своей актуальности. Как правило, поток определяет способ передачи чего-либо из одной точки в другую. К примеру, перевозка груза от завода до распределительного склада и от склада до самих магазинов; движение людей от мест проживания к местам работы; доставка писем от отправителей к получателям. Так же, как будет показано дальше, к потокам можно свести и ряд других задач, которые, с первого взгляда, с потоками ничего общего не имеют. [6]
Несмотря на большое разнообразие ситуаций, связанных с потоками, в них возникает ряд определенных проблем. Примерами таких проблем могут быть максимизация объемов перевозки товара и минимизация времени этих перевозок, максимизация прибыли и минимизация суммарных затрат при выполнении каких-либо работ. [1][3]
Задача нахождения максимального потока является одной из наиболее изучаемых задач комбинаторной оптимизации и представляет собой частный случай задачи линейного программирования. Она была впервые сформулирована в 1954 году Харрисом как упрощенная модель советской железнодорожной системы движения. [3][8] Позже, в 1955 году Форд и Фалкерсон создали первый алгоритм нахождения максимального потока. [4][5] Но, несмотря на то, что данный алгоритм был не столь эффективен, он стал трамплином к более производительным и элегантным решениям.
Как уже было сказано, задача нахождения потока имеет широкое применение в реальных задачах, а значит существует необходимость в ее эффективном решении. Отсюда возникает необходимость в алгоритмах поиска потока, имеющих наибольшую производительность. Но, несмотря на широкий ряд существующих алгоритмов, какого-то универсального, подходящего для любой задачи, скорее всего не существует. В каких-то случаях лучше использовать один алгоритм, в каких-то другой.
Данная работа посвящена как теоретическому, так и практическому сравнительному анализу алгоритмов поиска максимального потока.
Целью бакалаврской работы является выявление сильных и слабых сторон алгоритмов поиска максимального потока в некоторых ситуациях для их правильного и эффективного использования на практике.
Объект исследования - процесс поиска максимального потока.
Предметом исследования являются алгоритмы поиска максимального потока Форда-Фалкерсона, Эдмонса-Карпа, Диница.
Для достижения поставленной цели необходимо выполнить следующие задачи:
• рассмотреть задачу о максимальном потоке и ее применения;
• рассмотреть алгоритмы решения задачи о максимальном потоке;
• провести теоретический сравнительный анализ алгоритмов;
• изучить различные модели сетей;
• разработать компьютерную программу генерирования сетей;
• провести генерирование тестовых данных;
• разработать компьютерную программу, реализующую алгоритмы
поиска максимального потока;
• провести тестирование алгоритмов на сгенерированных данных;
• провести сравнительный анализ алгоритмов на основе результатов тестирования.
Бакалаврская работа состоит из введения, трех глав и заключения.
В первой главе рассказывается о задаче поиска максимального потока, ее математической модели и применениях.
Во второй главе дано описание алгоритмов поиска максимального потока. Приведены доказательства корректности и асимптотические оценки работы алгоритмов, а также проведен теоретический сравнительный анализ их работы.
Третья глава посвящена генерированию тестовых данных, тестированию алгоритмов и их сравнительному анализу на основе результатов тестирования.

Купить