Домашнее задание, страница 3

Перерисуем схему, пронумеровав все цепи:

Рис.19. Пронумерованные цепи схемы

Построим матрицу связности:

Вычислим вектор внешних связей элементов:

Используем последовательный алгоритм размещения.

Введем более удобные обозначения, пусть:

e1 = DD1

e2 = DD2

e3 = DD3

e4 = DD4

e5 = R1

e6 = R2

e7 = C1

e8 = C2

e9 = X1

1. Выбираем первый элемент по связности с элементами – наиболее связанный элемент e3 размещаем в середину монтажного пространства платы – 5 позицию.

Тогда массив элементов J_k={e3}, а массив позиций T_k = {t5}.

2. Находим индекс очередного размещаемого элемента по максимальной связности со всеми размещенными элементами – по матрице связности R.

3 строка матрицы R – {½; ½; 0; 1; ½ ; ½; ½; ½; 1}.

Элемент e3 со значением 1 связан с е4, e9. Выберем следующий размещаемый элемент – е9, т.к. у этого элемента связь с КГ равна 2, в отличии от e4, у которого связь с КГ равна 1. Поэтому e9 размещаем в позицию 1.

Тогда массив элементов J_k={e3, е9}, а массив позиций T_k = {t5, t1}.

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

3 строка матрицы R – {½; ½; 0; 1; ½ ; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0 ; 0; ½; ½; 0}.

Можно выбрать элементы – е4, e7, e8. Выберем элемент e7.

Определим позицию для установки этого элемента. Возможные позиции – 2, 4, 6, 8.

f₂ = r₃₇ d₅₂ + r₉₇ d₁₂ + m₂ h₇= ½*1 + ½*1+2*1=3

f₄ = r₃₇ d₅₄ + r₉₇ d₁₄ + m₄ h₇= ½*1 + ½*1+1*1=3

f₆ = r₃₇ d₅₆ + r₉₇ d₁₆ + m₆ h₇= ½*1 + ½*3+3*1=5

f₈= r₃₇ d₅₈ + r₉₇d₁₈ + m₈ h₇= ½*1 + ½*3+2*1=4

f₂ = min[f₄; f₆; f₈; f₂] = 3, размещаем элемент e7 в позицию 2. Тогда массив элементов J_k={e3, е9, e7}, а массив позиций T_k = {t5, t1, t2}.

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

3 строка матрицы R – {½; ½; 0; 1; ½ ; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0 ; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0 ; 0; 0; 0; ½}.

Можно выбрать элементы – е4, e8. Выберем элемент e8.

Определим позицию для установки этого элемента. Возможные позиции –3, 4, 6, 8.

f₃ = r₃₈ d₅₃ + r₉₈ d₁₃ + r₇₈ d₂₃ + m₃ h₈= ½*2 + ½*2+ 0*1+3*1=5

f₄ = r₃₈ d₅₄ + r₉₈ d₁₄ + r₇₈ d₂₄ + m₄ h₈= ½*1 + ½*1+ 0*2+1*1=2

f₆ = r₃₈ d₅₆ + r₉₈ d₁₆ + r₇₈ d₂₆ + m₆ h₈= ½*1+ ½*3+ 0*2+3*1=5

f₈= r₃₈d₅₈ + r₉₈d₁₈ + r₇₈ d₂₈ + m₈ h₈= ½*1 + ½*3+ 0*2+2*1=4

f₄ = min[f₄; f₆; f₈; f₃] = 2, размещаем элемент e8 в позицию 4. Тогда массив элементов J_k={e3, е9, e7, e8}, а массив позиций T_k = {t5, t1, t2, t4}.

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

3 строка матрицы R – {½; ½; 0; 1; ½ ; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0 ; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0 ; 0; 0; 0; ½}.

8 строка матрицы R – {0; 0; ½; 0; 0 ; 0; 0; 0; ½}.

Можно выбрать элемент – е4. Выберем элемент e4.

Определим позицию для установки этого элемента. Возможные позиции –7, 8, 6, 3.

f₃ = r₃₄ d₅₃ + r₉₄ d₁₃ + r₇₄ d₂₃ + r₈₄ d₄₃ + m₃ h₄= 1*2 + 0*2+ 0*1+ 0*3+3*1=5

f₇ = r₃₄ d₅₇ + r₉₄ d₁₇ + r₇₄ d₂₇ + r₈₄ d₄₇ + m₇ h₄= 1*1 + 0*2+ 0*3+ 0*1+1*1=2

f₆ = r₃₄ d₅₆ + r₉₄ d₁₆ + r₇₄ d₂₆ + r₈₄ d₄₆ + m₆ h₄= 1*1 + 0*3+ 0*2+ 0*2+3*1=4

f₈= r₃₄d₅₈ + r₉₄d₁₈ + r₇₄ d₂₈ + r₈₄d₄₈ + m₈ h₄= 1*1 + 0*3+ 0*2+ 0*2+2*1=3

f₇ = min[f₇; f₆; f₈; f₃] = 2, размещаем элемент e4 в позицию 7. Тогда массив элементов J_k={e3, е9, e7, e8, е4}, а массив позиций T_k = {t5, t1, t2, t4, t7}.

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

3 строка матрицы R – {½; ½; 0; 1; ½ ; ½; ½; ½; 1}.

9 строка матрицы R – {0; 0; 1; 0; 0 ; 0; ½; ½; 0}.

7 строка матрицы R – {0; 0; ½; 0; 0 ; 0; 0; 0; ½}.

8 строка матрицы R – {0; 0; ½; 0; 0 ; 0; 0; 0; ½}.

4 строка матрицы R – {0; 0; 1; 0; 0 ; 0; 0; 0; 0}.

Можно выбрать элемент – е1, e2, e5, e6. Выберем элемент e1.

Определим позицию для установки этого элемента. Возможные позиции –8, 6, 3.

f₃ = r₃₁ d₅₃ + r₉₁d₁₃ + r₇₁d₂₃ + r₈₁ d₄₃ + r₄₁d₇₃ + m₃ h₁= ½*2 + 3*1=4

f₆ = r₃₁d₅₆ + r₉₁d₁₆ + r₇₁ d₂₆ + r₈₁d₄₆ + r₄₁ d₇₆ + m₆ h₁= ½*1 + 3*1=3½

f₈= r₃₁d₅₈ + r₉₁d₁₈ + r₇₁d₂₈ + r₈₁d₄₈ + r₄₁d₇₈ + m₈ h₁= ½*1 + 2*1=2½

f₈ = min[f₆; f₈; f₃] = 2½, размещаем элемент e1 в позицию 8. Тогда массив элементов J_k={e3, е9, e7, e8, е4, e1}, а массив позиций T_k = {t5, t1, t2, t4, t7,t8}.

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