Определение максимального потока сети с помощью метода расстановки пометок
Автор: Гагарин Ю.Е., Никитенко У.В., Мосин Е.Д.
Журнал: Международный журнал гуманитарных и естественных наук @intjournal
Рубрика: Технические науки
Статья в выпуске: 4-2 (67), 2022 года.
Бесплатный доступ
В статье рассмотрен один из методов решения задачи о максимальном потоке. Этот метод основан на расстановке пометок и для его реализации используется нескольких эффективных алгоритмов, одним из которых является алгоритм Форда-Фалкерсона. За счет экономии времени и ресурсов, практическое применение алгоритма обеспечивает эффективную работу программ, связанных с сетевыми структурами.
Оптимизация, максимальный поток, сетевые структуры, расстановка пометок
Короткий адрес: https://sciup.org/170193333
IDR: 170193333
Текст научной статьи Определение максимального потока сети с помощью метода расстановки пометок
Задачу о максимальном потоке в сети можно сформулировать следующим образом: имеется некоторый произвольный неориентированный граф, например, городская дорожно-уличная сеть, по которой происходит движение транспорта от истока (начало движение транспорта) к стоку (конечная точка движения) [1]. Каждое ребро сети имеет свой вес. В случае с городской дорожно-уличной сетью это может быть ширина дороги или её пропускная способность, т.е. количество транспорта в единицу времени. Задача о максимальном потоке для данной сети состоит в нахождении максимального количества транспорта, перемещающегося от начальной вершины - источника, к конечной вершине графа - стоку. При этом, в подобных задачах необходимо определять интервальные величины потоков рассматриваемой сети [2]. Это дает возможность учесть неопределенность исходных данных, что повышает достоверность принимаемого решения [3, 4].
Эта задача может быть решена общим методом линейного программирования. Существует другой метод, который предложили Лестер Рэндольф Форд и Делберт Рей Фалкерсон и этот метод основан на расстановке пометок. Использование этого методы привело к появлению нескольких эффективных алгоритмов.
Рассмотрим реализацию алгоритма Форда-Фалкерсона для нахождения максимального потока. Работа алгоритма начинается с нулевого потока и затем, на каждой итерации, происходит увеличение потока в сети. На каждом шаге ищется цепь, которая увеличивает величину потока. При этом, поток увеличивается вдоль дуг этой цепи, пока она не станет насыщенной.
Такой увеличивающей цепью является цепь из источника в сток, все дуги которой допустимы. Для того, чтобы увеличить величину потока сети на некоторую величину Q , необходимо увеличить на такую же величину Q поток на каждой согласованной дуге цепи и уменьшить на каждой несогласованной. Фордом и Фалкерсоном было доказано, что поток в сети, для которой нельзя построить увеличивающую цепь, является максимальным.
Для нахождения такой увеличивающей цепи используется метод расстановки пометок. Процесс расстановки меток начинается в источнике сети и заканчивается в ее стоке. Увеличивающаяся цепь из источника в сток существует, если сток будет являться помеченным. На вершины сети наносятся метки, содержащие необходимую информацию для восстановления цепи и определения величины, на которую можно изменить поток в сети. При этом вершина может находиться в одном из следующих состояний: непомеченная, помеченная и просмотренная.
Метод расстановки пометок начинается с произвольного потока. Затем предпринимается попытка получить поток с большей величиной. Вычисления заканчиваются, когда получен максимальный поток. Алгоритм заключается в последовательном поиске всех возможных путей из узла N S в узел N , увеличивающих поток. Узлы получают специальные «пометки», указывающие направление, в котором может быть увеличен некоторый дуговой поток. После того как найден некоторый путь, увеличивающий поток, определяют величину максимальной пропускной способности этого пути; далее поток увеличивают на эту величину, а все пометки на узлах стирают. Затем начинается расстановка новых пометок узлов исходя из только что полученного потока.
Алгоритм состоит из двух этапов. Этап 1 – узлы получают пометки, причем каждый узел находится в одном из трех состояний: помечен и просмотрен, помечен и не просмотрен или не помечен. Вначале все узлы не помечены. Пометка произвольного узла N j всегда состоит из двух частей. Первая часть – индекс j узла N , который указывает, что можно «послать» поток из N в N j . Вторая часть пометки – число, указывающее максимальную вели- чину потока, который можно «послать» из источника NS в N j , не нарушая ограничений на пропускные способности дуг.
Список литературы Определение максимального потока сети с помощью метода расстановки пометок
- Гагарин Ю.Е. Интервальное оценивание условных вероятностей в байесовских сетях доверия / Ю.Е. Гагарин, У.В. Никитенко, М.А. Степович // Актуальные проблемы прикладной математики, информатики и механики: сборник трудов Международной научной конференции. - Воронеж: Научно-исследовательские публикации, 2021. - С. 802-804.
- EDN: CMVDZJ
- Гагарин Ю.Е. Прогнозирование показателей деятельности предприятий с учетом неопределенности исходных данных / Ю.Е. Гагарин, С.Н. Гагарина // Вестник университета. - 2019. - №1. - С. 94-99.
- DOI: 10.26425/1816-4277-2019-1-94-99 EDN: YZESOL
- Гагарин Ю.Е. Интервальное оценивание объемов потребления ресурсов при стохастических исходных данных / Ю.Е. Гагарин, С.Н. Гагарина // Вестник университета. - 2018. - №12. - С. 64-70.
- DOI: 10.26425/1816-4277-2018-12-64-70 EDN: YXCQUX
- Гагарина С.Н. Интервальное прогнозирование объемов спроса на услуги субъектов естественных монополий с учетом неопределенности информации / С.Н. Гагарина, Ю.Е. Гагарин // Вестник университета. - 2013. - №22. - С. 101-110.
- EDN: RYDMKN
- Гагарина С.Н. Повышение эффективности городской транспортной инфраструктуры на основе цифровых технологий / С.Н. Гагарина, Н.Н. Чаусов, В.Н. Левкина // Вестник университета. - 2020. - №7. - С. 68-75.
- DOI: 10.26425/1816-4277-2020-7-68-75 EDN: WUJJLR