close

Вход

Забыли?

вход по аккаунту

?

Laba 6 - копия Ю

код для вставкиСкачать
Ульяновский государственный технический университет
Кафедра Проектирования и технологии электронных средств
Лабораторная работа №6
ИССЛЕДОВАНИЕ ЭФФЕКТИВНОСТИ АЛГОРИТМА ТРАССИРОВКИ ПРОВОДОВ В ЖГУТЫ
Студент гр. Рбд-31 Преподаватель:
Грохин Ю. А. Мактас М.Я.
Ульяновск 2013
Цель работы - исследовать эффективность алгоритма трассировки соединений в жгуты; освоить особенности алгоритмизации и программирования задачи трассировки проводов на современных ПЭВМ алгоритмом Форда-Фалкерсона; приобрести навыки построения математических моделей проводных соединений, реализации и исследования их при решении задачи трассировки с применением САПР.
1. ЗАДАЧА О МАКСИМАЛЬНОМ ПОТОКЕ
Одной из наиболее интересных и важных задач теории графов является задача определения максимального потока, протекающего от некоторой вершины s (источника) графа к некоторой конечной вершине t (стоку). При этом каждой дуге графа G приписывается некоторая пропускная способность , определяющая наибольшее значение потока, который может протекать по данной дуге.
Метод решения задачи о максимальном потоке был предложен в 1962 г. американскими учеными Фордом и Фалкерсоном. Предложенная "техника пометок" составляет основу других алгоритмов решения многочисленных задач, являющихся простыми обобщениями или расширениями указанной задачи.
Эта задача и ее варианты часто возникают на практике. При конструировании РЭС с ней сталкиваются при проектировании жгутового монтажа, при канальной трассировке печатных и пленочных соединений.
В этом случае проводники укладываются в нормализованные каналы, расположенные в монтажном пространстве узлов во взаимно перпендикулярных направлениях (рис. 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.
Документ
Категория
Рефераты
Просмотров
36
Размер файла
968 Кб
Теги
лабораторная работа, копия, лаба, laba, лабораторная
1/--страниц
Пожаловаться на содержимое документа