В качестве первого размещённого элемента примем разъём Х1 (позиция 1)

2.2.1 В качестве первого размещённого элемента примем разъём Х1 (позиция 1)

Рассчитываем коэффициенты относительной внешней связанности по формуле (8).

  

  

  

 .

На данном этапе будем размещать элемент с максисальным значением Ф_i, т. е. микросхему DD11.

Рассчитываем прирощение функции цели для незанятых ячеек печатной платы по формуле (9).

ΔF₂=2 ΔF₃=2 ΔF₄=2 ΔF₅=4 ΔF₆=4 ΔF₇=4 ΔF₈=6 ΔF₉=6 ΔF₁₀=6 ΔF₁₁=8 ΔF₁₂=8.

Выбираем минимальное значение F_i,т. е. вторую.

2.2.2.В качестве первого размещённого элемента примем разъём Х1 (позиция 1) и DD11 (позиция 2)

Рассчитываем коэффициенты относительной внешней связанности по формуле (8).

  

  

  

.

На данном этапе будем размещать элемент с максисальным значением Ф_i, т. е. микросхему DD1.

Рассчитываем прирощение функции цели для незанятых ячеек печатной платы по формуле (9).

ΔF3=С1х1d13+C111d23=3*1+3*1=6;

ΔF4= С1х1d14+C111d24=3*1+3*2=9;

ΔF5= С1х1d15+C111d25=3*2+3*1=9;

ΔF6= С1х1d16+C111d26=3*2+3*2=12;

ΔF7= С1х1d17+C111d27=3*2+3*3=15;

ΔF8= С1х1d18+C111d28=3*3+3*2=15;

ΔF9= С1х1d19+C111d29=3*3+3*3=18;

ΔF10= С1х1d110+C111d210=3*3+3*4=21;

ΔF12= С1х1d112+C111d212=3*4+3*4=24;

Выбираем минимальное значение F_i,т. е. третью.

Результаты размещения

Микросхема	Номер посадочного места
Х1	1
DD1	3
DD2	4
DD3	8
DD4	9
DD5	5
DD6	6
DD7	7
DD8	10
DD9	11
DD10	12
DD11	2

3. Трассировка цепей питания и земли с использованием алгоритма построения кратчайших связывающих цепей

Трассировка – прокладка электрических трасс, проводов (при проводном монтаже), дорожек.

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

Алгоритм Краскала (цепи земли)

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

-            ребро минимально

-            ребро инцидентно только по одной вершине

-            присоединение рассматриваемого ребра не приводит к повышению степени любой вершины больше заданного числа

Последовательность:

-            на множестве вершин строится полный граф, задаются матрица расстояний

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

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

1)         Матрица расстояний

x1	DD11	DD5	DD3	DD9
	DD1	DD6	DD4	DD10
	DD2	DD7	DD8

Рис.4

Матрица длин

	1	2	3	4	5	6	7	8	9	10	11	12	p
1	0	1	1	1	2	2	2	3	3	3	4	4	30
2	1	0	1	2	1	2	3	2	3	4	3	4	31
3	1	1	0	1	2	1	2	3	2	3	4	3	27
4	1	2	1	0	3	2	1	4	3	2	5	4	31
5	2	1	2	3	0	1	2	1	2	3	2	3	26
6	2	2	1	2	1	0	1	2	1	2	3	2	22
7	2	3	2	1	2	1	0	3	2	1	4	3	26
8	3	2	3	4	1	2	3	0	1	2	1	2	27
9	3	3	2	3	2	1	2	1	0	1	2	1	23
10	3	4	3	2	3	2	1	2	1	0	3	2	27
11	4	3	4	5	2	3	4	1	2	3	0	1	29
12	4	4	3	4	3	2	3	2	1	2	1	0	30

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

 

В результате трассировки цепей земли будет иметь вид:

x1	DD11	DD5	DD3	DD9
	DD1	DD6	DD4	DD10
	DD2	DD7	DD8

Рис.5

Алгоритм Прима (цепи питания)

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

1)         матрица расстояний используется та же, что и в алгоритме Краскала (см. выше)

2)         выбирается произвольно вершина (например № 1), где минимум элемент

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

x1	DD11	DD5	DD3	DD9
	DD1	DD6	DD4	DD10
	DD2	DD7	DD8

Рис.6