Лекция 23. Последовательный и итерационный алгоритмы размещения конструктивных модулей на плате
Пример. Произвести размещение элементов с помощью алгоритма последовательного размещения для приведенной схемы и коммутационного поля.
|
Позиции, запрещенные |
Цепь 1 |
для размещения |
|
Цепь 2
1 |
2 |
2 |
|
|
Цепь 3
1 |
3 |
4 |
Цепь 4
3
Матрица относительных расстояний в ортогональной метрике
|
|
1 |
|
2 |
|
3 |
4 |
d |
|
Вектор очередности |
|
|
||||
|
1 |
0 |
|
|
2 |
|
1 |
2 |
5 |
|
|
|
||||
|
|
|
|
|
позиций для размещения |
|
||||||||||
|
2 |
2 |
|
|
0 |
|
1 |
2 |
5 |
|
|
|||||
|
|
|
|
|
3;1;2;4 |
|
|
|
|
|||||||
|
3 |
1 |
|
|
1 |
|
0 |
1 |
3 |
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|||||||
|
4 |
2 |
|
|
2 |
|
1 |
0 |
5 |
|
|
|
|
|
|
|
c |
100 |
|
|
100 |
|
100 |
|
116 |
1 |
2 |
3 |
с |
||||
|
|
|
|
|||||||||||||
12 |
|
|
|
|
|
3 |
|
|
|
3 |
|
1 |
0 |
116 |
33 |
149 |
|
2 |
|
|
|
|
|
|
|
|
|||||||
c |
100 |
|
33 |
|
|
|
|
|
2 |
116 |
0 |
83 |
199 |
|||
13 |
|
|
|
|
|
|
|
|
|
|
|
|||||
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
c23 |
100 |
|
|
|
100 |
|
83 |
|
3 |
33 |
83 |
0 |
116 |
|||
|
|
|
|
|
2 |
|
|
|
|
|
|
|
||||
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Вектор назначения элементов на позиции: 2;1;3 Решение на 1 позиции – первый элемент; на второй – третий элемент; на третей – второй элемент; четвертая позиция – пустая.
Итерационные алгоритмы размещения
В случае минимизации суммарной взвешенной длины соединений формула для расчета изменения значения целевой функции при перестановке местами элементов ri и rj , закрепленных в позициях tf и tg, имеет вид:
k |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
Fij ( f , g) (cip c jp )(d fh( p) |
d gh( p) ) |
||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
p 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
h |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
где p и h(p) – |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rp |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
порядковый номер и |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||
позиция закрепления |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
f |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
g |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||
неподвижного |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
ri |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
rj |
|
|
|
|
|
|
||||||||||||||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
элемента rp |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Лекция 24 Трассировка соединений
Волновой алгоритм Ли
h
h
h
Ячейки коммутационного поля.
Веса ячеек часто оцениваются по формуле:
Pk Pk 1 |
( f1, f2 ,..., fg ) |
где Pk и Pk-1 - веса ячеек |
|
|
k-го и (k-1)-го фронтов; |
( f1 , f f |
,..., f g ) -весовая функция, являющаяся |
|
|
показателем качества проведения пути |
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
|
1 |
3 |
2 |
1 |
0 А |
1 |
|
|
|
|
|
2 |
4 |
3 |
2 |
1 |
2 |
|
|
|
|
– свободная ячейка |
3 |
5 |
4 |
3 |
|
|
|
|
|
|
|
4 |
6 |
5 |
4 |
|
10 В |
|
|
|
|
– занятая ячейка |
5 |
7 |
6 |
5 |
|
9 |
10 |
|
|
|
|
6 |
8 |
7 |
6 |
7 |
8 |
9 |
|
|
|
– соединяемые ячейки |
7 |
9 |
|
|
|
|
|
|
|
|
|
8 |
10 |
|
|
|
|
|
|
|
|
|
|
|
|
|
Распространение волны на ДРП |
|
|||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
1 |
1 |
|
А |
|
|
|
|
|
2 |
2 |
|
|
|
|
|
|
|
3 |
3 |
|
|
|
|
|
|
|
4 |
4 |
|
|
В 10 |
|
|
|
|
5 |
5 |
|
|
9 |
|
|
|
|
6 |
6 |
|
7 |
8 |
|
|
|
|
7 |
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
|
Трасса пути (пунктиром |
|
|||||
|
|
|
показан другой путь). |
|
|
|||
Лекция 25 Модифицированные волновые алгоритмы.
Лучевые алгоритмы трассировки
1
2
3
4
5
6
7
8
|
|
|
|
|
|
Метод путевых координат |
|
|
|
||||||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
|
|
|
A |
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
A |
|
|
|
|
|||||||
|
|
|
|
|
|
|
2 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
3 |
|
|
|
|
|
|
|
|
|
|
|
|
B |
|
|
4 |
|
|
|
|
B |
|
|
|
|
|
|
|
|
|
|
5 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
6 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
7 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
8 |
|
|
|
|
|
|
|
|
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
1 |
3 |
2 |
1 |
А |
1 |
|
|
1 |
2 |
1 |
3 |
2 |
1 |
2 |
|
|
2 |
3 |
2 |
1 |
3 |
|
|
|
|
3 |
4 |
3 |
2 |
1 |
|
1 В |
|
|
4 |
5 |
1 |
3 |
2 |
|
3 |
1 |
|
5 |
6 |
2 |
1 |
3 |
1 |
2 |
3 |
1 |
6 |
7 |
3 |
|
|
|
|
|
|
7 |
8 |
1 |
|
|
|
|
|
|
8 |
|
|
|
Кодирование весов |
|
||||
|
|
|
|
модулю 3. |
|
|
||
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
2 |
1 |
1 |
А |
1 |
|
|
|
2 |
2 |
1 |
1 |
1 |
|
|
|
1 |
2 |
2 |
|
|
|
|
|
1 |
1 |
2 |
|
1 В |
|
|
|
2 |
1 |
1 |
|
1 |
1 |
|
|
2 |
2 |
1 |
2 |
2 |
1 |
1 |
|
1 |
|
|
|
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
Разметка ДРП по Акерсу. |
|||||