Компьютерные технологии проектирования

Общая схема алгоритмов такова. Искомое дерево строится постепенно: к изначально пустому множеству A на каждом шаге добавляется одно ребро.

Множество A всегда является подмножеством некоторого минимального дерева. Ребро (u,v), добавляемое на очередном шаге, выбирается так, чтобы не нарушить этого свойства.

Алгоритм Краскала: Рисуем граф, добавляем вес, на каждом этапе выбираем ребро с минимальным весом, так, чтобы не было циклов.

Алгоритм Прима: Формируем дерево из произвольной вершины. Далее выбираем ребро, не относящееся к этому дереву, с минимальным весом.

38. Алгоритм Дейкстры (нахождение кратчайшего пути в графе)

Алгоритм Дейкстры всякий раз выбирает для обработки вершины с наименьшей оценкой кратчайшего пути.

На каждой итерации выбирается вершина u, имеющая минимальное значение d (выделена серым цветом). (б-е) Вершина и с наименьшим значением d[u] изымается из очереди Q = V \ S и добавляется к множеству S (в первый раз имеем и = s), при этом могут измениться оценки d[v] вершин, смежных с u.

39. Алгоритм А* (нахождение кратчайшего пути в графе)

Итак, пусть g(v) - стоимость пути от источника до вершины v;

h(v) - нижняя оценка стоимости пути от вершины v до приемника (в качестве h(v) для данной задачи примем расстояние от вершины v до приемника);

f(v) = g(v) + h(v) - нижняя оценка стоимости пути от источника до приемника, проходящего через вершину v.

1) Среди вершин графа, граничащих с приемником, найти вершину v, имеющую наименьшую оценку f(v);

2) Если вершина v не граничит с источником определить среди вершин, достижимых из v, вершину v1 с наименьшей оценкой f1(v);

3) Если вершина v граничит с источником, она является единственной вершиной графа между источником и приемником;

4) Поиск прекращается, когда найдена вершина vn, граничащая с источником.

40. Алгоритм Ли (нахождение кратчайшего пути в решетчатом графе)

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

Пусть требуется найти путь в лабиринте от точки A до точки B. Запишем единицу в каждую пустую ячейку, являющуюся непосредственным соседом ячейки A (рис.2.6.b).

Затем во все пустые ячейки, которые соседствуют с ячейками, содержащими единицы, вписываются двойки. Затем за цифрами 2 записываются цифры 3 и т.д. Процесс продолжается до тех пор, пока не произойдет одно из двух событий:

· все пути окажутся заблокированными, т.е. на k-м шаге не останется пустых ячеек, соседствующих с ячейками, содержащими число (k - 1);

· будет достигнута ячейка, содержащая B. В последнем случае запускается «обратная волна» и легко определяется кратчайший путь (или пути) между точками A и B.

граф автоматизированный проектирование библиотека

41. Модификации алгоритма Ли

Недостатки алгоритма Ли:

· Волна распространяется во все стороны одинаково, и в результате в процессе трассировки производится множество совсем ненужных действий.

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

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

Другой вариант сокращения объемов вычисления - запуск волны во встречных направлениях от источника и приемника. Если два фронта сталкиваются в какой-то точке, то путь найден. Метод дает существенную экономию про времени работы алгоритма.

Есть ещё лучевой алгоритм, его смысл в том, если в алгоритме Ли сначала исследуются клетки соседи, а затем клетки наследники, то в лучевом алгоритме сначала изучаются наследники одного из соседей (например, соседа с самого перспективного направления). Таким образом, первоначально вместо волны образуется направленный луч.

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

42. Сеточные модели дискретного рабочего поля печатной платы

Еще один из способов ускорить работу волнового алгоритма - заставить волну распространяться неравномерно. Для этого вводится система штрафов за движение в неприоритетном направлении. На рис.2.9. и рис.2.10. представлены модели дискретного рабочего поля (ДРП) односторонней печатной платы с равнозначными и двусторонней ПП с неравнозначными стоимостями перемещения.

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

