Порівняльний аналіз та програмна реалізація методів розв'язання задачі про максимальний потік у мережах
Вантажиться...
Дата
2023
Автори
Науковий керівник
Назва журналу
Номер ISSN
Назва тому
Видавець
Анотація
Дипломна робота: 127 с., 52 рис., 6 табл., 2 дод., 22 джерела.
Об’єктом роботи є задача пошуку максимального потоку в мережах.
Предметом роботи є методи знаходження максимального потоку в
мережах, їх асимптотична складність та порівняння за часом (швидкістю
виконання).
Мета роботи полягає в програмній реалізації алгоритма Форда-
Фалкерсона, Едмондса-Карпа та просування передпотоку; вказати та
обґрунтувати їх асимптотичну складність; виконати порівняльний аналіз
вказаних алгоритмів.
Результатом роботи є розроблене програмне забезпечення, яке реалізує
алгоритми знаходження максимального потоку. Також було виконано аналіз
та порівняння їх результатів.
Вирішені наступні завдання:
− досліджені та порівняні різні методи розв’язання задачі про
максимальний потік, а саме алгоритм Форда-Фалкерсона, Едмондса-
Карпа та просування передпотоку;
− реалізовано програмний код на мові Python для кожного з алгоритмів
та проведено експерименти на різних множинах тестових мереж;
− зроблено порівняльний аналіз ефективності методів залежно від
розміру мережі та її характеристик.
Опис
Ключові слова
максимальний потік, задача про максимальний потік, алгоритм форда-фалкерсона, алгоритм едмондса-карпа, алгоритм просування передпотоку, maximum flow, maximum flow problem, ford-fulkerson algorithm, edmonds-karp algorithm, push-relabel algorithm
Бібліографічний опис
Боднар, М. С. Порівняльний аналіз та програмна реалізація методів розв'язання задачі про максимальний потік у мережах : дипломна робота ... бакалавра : 124 Системний аналіз / Боднар Максим Сергійович. – Київ, 2023. – 127 с.