Математическая формулировка задачи. Цель работы – исследовать эффективность алгоритма трассировки соединений в жгуты; освоить особенности алгоритмизации и программирова-ния задачи трассировки

ЛАБОРАТОРНАЯ РАБОТА №6

ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА

ТРАССИРОВКИ ПРОВОДОВ В ЖГУТЫ

Цель работы – исследовать эффективность алгоритма трассировки соединений в жгуты; освоить особенности алгоритмизации и программирова-ния задачи трассировки проводов на современных ПЭВМ алгоритмом Форда-Фалкерсона; приобрести навыки построения математических моделей провод-ных соединений, реализации и исследования их при решении задачи трассиров-ки с применением САПР.

 

ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ

 

Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s (источника) графа к некоторой конечной вершине t (стоку). При этом каждой дуге графа G приписывается некоторая пропускная способность , определяющая наибольшее значение потока, который может протекать по данной дуге [8, 9].

Метод решения задачи о максимальном потоке был предложен в 1962 г. американскими учеными Фордом и Фалкерсоном. Предложенная «техника пометок» составляет основу других алгоритмов решения многочисленных задач, являющихся простыми обобщениями или расширениями указанной задачи.

Эта задача и ее варианты часто возникают на практике. При конструирова-нии РЭС с ней сталкиваются при проектировании жгутового монтажа, при канальной трассировке печатных и пленочных соединений [1, 2, 4].

В этом случае проводники укладываются в нормализованные каналы, расположенные в монтажном пространстве узлов во взаимно перпендикулярных направлениях (рис. 6.1, а).

Рис. 6.1.

Математическая формулировка задачи

 

Канальную конструкцию подобного типа можно представить в виде ортого-нальной несимметрической сети (графа ) с множеством узлов (вершин) A и множеством дуг (ребер) B (рис. 6.1, б). Каждой дуге (ребру) , соединяющей вершины , приписывается некоторое число . Оно соответствует, например, максимальному числу проводников, укладываемых на участке, моделируемом дугой (ребром) . Величина называется пропускной способностью дуги (ребра) . Множества текущих чисел , определенных на дугах , называют потоками по дуге или дуговыми потоками. Дуговой поток изменяется в пределах:

. (6.1)

Множество вершин A разобьем на подмножества:

A_S – источники, вершины из которых выходят дуги;

A_T – стоки, вершины в которые входят дуги;

A_P – промежуточные вершины, через которые проходит поток.

Тогда для любой вершины графа должно выполняться условие:

(6.2)

Здесь .

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

. (6.3)

Поскольку пропускные способности дуг (ребер) ограничены, то задача сводится к поиску такого максимального потока в графе, при котором достигается максимум функции (6.3) при ограничениях (6.1) и (6.2). Поскольку и – целые числа, то задача сводится к задаче линейного целочисленного программирования.

 

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

Метод заключается в поиске возможных путей из 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. Выполнить трассировку проводов в жгуты по алгоритму Форда-Фалкерсона «вручную».

 

ЗАДАНИЕ К ЛАБОРАТОРНОЙ РАБОТЕ

3.1. Порядок работы с программой «PCPROV» в режиме раскладки проводов в жгуты

Алгоритм трассировки проводов в жгуты реализован в учебной САПР PSAPRна ПЭВМ программой «Трассировка проводов» (режим алгоритм Форда-Фалкерсона). Программа позволяет:

- определять максимально возможное число проводов, которые можно уложить в заданное монтажное пространство;

- при укладке проводов учитывается пропускная способность каналов, в которые укладываются проводники.

Для запуска программы «Трассировка проводов» установить курсор на окно с этим названием (оно будет в зелёной рамке) и нажать Enter. Появится рабочее поле графического редактора «Трассировка проводов». Выбрать алгоритм Форда-Фалкерсона (рис.6.12).

 

Рис.6.12

 

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

· Экспериментальная часть.

1. Получить у преподавателя технические условия на проектирование жгутового монтажа.

2. Для заданного варианта электрических соединений (число проводов между контактами) и монтажного пространства (каналов в блоках) установить источник S и сток T. Для этого указать курсором точку на дискретном поле и нажать клавишу S. Это будет источник. Затем указать другую точку поля и нажать клавишу T –сток. После этого задать на дугах пропускные способности (цифрой 1 и потоки по дугам – цифрой 2) (рис.6.13).

Рис.6.13

 

3. Для заданной сети рассчитать максимальный поток по программе. Нажать клавишу Enter. На экране появится результат (рис.6.14).

4. Для заданной сети рассчитать максимальный поток вручную.

5. Начертить эскизы раскладки проводов в жгуты.

6. Оценить результаты трассировки проводов в жгуты по всем критериям и

проанализировать возможность “ручной” доработки полученного результата

или повторного решения с уточненными требованиями к трассировке.

7. Эффективность алгоритма трассировки проводов в жгуты оценить с точки зрения требований к математическому обеспечению САПР.

 

СОДЕРЖАНИЕ ОТЧЕТА

 

4.1. Цель работы.

4.2. Сведения из теории. Задача трассировки проводов в жгуты и ее матема-

тическая формулировка.

4.3. Графическое изображение на плоскости в декартовой системе координат множества контактов, подлежащих соединению.

Рис.6.14

 

4.4. Условия трассировки проводов в жгуты.

4.5. Графовая модель соединяемых контактов, необходимая для работы алгоритма Форда-Фалкерсона.

4.6. Результаты ручного и машинного расчётов максимального потока.

4.7. Эскиз (распечатка) результатов решения задачи раскладки проводов в жгуты.

4.8. Выводы.

 

КОНТРОЛЬНЫЕ ВОПРОСЫ

 

5.1. Сформулируйте цели задачи трассировки проводов в жгуты.

5.2. Как формулируется задача трассировки проводов в жгуты в терминах теории графов?

5.3. В чем суть алгоритма трассировки проводов в жгуты?

5.4. Каким образом можно оценить качество жгутового монтажа?

5.5. Перечислите последовательность действий алгоритма Форда-Фалкерсона.

5.6. Каким образом формулируется задача поиска максимального потока при нескольких источниках и стоках?

5.7. Назовите достоинства и недостатки алгоритма с позиций трассировки

проводов.

5.8. Поясните порядок работы с программой.