Алгоритм Форда-Фалкерсона

Метод заключается в поиске возможных путей из A_S в A_T, увеличивающих поток. За начальный выбирается любой произвольный поток в графе, в частности нулевой.

Поиск выполняют в два этапа.

На первом этапе вершинам присваивают специальные пометки, указываю-щие направление возможного увеличения отдельных дуговых потоков; на втором – производят изменение потока в графе.

Рассмотрим работу алгоритма на примере графа с одним источником a_S и одним стоком a_t, обобщив затем его для задач с несколькими A_S и A_T.

 

Расстановка меток

На первом этапе каждая вершина графа находится в одном из трех состояний: «не помечена», «помечена, но не просмотрена», «помечена и просмотрена».

Пометка любой вершины графа a_j состоит из двух частей: первая часть указывает индекс вершины, из которой можно послать поток в рассматривае-мую a_j, вторая – максимальную величину, на которую можно увеличить поток из a_S в a_j без нарушения ограничений на пропускные способности дуг. Сначала все вершины не помечены.

Пометки расставляют, начиная с источника a_S, который получает пометку , что, указывает на возможность посылки неограниченного сверху потока из a_S в a_j. Вершина a_S считается помеченной, но не просмотренной.

Пусть имеется некоторая помеченная, но не просмотренная вершина a_j, имеющая пометку или . Знак в первой части пометки указыва-ет направление дугового потока: если – приращение потока в дуге b_ij совпадает на втором этапе с направлением первоначального потока дуги, если – приращение потока в дуге b_ij на втором этапе, противоположное направлению первоначального потока. Из множества соседних с a_j вершин Гa_j выделим подмножество A_K непомеченных вершин, для которых дуговой поток меньше пропускной способности . Припишем каждой соседней вершине пометку , где .

Выделим подмножество непомеченных вершин, для которых , то есть поток «идет» в противоположном направлении.

Припишем каждой последующей соседней вершине пометку , где . В результате все соседние с a_j верши-ны, которые могут получить пометки, оказываются помеченными, но не про-смотренными. А вершина a_j – помеченной и просмотренной.

Продолжаем приписывать пометки вершинам соседним с помеченными и не просмотренными узлами, до тех пор, пока либо сток a_T не будет помечен, либо не будет ни одной вершины, которая могла бы быть помечена, и сток a_T окажет-ся без пометки. Если a_T не получает пометки, то дальнейшее увеличение потока в сети невозможно, то есть исходный поток максимален. Иначе переходим ко второму этапу – изменению потока в сети.

 

Увеличение потока

Пусть по результатам первого этапа сток a_T получил метку . В этом случае заменяем на . Если же сток получит пометку , то заменяем .

Переходим к предыдущей вершине a_P. Если она имеет пометку , то заменяем на . Переходим к вершине a_j и т. д.

Процесс изменения потока продолжается до прихода в источник a_S. После этого все старые пометки стираются, и делается попытка вновь увеличить поток в графе (переходим к первому этапу алгоритма).

 

АЛГОРИТМ

· Расстановка пометок

1. Присвоить вершине S (источнику) пометку . Вершине S при-своена пометка и она просмотрена, все остальные вершины без пометок.

2. Взять некоторую непросмотренную вершину a_i с пометкой; пусть ее пометка будет .

а) Каждой непомеченной вершине , для которой , присвоить , где .

б) Каждой непомеченной вершине , для которой , присвоить пометку , где .

Теперь вершина a_i и помечена, и просмотрена, а вершины a_j, пометки которым присвоены в а) и б), являются непросмотренными. Обозначить, что вершина a_i просмотрена.

3. Повторить 2 до тех пор, пока либо сток T будет помечен, и тогда перейти к 4, либо T не будет помечен и никаких других пометок нельзя будет расставить. В этом случае алгоритм заканчивает работу с максимальным вектором потока X. Идти к 7.

· Увеличение потока

4. Положить и идти к 5.

5. а) Если пометка в вершине a_j имеет вид , то изменить поток вдоль дуги b_iT с x_iT на .

б) Если пометка в вершине a_j имеет вид , то изменить поток вдоль дуги b_iT с x_iT на .

6. Если , то стереть все пометки и вернуться к шагу 1, чтобы вновь начать расставлять пометки, но используя уже улучшенный поток, найденный на шаге 5. Если , то взять и вернуться к шагу 5.

· Конец работы алгоритма.

 

ПРИМЕР 6.1

Дана конструкция узла РЭС с нормализованными каналами для укладки жгутов (рис.6.2). В точках S и T узла размещено по разъему. Известны диаметры всех каналов (см. рис.6.2) и сечения укладываемых проводов – 1 мм². Требуется уложить максимально возможное количество проводов в жгут между этими разъемами, учитывая размеры каналов и сечения проводов.

 

Рис.6.2.

Решение

Задачу можно свести к поиску максимального потока в графе, моделирую-щем конструкцию узла. Для этого конструкцию представим в виде графа (рис.6.3), в котором узлы заданы вершинами, а каналы – ребрами между соот-ветствующими вершинами. Для работы по алгоритму Форда-Фалкерсона необходимо задать пропускные способности ребер. Для этого необходимо соответствующие диаметры каналов разделить на сечение провода. Так , , , , , , . Поскольку в начальный момент в каналы не уложено ни одного провода, потоки по дугам пока равны нулю – . Данную информацию запишем в виде двух чисел над ребрами: первое число – пропускная способность ребра, второе – поток по нему (см. рис.6.3).

 