43. Этапы трассировки проводников на печатной плате. Алгоритмы, применяемые на разных этапах трассировки

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

Принято выделять четыре основных этапа трассировки:

1. Составление списка соединений.

2. Распределение соединений по слоям (задача расслоения) или зонам (макротрассировка).

3. Определение порядка трассировки для всех соединений.

4. Трассировка проводников.

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

44. Раскраска графов

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

Требуется раскрасить вершины в минимальное количество цветов таким образом, чтобы не было ни одного ребра, соединяющего вершины одного цвета. Отрезки, соответствующие одноцветным вершинам, назначаются в один слой.

Задача NP трудна и не решает проблемы, потому что число слоев обычно ограничено, а хроматическое число (минимальное число цветов) может оказаться больше заданного числа слоев, кроме того, не учитывается возможность перехода со слоя на слой в произвольном месте - это совсем другая задача.

Алгоритм раскраски графа по степеням вершин

Дано: G=(V,X) - связный граф. Требуется найти вершинную раскраску графа и приближенное значение хроматического числа K. Необходимо:

1. Вычислить степени вершин. Положить K=1. (степень - сколько смежных ребер)

2. Просмотреть вершины в порядке невозрастания степеней и окрасить первую неокрашенную вершину в цвет № K.

3. Просмотреть вершины в порядке невозрастания степеней и окрасить в цвет № К все вершины, которые не смежны вершинам, уже окрашенным в цвет №К.

4. Если все вершины окрашены, то К-искомое хроматическое число, Иначе К=К+1 и переход к пункту 2.

45. Сеточные, бессеточные и топологические методы трассировки

Прямоугольная сетка:

??требующаяся память и быстродействие напрямую не зависят от величины проекта (схемы): для одного и того же проекта уменьшение шага сетки ведёт к квадратичному увеличению числа её узлов (требуется большая память) и к квадратичному увеличению времени решения (уменьшается быстродействие);

??неэкономично используются ресурсы коммутационного пространства: если какая-либо деталь топологического элемента занимает лишь часть площади дискрета, то всё равно оккупируется весь дискрет; каждая трасса занимает весь дискрет целиком.

??существуют дополнительные сложности, связанные с непопаданием элементов топологии в сетку;

??происходит неоправданное увеличение длины трасс (проводятся два катета или ломаная вместо гипотенузы);

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

Модификации сетки: свободное для трасс монтажное пространство в виде множества отрезков (на одном слое горизонтальные, на другом - вертикальные), при фиксации трассы как совокупности фрагментов отрезков последние делятся на части.

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

Бессеточность.Shape-based трассировщики, например, SPECCTRA работают с геометрическими объектами (контактными площадками, переходными отверстиями и линейными фрагментами проводников), не раскладывая их в набор дискретов.

Триангуляция: число ячеек пропорционально числу элементов топологии, следовательно, размеры модели линейно зависят от размера проекта (числа контактов и т. п.), следовательно, достигается минимум памяти и максимум быстродействия. Но, к сожалению, в этой модели сложно (невозможно) учесть реальную геометрию элементов.

Топологический метод.

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

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

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

· Современные технологии обычно позволяют проводить дорожки между контактами элементов РЭА или под планарными контактами в другом слое. Отсутствие учёта такой возможности топологическим трассировщиком будет приводить к неоптимальным решениям из-за того, что чисто топологическая модель коммутационного пространства неадекватно отражает свойства реального конструктива.

46. Гибкая трассировка

Разбить рабочее поле на выпуклые многоугольные области (например, треугольники), в углах которых находятся контакты, и назвал свою модель дискретным топологическим рабочим полем,(ДТРП) а метод - методом гибкой трассировки.

Плюсы:

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

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

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

Гибкая трассировка изотропна, то есть не имеет никаких выделенных направлений и не подвержена «болезни ортогональности», проводники идут так, как им ближе.

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

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

47. Критерии качества монтажно-коммутационного проектирования

Суммарная длина соединений.

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

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

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

