Алгоритм Форда-Фалкерсона
Метод заключается в поиске возможных путей из AS в AT, увеличивающих поток. За начальный выбирается любой произвольный поток в графе, в частности нулевой. Поиск выполняют в два этапа. На первом этапе вершинам присваивают специальные пометки, указываю-щие направление возможного увеличения отдельных дуговых потоков; на втором – производят изменение потока в графе. Рассмотрим работу алгоритма на примере графа с одним источником aS и одним стоком at, обобщив затем его для задач с несколькими AS и AT.
Расстановка меток На первом этапе каждая вершина графа находится в одном из трех состояний: «не помечена», «помечена, но не просмотрена», «помечена и просмотрена». Пометка любой вершины графа aj состоит из двух частей: первая часть указывает индекс вершины, из которой можно послать поток в рассматривае-мую aj, вторая – максимальную величину, на которую можно увеличить поток из aS в aj без нарушения ограничений на пропускные способности дуг. Сначала все вершины не помечены. Пометки расставляют, начиная с источника aS, который получает пометку Пусть имеется некоторая помеченная, но не просмотренная вершина aj, имеющая пометку Выделим подмножество Припишем каждой последующей соседней вершине Продолжаем приписывать пометки вершинам соседним с помеченными и не просмотренными узлами, до тех пор, пока либо сток aT не будет помечен, либо не будет ни одной вершины, которая могла бы быть помечена, и сток aT окажет-ся без пометки. Если aT не получает пометки, то дальнейшее увеличение потока в сети невозможно, то есть исходный поток максимален. Иначе переходим ко второму этапу – изменению потока в сети.
Увеличение потока Пусть по результатам первого этапа сток aT получил метку Переходим к предыдущей вершине aP. Если она имеет пометку Процесс изменения потока продолжается до прихода в источник aS. После этого все старые пометки стираются, и делается попытка вновь увеличить поток в графе (переходим к первому этапу алгоритма).
АЛГОРИТМ · Расстановка пометок 1. Присвоить вершине S (источнику) пометку 2. Взять некоторую непросмотренную вершину ai с пометкой; пусть ее пометка будет а) Каждой непомеченной вершине б) Каждой непомеченной вершине Теперь вершина ai и помечена, и просмотрена, а вершины aj, пометки которым присвоены в а) и б), являются непросмотренными. Обозначить, что вершина ai просмотрена. 3. Повторить 2 до тех пор, пока либо сток T будет помечен, и тогда перейти к 4, либо T не будет помечен и никаких других пометок нельзя будет расставить. В этом случае алгоритм заканчивает работу с максимальным вектором потока X. Идти к 7. · Увеличение потока 4. Положить 5. а) Если пометка в вершине aj имеет вид б) Если пометка в вершине aj имеет вид 6. Если · Конец работы алгоритма.
ПРИМЕР 6.1 Дана конструкция узла РЭС с нормализованными каналами для укладки жгутов (рис.6.2). В точках S и T узла размещено по разъему. Известны диаметры всех каналов (см. рис.6.2) и сечения укладываемых проводов – 1 мм2. Требуется уложить максимально возможное количество проводов в жгут между этими разъемами, учитывая размеры каналов и сечения проводов.
Рис.6.2. Решение Задачу можно свести к поиску максимального потока в графе, моделирую-щем конструкцию узла. Для этого конструкцию представим в виде графа (рис.6.3), в котором узлы заданы вершинами, а каналы – ребрами между соот-ветствующими вершинами. Для работы по алгоритму Форда-Фалкерсона необходимо задать пропускные способности ребер. Для этого необходимо соответствующие диаметры каналов разделить на сечение провода. Так
Рис.6.3. · Расстановка меток Присваиваем вершине aS пометку Теперь У вершины Рассмотрим теперь вершины, смежные · Переходим к вершине Смежные с ней вершины Поскольку разность · Увеличение потока. Поскольку сток · Увеличение потока. Вершина
Рис.6.4. Рис.6.5.
Далее в порядке возрастания номеров перейдем к вершине Следующей является вершина
Рис.6.6. Рис.6.7.
· Обратный ход алгоритма. В связи с тем, что сток Вновь стираем все метки при вершинах и попытаемся еще увеличить поток в графе. Расставляя аналогичным методом метки, получим результат, представ-ленный на рис.6.8. После обратного хода алгоритма окончательный граф с измененным потоком показан на рис.6.9. Повторная расстановка меток уже не приводит к пометке стока
Рис.6.8. Рис.6.9.
Вернемся теперь к задаче укладки проводов в жгуты. В рассмотренную кон-струкцию узла (рис.6.2) можно уложить жгут максимум из шести проводов (рис.6.10).
Рис.6.10. Рис.6.11.
Метод расстановки пометок позволяет учитывать целый ряд дополнитель-ных требований к трассировке проводных соединений [2]. Например, для учета ограничений на максимальную длину отдельных проводников можно в про-цессе расстановки пометок вводить информацию об удаленности узлов от источника. В этом случае трассы, к длине которых предъявляются особые требования, прокладывают в первую очередь и они проходят через узлы, расстояние которых до источника меньше предельного. После их фиксации осуществляют разводку остальных проводников. Если в графе несколько источников и стоков, то при отсутствии ограничения на прохождение потоков из отдельно взятых источников в строго определенные стоки задача сводится к задаче с одним источником и стоком. Для этого вводят искус-ственные источник S и сток T (рис.6.11). Между ними и реальными источниками Si и стоками Tj проводят дуги. Пропускные способности дуг от S к Si можно выбрать равными бесконеч-ности или, если пропускная способность дуги от Sk ограничена, то и у дуги SSk она может равняться этой границе. Аналогичным образом поступают и с дугами от стоков Tj к искусственному стоку T.
ДОМАШНЕЕ ЗАДАНИЕ
2.1. Ознакомиться с методами решения задачи трассировки проводных соединений жгутовым монтажом. 2.2. Изучить алгоритм укладки проводов в жгуты (Форда-Фалкерсона). 2.3. Подготовить данные к эксперименту. 2.4. Выполнить трассировку проводов в жгуты по алгоритму Форда-Фалкерсона «вручную».
Популярное: Как построить свою речь (словесное оформление):
При подготовке публичного выступления перед оратором возникает вопрос, как лучше словесно оформить свою... Как вы ведете себя при стрессе?: Вы можете самостоятельно управлять стрессом! Каждый из нас имеет право и возможность уменьшить его воздействие на нас... Почему стероиды повышают давление?: Основных причин три... ![]() ©2015-2024 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (988)
|
Почему 1285321 студент выбрали МегаОбучалку... Система поиска информации Мобильная версия сайта Удобная навигация Нет шокирующей рекламы |