Все из лекции 4-5

31. Особенности алгоритмов размещения при многоцелевой оптимизации модулей

Мб лк 3 но там дрочь

32. Классификация алгоритмов трассировки





33. Формулировка задачи трассировки проводных соединений

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

М = {m1, m2,..., mn}.

В соответствии с электрической схемой соединений разобьем множество М на непересекающиеся подмножества М(1), М(2),..., М(Р), каждое из которых включает в себя выводы, подлежащие электрическому объединению.

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

34. Алгоритм Краскала (Вайнберга – Лобермана)

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

Пусть в некоторой системе координат XYZ задано местоположение множества точек.

М = {m1, m2,..., mn}.

1. Строим на множестве М полный граф Gn(M, U).

2. Вычисляем длину всех ребер графа Gn(M, U)

3. Упорядочиваем список ребер с точки зрения их длины так, чтобы выполнялось условие

,

- построения кортежа с возрастанием длины каждого очередного ребра

4. Для построения дерева необходимо выбрать n-1 ребер из кортежа, которые не образуют циклов.

Существуют 2 процедуры для решения п. 4

Вариант 1 (параллельный).

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

---

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

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

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

Вариант 2 (последовательный).

На каждом шаге просматривают список ребер (начиная с первого) и к строящемуся поддереву присоединяют то ребро, которое:

а) еще не включено в решение;

б) присоединяет к поддереву новую вершину (один из концов ребра должен принадлежать вершине поддерева, другой —изолированной вершине)

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

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

35. Алгоритм Прима

Позволяет организовать просмотр только тех ребер графа Gn(M, U), которые связывают вершины строящегося поддерева с новыми, еще не присоединенными вершинами.

Возможно дополнительное ограничение на локальные степени вершин связывающей сети:



Шаги алгоритма:

1) любая произвольная вершина m € M соединяется с ближайшей соседней, образуя исходное поддерево.

Для определенности построения КСС можно начинать с ребра, инцидентного вершине m1.

2) На каждом последующем шаге к строящемуся поддереву присоединяют очередное ребро минимально возможной длины, связывающее новую, еще не присоединенную вершину mj с одной из вершин поддерева mi , локальная степень которой





- длина ребра, соединяющего вершины

1) составляем матрицу длин, общий элемент которой dij равен расстоянию между i-й и j-й точками (N - число объединяемых вершин):



2) Просматриваем элементы первой строки матрицы D и находим минимальный из них. Пусть таким элементом оказался элемент g-гo столбца, тогда весь первый и g-й столбцы матрицы D исключаем из рассмотрения, а первое соединение проводим между точками

---

m1 и mg.

3) Просматриваем первую и g-ю строки матрицы с оставшимися элементами. Из элементов этих строк находим минимальный. Предположим, что им оказался элемент, принадлежащий k-му столбцу. Если этот элемент находится на пересечении с первой строкой, то точку mk соединяем с mi, если же он находится на пересечении c g-й строкой, то точку mk соединяем с mg, после чего из матрицы D исключаем все элементы k-го столбца.

4) Просматриваем первую, g-ю и k-ю строки и т.д.

Выполнение ограничения на локальную степень вершин обеспечивается проверкой в каждой просматриваемой i-й строке числа уже выбранных для построения КСС элементов K(i). При K(i) = k все оставшиеся элементы i-й строки исключаются из рассмотрения.

36. Особенности трассировки проводов в каналах







37. Трассировка печатных соединений. Постановка задачи

1) своими координатами (х, у) множество конструктивных элементов
Х = {х1, х2, ..., хt}.

2) множество из L связных подмножеств:

С = {C1, C2, ..., CL},

где каждое l-е подмножество Сl объединяет Nl выводов конструктивных элементов из множества R в соответствии с принципиальной электрической схемой.

3) требования, предъявляемых к топологии платы:

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

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

Сl  С

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

Задача трассировки печатных соединений в общем виде:

