Ульяновский государственный технический университет

Кафедра Проектирования и технологии электронных средств

Лабораторная работа №6

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

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

Студент гр. Рбд-31 Преподаватель:

Грохин М. Я.

Ульяновск 2013

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

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

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

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

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

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

НЕ нашли? Не то? Что вы ищете?

6-1

Рис. 6.1.

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

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

. (6.1)

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

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

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

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

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

(6.2)

Здесь .

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

. (6.3)

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

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

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

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

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

Рассмотрим работу алгоритма на примере графа с одним источником aS и одним стоком at, обобщив затем его для задач с несколькими AS и AT.

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

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

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

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

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

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

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

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

АЛГОРИТМ

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

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

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

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

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

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

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

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

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

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

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

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

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

2. Практические решения

Рисунок 2, а.

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

Рисунок 2, б.

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

Требуется уложить максимально возможное количество проводов в жгут между контактами, учитывая размеры каналов и сечения проводов. Размер схемы 2x3 узла.

2.1. Ручная трассировка

Возьмем крайние шесть контактов и представим схему в виде графа (рис. 2.1, а), в котором узлы заданы вершинами, а каналы ребрами. Зададим пропускные способности ребер.

СS1= 3:0 С23= 2:0 С3T= 4:0 С13= 6:0 С24= 3:0 СS2= 2:0 С4T= 4:0

В начальный момент потоки по дугам пока равны нулю – .

Рисунок 2.1, а.
Граф узла

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

Присваиваем вершине aS пометку [S+,∞].

Вершина aS имеет две смежные вершины, а1 и а2. Рассмотрим смежные вершины в порядке возрастания их номеров.

Сначала а1. Она получает пометку [S+,3] , поскольку (cs1 - xs1) = (3-0)=3 >0 и ε(1)=min[ε(S); (cs1 - xs1)] = min[∞;3] = 3.

Рассмотрим а2. Она получает пометку [S+,2].

Вершины a1 и а2 помечены, но не просмотрены.

Идем к вершине а1, смежные с ней вершины aS и а3.

Вершина aS уже помечена, поэтому рассматриваем вершину а3.

Она получает пометку [1+, 3] , поскольку (c13 – x13) = (6-0)=6 >0 и ε(3)=min[ε(1); (c13- x13)] = min[3;6] = 3

Вершина а3 помечена, но не просмотрена.

Идем к вершине а2, смежные с ней вершины aS и а4. Пометить мы можем только вершину а4, т. к. вершина aS уже помечена.

Она получает пометку [2+, 2] , поскольку (c24 – x24) = (3-0)=3 >0 и ε(4)=min[ε(2); (c24- x24)] = min[2;3] = 2

Вершина а4 помечена, но не просмотрена.
Все смежные вершины с а1 и а2 помечены, но не просмотрены.

Возвращаемся к вершине а3, смежные с ней вершины aT и а2. Пометить мы можем только вершину aT, т. к. вершина a2 уже помечена и просмотрена.

Она получает пометку [3+, 3] , поскольку (c3T – x3T) = (4-0)=4 >0 и ε(T)=min[ε(3); (c3T – x3T)] = min[3;4] = 3

Вершина аT помечена.

Сток получает метку [3+,3]. Исходный граф с помеченными вершинами приведен на рис. 2.1, б.

Рисунок 2.1, б.

Исходный Граф с помеченными вершинами

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

Поскольку сток aT имеет пометку [3+,3], то увеличиваем x3T на три единицы. В результате получаем x3T’ = x3T + 3 = 3 . Переходим к узлу a3, пометка которого [1+,3]. Увеличиваем x13 на 3. Получаем x13’ = x13 + 3= 3. Переходим к узлу а1, имеющему метку [S+,3]. Увеличивается поток по дуге xS1 на три единицы, и получаем xS1’= xS1 + 3 = 3.

После этого стираем все метки при вершинах и меняем текущие потоки по дугам x3T,x13,xS1.

Граф с измененным по нему потоком указан на рис. 2.1, в. После этого стираем все метки при вершинах и меняем текущие потоки по дугам,. Попытаемся вновь увеличить поток в графе.

Рисунок 2.1, в.

Граф с измененным потоком

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

Вершина aS вновь получает метку . Смежную с ней вершину а1 пометить не удается, т. к. (cs1 - xs1) = (3-3)= 0. У вершины а2, как и прежде, метка будет [S+,2] . Поскольку а1 метки не получила, рассматриваем а2. Смежные с ней вершины a3 и а4.

Вершина а3 получает пометку [2+, 2] , поскольку (c23 – x23) = (2-0)=2 >0 и ε(3)=min[ε(2); (c23- x23)] = min[2;2] = 2

Вершина а3 помечена, но не просмотрена.

Вершина а4 получает пометку [2+, 2] , поскольку (c23 – x23) = (3-0)=3 >0 и ε(4)=min[ε(2); (c24- x24)] = min[2;3] = 2

Вершина а4 помечена, но не просмотрена.

Рассмотрим вершину а4 , смежные с ней вершины aT и а2.

Пометить мы можем только вершину aT, т. к. вершина a2 уже помечена и просмотрена.

Вершина аT получает пометку [4+, 2] , поскольку (c4T – x4T) = (4-0)=4 >0 и ε(T)=min[ε(4); (c4T- x4T)] = min[2;4] = 2

Далее в порядке возрастания номеров перейдем к вершине а3. Она имеет две смежных вершины – а1 и аT. Присвоим им метки: а1 получит , « 3 » – это номер вершины а3, « – » – потому что поток x13 = 3>0 направлен в направлении противоположном порядку рассмотрения вершин – от а3 к а1. Величина второго числа метки в данном случае ε(1)=min[ε(3); (c13-(-x13)] = min[2;9] = 2

Вершина а1 помечена.

Граф с помеченными вершинами приведен на рис. 2,1 г.

Рисунок 2,1 г.

Граф с помеченными вершинами

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

В связи с тем, что сток aT получил метку, переходим к обратному ходу алгоритма. Метка у aT [4+, 2], поэтому x4T’ = x4T + 2 = 2. Переходим к узлу а4, имеющему метку [2+, 2]. Также увеличивается поток по дуге x24 на две единицы, и получаем x24’= x24 + 2 = 2.

Переходим к узлу а2, имеющему метку [S+, 2]. Также увеличивается поток по дуге xS2 на две единицы, и получаем xS2’= xS2 + 2 = 2.

Увеличения потоков от вершины а2 к а3 и а3 к а1 не рассматриваются, так как нарушается условие сохранения потока.

После обратного хода алгоритма окончательный граф с измененным потоком показан на рис. 2.1, д.

Повторная расстановка меток уже не приводит к пометке стока aT, т. к. ни одна из соседних с aS вершин не может быть помечена. Следовательно, максимальный поток в графе X max = 5.

Рисунок 2.1, д.

Окончательный граф с измененным потоком

В рассмотренную конструкцию узла (рис. 2.1, а.) можно уложить жгут максимум из пяти проводов (рис. 2.1, е.).

Рисунок 2.1, е.

Конструкция узла РЭС

Для сравнения результата ручной трассировки с машинной, проведем машинную трассировку для выбранных шести контактов на ПЭВМ.

Рисунок 2.1, ж.

Результат машинной трассировки для выбранных шести контактов(фотография)

В результате машинной трассировки максимальный поток в графе X max = 5.

3. Машинная трассировка (для всех контактов)

Рисунок 3, а.

Результат машинной трассировки для всех контактов(фотография)

В результате машинной трассировки проводов для 12 контактов максимальный поток в графе получился равным X max = 7.

Вывод:

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