Алгоритми розв’язання задачі про максимальний потік у мережі, порівняння та їх застосування
Тип публікації :
Бакалаврська робота
Дата випуску :
2023
Автор(и) :
Марухно Тарас Васильович
Мова основного тексту :
ua
eKNUTSHIR URL :
Цитування :
[APA 7] Марухно, Т. В. (2023). Алгоритми розв’язання задачі про максимальний потік у мережі, порівняння та їх застосування [Бакалаврська робота, Київський національний університет імені Тараса Шевченка]. eKNUTSHIR. https://ir.library.knu.ua/handle/123456789/5755
[ДСТУ] Марухно Т. В. Алгоритми розв’язання задачі про максимальний потік у мережі, порівняння та їх застосування : кваліфікаційна робота бакалавра : 11 Математика та статистика. Київ, 2023. 45 с. URL: https://ir.library.knu.ua/handle/123456789/5755 (дата звернення: 25.07.2026).
Метою дипломної роботи є дослідження алгоритмів розв’язання задач про максимальний потік, а саме: порівняння часу розв’язання при різних вхідних даних, визначення для яких розмірів умови задачі який алгоритм є швидшим і наскільки.
Досліджено алгоритм Форда-Фалкерсона. Алгоритм Форда-Фалкерсона є найповільнішим алгоритмом розв’язання задачі про максимальний потік серед розглянутих. Його можна застосовувати лише для розв’язання задач дуже малих розмірів на кшталт 11 вершин та 26 ребер, і його швидкість буде меншою лише в 120 разів порівняно з алгоритмом Едмондса-Карпа, який виявився найшвидшим при такому розмірі, але вже при 20 вершинах та 53 ребрах буде в десятки тисяч разів повільнішим ніж алгоритми Дініца та Едмондса-Карпа.
Зроблено висновок що найшвидшими алгоритмами розв’язання задачі про максимальний потік є алгоритми Едмондса-Карпа та Дініца. Алгоритм Едмондса-Карпа варто застосовувати, коли мережі не є великими (приблизно до 20 вершин). Для більших мереж час роботи алгоритму Дініца буде приблизно таким як Едмондса-Карпа, або швидше.
Ключові слова : алгоритм Форда-Фалкерсона, алгоритми Едмондса-Карпа та Дініца, алгоритм Едмондса-Карпа.
Досліджено алгоритм Форда-Фалкерсона. Алгоритм Форда-Фалкерсона є найповільнішим алгоритмом розв’язання задачі про максимальний потік серед розглянутих. Його можна застосовувати лише для розв’язання задач дуже малих розмірів на кшталт 11 вершин та 26 ребер, і його швидкість буде меншою лише в 120 разів порівняно з алгоритмом Едмондса-Карпа, який виявився найшвидшим при такому розмірі, але вже при 20 вершинах та 53 ребрах буде в десятки тисяч разів повільнішим ніж алгоритми Дініца та Едмондса-Карпа.
Зроблено висновок що найшвидшими алгоритмами розв’язання задачі про максимальний потік є алгоритми Едмондса-Карпа та Дініца. Алгоритм Едмондса-Карпа варто застосовувати, коли мережі не є великими (приблизно до 20 вершин). Для більших мереж час роботи алгоритму Дініца буде приблизно таким як Едмондса-Карпа, або швидше.
Ключові слова : алгоритм Форда-Фалкерсона, алгоритми Едмондса-Карпа та Дініца, алгоритм Едмондса-Карпа.
Галузі знань та спеціальності :
11 Математика та статистика
113 Прикладна математика
Файл(и) :![Ескіз]()
Вантажиться...
Формат :
Adobe PDF
Розмір :
342.2 KB
Контрольна сума :
(MD5):2d47148a7061bff64c1604159ff1e0c4
Якщо не вказано інше, ця робота розповсюджується на умовах ліцензії Creative Commons Attribution-NonCommercial 4.0 International