Рис.6.3.

· Расстановка меток

Присваиваем вершине a_S пометку . Вершина a_S имеет две смежные вершины, и . Рассмотрим смежные вершины в порядке возрастания их номеров. Сначала . Она получает пометку , поскольку и .

Теперь . У нее метка будет , поскольку и . После этого вершина стала «помеченной и просмотренной», а вершины и – «помеченными, но не просмотрен-ными».

У вершины смежные и , а у – , и . Снова будем рассмат-ривать вершины в порядке возрастания их номеров. Сначала вершина . Будем пытаться расставлять метки смежным с ней вершинам. У метка уже есть – . Попытаемся пометить . Поскольку , вершину можно пометить через . Метка будет . Где «1» – это номер вершины , «+» – т. к. в направлении рассмотрения от к возможно увеличение потока и “2” – это минимальное число из . Все смежные с вершины помечены.

Рассмотрим теперь вершины, смежные . Из них и уже имеют метки, поэтому через пометим только . У нее метка будет , поскольку и . Все смежные с вершины также помечены. Следовательно, и «помечены и просмотрены».

· Переходим к вершине .

Смежные с ней вершины и уже помечены, поэтому попытаемся поме-тить оставшуюся вершину – сток.

Поскольку разность положительное число, сток можно пометить следующим образом: . Здесь «3» – номер вершины, «2» – это . Исходный граф с помеченными верши-нами приведен на рис.6.4.

· Увеличение потока.

Поскольку сток имеет пометку , то увеличиваем на две единицы. В результате получаем . Переходим к узлу , пометка которого . Увеличиваем также на 2. Получаем . Переходим к узлу , имеющему метку . Также увеличивается поток по дуге на две единицы, и получаем . Граф с измененным по нему потоком указан на рис.6.5. После этого стираем все метки при вершинах и меняем текущие потоки по дугам , и . Попытаемся вновь увеличить поток в графе.

· Увеличение потока.

Вершина вновь получает метку . Смежную с ней вершину пометить не удается, т. к. . У вершины , как и прежде, метка будет . Поскольку метки не получила, рассматриваем . Смежные с ней вершины и . Вершина получает метку , так как и . Вершина , как и на предыдущем шаге, получает метку . Все смежные с вершины помечены.

 

Рис.6.4. Рис.6.5.

 

Далее в порядке возрастания номеров перейдем к вершине . Она имеет две смежных вершины – и . Присвоим им метки: получит , « 3 » – это номер вершины , « – » – потому что поток направлен в направлении противоположном порядку рассмотрения вершин – от к . Величина второго числа метки в данном случае .

Следующей является вершина . Ее метка будет . Здесь второе число метки . Граф с помеченными вершинами приведен на рис.6.6.

 

Рис.6.6. Рис.6.7.

 

· Обратный ход алгоритма.

В связи с тем, что сток получил метку, переходим к обратному ходу алго-ритма. Метка у - , поэтому . Переходим к с меткой . Увеличим на две единицы: . Переходим к вершине . Здесь метка . Казалось бы, поток надо увеличить на 4 единицы. Но тогда поток в 2 единицы окажется «зависшим» в вершине . Поэтому поток – из S в вершину 2 увеличиваем на величину, равную ; . Получившийся поток показан на рис. 6.7.

Вновь стираем все метки при вершинах и попытаемся еще увеличить поток в графе. Расставляя аналогичным методом метки, получим результат, представ-ленный на рис.6.8. После обратного хода алгоритма окончательный граф с измененным потоком показан на рис.6.9. Повторная расстановка меток уже не приводит к пометке стока , т. к. ни одна из соседних с вершин не может быть помечена. Следовательно, максимальный поток в графе .

 

Рис.6.8. Рис.6.9.

 

Вернемся теперь к задаче укладки проводов в жгуты. В рассмотренную кон-струкцию узла (рис.6.2) можно уложить жгут максимум из шести проводов (рис.6.10).

 

Рис.6.10. Рис.6.11.

 

Метод расстановки пометок позволяет учитывать целый ряд дополнитель-ных требований к трассировке проводных соединений [2]. Например, для учета ограничений на максимальную длину отдельных проводников можно в про-цессе расстановки пометок вводить информацию об удаленности узлов от источника. В этом случае трассы, к длине которых предъявляются особые требования, прокладывают в первую очередь и они проходят через узлы, расстояние которых до источника меньше предельного. После их фиксации осуществляют разводку остальных проводников.

Если в графе несколько источников и стоков, то при отсутствии ограничения на прохождение потоков из отдельно взятых источников в строго определенные стоки задача сводится к задаче с одним источником и стоком. Для этого вводят искус-ственные источник S и сток T (рис.6.11).

Между ними и реальными источниками S_i и стоками T_j проводят дуги.

Пропускные способности дуг от S к S_i можно выбрать равными бесконеч-ности или, если пропускная способность дуги от S_k ограничена, то и у дуги SS_k она может равняться этой границе. Аналогичным образом поступают и с дугами от стоков T_j к искусственному стоку T.

 

ДОМАШНЕЕ ЗАДАНИЕ

 

2.1. Ознакомиться с методами решения задачи трассировки проводных соединений жгутовым монтажом.

2.2. Изучить алгоритм укладки проводов в жгуты (Форда-Фалкерсона).

2.3. Подготовить данные к эксперименту.

2.4. Выполнить трассировку проводов в жгуты по алгоритму Форда-Фалкерсона «вручную».