Равномерность заполнения монтажного пространства.

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

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

Пусть и - множества вертикальных и горизонтальных сечений, расположенных на монтажном пространстве

,

где и - соответственно числа вертикальных и горизонтальных сечений.

Есии

, считается, что в этом случае достигается равномерное распределение цепей в монтажном пространстве.

Существенным недостатком метода сечений является то, что при проведении сечения учитывается количество цепей, пересекаемых сечением, а не количество пересечений звеньев цепей с линией сечения.

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

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

48. Алгоритмы размещения элементов. Силовой алгоритм

В монтажном пространстве задана область, которая разбивается на множество позиций (посадочных мест) P = {p₁, p₂, …, p_q}, число которых должно быть не меньше числа размещаемых элементов. Очевидно, что каждый элемент может занимать не более одного посадочного места, расстояние между которыми описывается симметричной матрицей расстояний D = d_i,j. Имеющееся множество элементов X = {x₁, x₂, …, x_n}, связанных между собой множеством электрических цепей E = {e₁, e₂, …, e_m}, необходимо таким образом отобразить на множестве Р, чтобы обеспечивался экстремум целевой функции качества размещения.

Имеется множество элементов Е, множество позиций S = {S1,S2,…St}.

Алгоритм состоит из двух основных стадий:

1 стадия: выбор элемента

При t > n вводятся фиктивные элементы => t = n.

, - размещенные элементы и соответствующие им позиции;

, - свободные позиции, неразмещенные элементы.

выбор элемента из Е с , 2 стадия: размещение элементов на определенную позицию.

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

Функционал Ф, выражающий сумму квадратов длин проводников,

,

где x и y - координатные векторы для n ячеек, а представляет связность ячеек i и j.

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

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

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

49. Алгоритмы размещения элементов. Алгоритм Гото

Обозначим окрестность точки оптимума p_М для элемента М как е(p_М). Окрестность е(p_М) определяется как упорядоченный набор позиций, ближайших к p_М.

Пусть в точке оптимума, например, по критерию суммы квадратов длин соединений (5.1) элемента А находится элемент B, а мощность окрестности е(p_А) равна трем. Тогда проводятся три пробы замены первичного элемента: A-B, A-C, A-D, как показано на рис.5.7. Пробные замены элементов при л = 2 и е = 3.

Справа приведено дерево поиска при глубине поиска л = 2. Из трех парных замен для реализации принимается замена, приводящая к наибольшему сокращению длины соединений. Если ни одна из пробных замен не приводит к сокращению длины, то проводится следующий шаг поиска в дереве решений при л = 3.

Пусть увеличена глубина поиска, и элемент A перемещается на место B. Тогда вычисляется точка оптимума p_B и определяется окрестность е(p_B). Пусть в окрестности е(p_B) находятся элементы E,F и G. Тогда проводятся пробные замены A-B-E, A-B-F и A-B-G. На рис.5.8 показана замкнутая цепочка переносов, приводящая к наибольшему сокращению длины соединений.

Метод обеспечивает получение хороших локально-оптимальных решений за сравнительно небольшое время.

50. Алгоритм линейного размещения элементов

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

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

51. Размещение разногабаритных элементовП

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

Алгоритм

1. Определение множества всех позиций (положений) элементов на дискретной модели платы. Каждому элементу на плате соответствует множество позиций .

Количество позиций для прямоугольного элемента (причем возможны две ориентации элемента)

. (5.9)

Для квадратного элемента число позиций не зависит от ориентации и определяется по формуле

. (5.10)

2. Построение графа G(V,E), где множеству вершин соответствует множество позиций каждого из элементов на модели платы и две вершины из V соединяются ребром из E только в случае, если соответствующие им позиции элементов геометрически не пересекаются. Другими словами строится граф совместимости между параллельными вершинами.

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

Достоинством алгоритма является высокая точность решения, недостатком - большое время решения, обусловленное сложностью выделения в графе наибольших полных подграфов.

Размещено на Allbest.ru