1)построение бесперекрестного минимального леса

2)отыскание кратчайшего пути между его вершинами (трассировка соединений).

все методы построения минимальных связывающих деревьев не учитывают

- ограничения на размеры монтажного поля

- толщину печатных проводников

- величину зазора между ними.

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

---

• 
  Трассировку соединений осуществляют с помощью алгоритмов, основанных на методах динамического программирования.
  

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

• 
  Минимальные размеры ячеек обусловливаются объемом памяти компьютера и соотношением
  

где d - расстояние между центрами соседних ячеек; bn - минимальная ширина печатного проводника; l -минимальное расстояние между соседними проводниками.

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

38. Ортогональные алгоритмы трассировки

Трассировка печатных соединений по прямым, параллельным осям координат монтажного пространства поочередно для каждой координаты.

При встречи препятствия трасса меняет свое направление на 90⁰. (для МПП – вставляется переходное отверстие)

Достоинства алгоритма:

- обладают самым большим быстродействием

(реализация их на компьютере требует в 75—100 раз меньше вычислений по сравнению с волновыми алгоритмами).

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

- получение большого числа переходов со слоя на слой,

- отсутствие 100%-ной гарантии проведения ряда трасс,

- большое число параллельно идущих проводников.

1) Определяем приоритетное направление (например по х)

2) х_i-х_к= Δх.

3) Перемещаемся по оси х от начальной к конечной точке. Целевая функция Δх →0. При y=const.

4) х₀-х_к= Δх_к =3

5) х₁-х_к= Δх_к-1 =2

6) Движение по х невозможно. Меняем направление..

7) Перемещаемся по оси y от текущей к конечной точке. Целевая функция
Δy →0.

8) y₀-y_к= Δy_к =3

9) y₁-y_к= Δy_к-1 =2

9) y₂-y_к= Δy_к-2 =1

10) y₃-y_к= Δy_к-3 =0

11) Движение по y прекращаем, тк. . Δy=0

Меняем направление..

12) Перемещаемся по оси x от текущей к конечной точке. Целевая функция
Δx →0. При x=const.

13) х₁-х_к= Δх_к-1

---

=2 … и т.д.

39. Волновой алгоритм Ли

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

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

Остальные - свободные

Для построения трасс возможно использовать только свободные ячейки

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

Первую ячейку, в которой зарождается волна влияний, называют источником,

а вторая соединяемая точка - приемник.

Фронту волны влияния на каждом этапе присваивают некоторый вес



где Pk и Рk-1 ‑ веса ячеек k-го и (k‑1)-го фронтов;

Ψ(f1,f2, …,fg) ‑ весовая функция, являющаяся показателем качества проведения пути, каждый параметр которой fi(i = 1, 2, ...,g) характеризует путь с точки зрения одного из критериев качества (длины пути, числа пересечений и т.п.).

Ограничение на вес фронта волны: веса ячеек предыдущих фронтов не должны быть больше весов ячеек последующих фронтов

1) Фронт распространяется только на соседние ячейки, которые имеют с ячейками предыдущего фронта либо общую сторону (хотя бы одну общую точку).

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

3) При достижении приемника осуществляют «проведение пути» - движении от приемника к источнику по пройденным на этапе распространения волны ячейкам, следя за тем, чтобы значения веса волны монотонно убывали

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

Каждое направление кодируют двоичным числом по mod q, где q - число просматриваемых соседних ячеек (двухбитным или трехбитным)

Чем меньшее значение путевой координаты - тем более предпочтительно это направление.

---

Смотрите также файлы

• Курсовая работа по теме Законность и правопорядок.docx

• В ходе войны можно выделить 3 периода.docx

• И. Кант немецкий философ, считается основателем классической немецкой философии. Кратко охарактеризуем этические принципы Канта.docx

• Генеральная ассамблея оон подготовила студентка 4курса группы ю111б.pptx

• .doc