XIV Міжнародна наукова інтернет-конференція ADVANCED TECHNOLOGIES OF SCIENCE AND EDUCATION

Русский English




Научные конференции Наукові конференції

к.т.н., Королев А.Г, Ганжа С.Н., Ганжа С.А., Иванов В.Г. О МИНИМИЗАЦИИ ЧИСЛА ПЕРЕХОДНЫХ ОТВЕРСТИЙ В ДВУХСЛОЙНЫХ ПЕЧАТНЫХ ПЛАТАХ ПРИ АВТОМАТИЗИРОВАННОМ ПРОЕКТИРОВАНИИ.

Доц., к.т.н., Королев А.Г, доц., Ганжа С.Н., Ганжа С.А., Иванов В.Г.

Технологический институт ВНУ им. В. Даля (г. Северодонецк)

О МИНИМИЗАЦИИ ЧИСЛА ПЕРЕХОДНЫХ ОТВЕРСТИЙ В ДВУХСЛОЙНЫХ ПЕЧАТНЫХ ПЛАТАХ ПРИ АВТОМАТИЗИРОВАННОМ ПРОЕКТИРОВАНИИ

Известны эвристические решения задачи размещения межслойных переходов. В отличие от них в данной работе исследуются точные методы, позволяющие по­лучить минимум числа переходных отверстий при заданном варианте совмещенной трассировки.

Содержательно задача ставится следующим образом. Пусть имеется вариант трассировки, выполненный условно в одном слое и содер­жащий пересечения цепей. Необходимо разме­стить межслойные переходы на цепях без из­менения конфигурации цепей, которые должны располагаться в двух слоях без пересечений, а число межслойных переходов должно быть минимальным. Обычно при трассировке эти требования дополняются еще условиями, огра­ничивающими места расположения межслой­ных переходов.

Рассмотрим формальную постановку задачи. Пусть задан плоский неориентированный мулътиграф. На его ребрах определим разбиение на два класса: ребра, разрешенные для межслойных переходов, и ребра, запрещенные для межслойных переходов. Определим на ребрах разбиение на ребра одной цепи, которое дол­жно быть таким, чтобы ребра каждого под­множества являлись связными. Каждое из этих подмножеств назовем цепью. Это понятие экви­валентно понятию «цепь» в варианте трассировки.

Указанный мультиграф (вместе с определен­ными реберными разбиениями) будем назы­вать графом двухслойной трассировки, если все кратные ребра запрещены для межслойных переходов и каждой вершине инцидентны ребра, принадлежащие не более чем двум цепям. На графе трассировки, следуя, определим понятие границы грани, т. е. связного множест­ва ребер, ограничивающих грань.

Для рассматриваемого метода размещения межслойных переходов важным понятием является четность числа переходов с цепи на цепь на границе. Будем говорить, что в границе произошел переход с цепи на цепь, если два смежных ребра границы принадлежат разным цепям графа, и что граница грани четна, если она имеет четное число переходов с цепи на цепь, и нечетна в противном случае.

Сформулируем следующую теорему. Цепи графа трассировки размещаются в двух слоях без пересечений тогда и только тогда, когда все границы граней в графе четны. Доказа­тельство следует из анализа четных и нечетных границ графа трассировки.

Рассмотрим трассировку в двух слоях с межслойными переходами вне узловых точек це­пей. К межслойному переходу цепь может под­ходить в одном слое или в разных слоях. Ина­че говоря, каждый такой межслойный переход разрезает цепь на две части. На графе трас­сировки такие межслойные переходы эквива­лентны разрезу ребра и слиянию двух приле­жащих к нему границ. При слиянии двух гра­ниц суммарное число их переходов с цепи на цепи равно числу переходов в результирующей границе. Таким образом, для размещения це­пей в двух слоях без пересечений необходимо ввести такие разрезы ребер графа, чтобы все полученные границы стали четными. Разре­жем ребра графа трассировки так, чтобы по­лучить одну границу; согласно теореме эта граница четна. Следовательно, в любом графе будет четное число нечетных границ.

Разобьем вершины графа трассировки на два подмножества: узлы и пересечения. Вер­шину графа назовем узлом, если ей инцидент­ны ребра одной цепи; в противном случае она называется пересечением. Эти понятия эквива­лентны понятиям «узел» и «пересечение» в варианте трассировки. Для графа трассировки построим двойственный граф, для чего сопоставим каждой границе грани вершину двой­ственного графа. Для каждого ребра графа трассировки определим пару границ, в кото­рых оно содержится, и соединим ребром соот­ветствующую пару вершин двойственного гра­фа. Вершины этого графа будем называть чет­ными или нечетными в зависимости от четнос­ти соответствующей границы грани в графе трассировки.

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

 Каждая ребро двойственного графа соответствует ребру модельного графа, которое соединяется ровно с одной вершиной каждого из двух подграфов. Ребра  внутри подграфа, соединяют каждую вершину подграфа с каждой другой в подграфе. Внутренние ребра получают вес равный нулю, а остальные ребра - сохраняют прежний вес ( как правило, равный 1).  Так как в  максимальном паросочетании минимального веса для такого графа, суммарный вес ребер с ненулевым весом  будет таким же, как в задачи о покрытии, то задача о покрытии - эквивалентна  задаче о паросочетании на модельном графе. 

Очевидно,  что каждому подграфу будет инцидентно четное или нечетное число ребер с ненулевым весом, в зависимости от того, к какому классу, четных или нечетных была отнесена вершина двойственного графа.   Все остальные вершины каждого подграфа можно будет покрыть ребрами  с нулевым весом.

Итак, ребра с ненулевым весом в модельном графе, можно интерпретировать как ребра искомого покрытия.

Естественно, польза от такого сведения будет только в том случае, если встроить работу с подграфами прямо в алгоритм построения паросочетания, что и предлагается автором.

Задача построения соответствующего паросочетания является достаточно трудоемкой, несмотря на то, что ребра, как правило, имеют всего 2 варианта веса, 0 или 1. Эта задача  может быть реально решена только для сравнительно небольшого числа вершин ( несколько тысяч).

Поэтому в качестве альтернативы, предлагается приближенный алгоритм, основанный на идеях алгоритма Форда для ориентированных графов, который работает непосредственно  с двойственным графом.

Рассмотрим двойственный граф с весами на ребрах. Вначале все ребра графа вне покрытия. Ребра, которые отнесены к покрытию, будем учитывать, изменяя знак их веса. Построим для нечетной вершины дерево кратчайших путей в соответствии с алгоритмом Форда, запрещая переходы по дереву непосредственно в ту вершину, откуда мы попали в данную вершину. Если в процессе построения дерева будут возникать циклы с отрицательным весом, то в этом цикле поменяем  все ребра покрытия, на ребра вне покрытия и наоборот, естественно, изменяя знак у веса ребер цикла. После чего старое дерево разрушаем и переходим к построению нового дерева с корнем в прежней вершине.

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

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

Данный алгоритм обычно дает точное решение задачи, и способен обрабатывать графы с десятками тысяч вершин, что подтверждается экспериментами с программой на языке DELPHI для персонального компьютера.


Залиште коментар!

Дозволено використання тегів:
<a href="" title=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <code> <em> <i> <strike> <strong>