Послідовний алгоритм компоновки

 

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

Сутність задачі полягає в розподілі комутаційної схеми на частини (вузли) з наступними обмеженнями: кількість елементів (КЕ) вузла не повинна перевищувати 6, кількість зовнішніх виводів (В) вузла повинно бути менш або рівно 17. В алгоритмі закладений принцип мінімізації зовнішніх виводів вузла при максимізації внутрішньо вузлових зв'язків.

Послідовність рішення.

1. Перед початком компоновки безліч нерозподілених елементів включає D0 (фіктивний елемент, що об'єднує всі зовнішні виводи схеми), D1, D2, D3, D4, D5, D6, D7.

2. Фіктивний елемент D0 назначаємо в фіктивний вузол T0 (r=0). Після цієї безлічі нерозподілених елементів Ir= (D1, D2, D3, D4, D5, D6, D7).

3. Починаємо компоновку вузла Т1 (r=1) (табл. 2.1):

А) для кожного з нерозподілених елементів (безліч Ir при r=1) обчислюємо функціонал L1 - кількість електричних ланцюгів (комплексів), якими даний елемент Xr зв'язаний з безліччю ще нерозподілених.

 

 

де

Ir - безліч нерозподілених елементів.

В якості базового елементу  вузла Tr (при r=1) вибираємо перший по порядку елемент з максимальним значенням L1. Це D2. Елемент D2 виключаємо з безлічі нерозподілених елементів Ir (r=1).

Б) для кожного з нерозподілених елементів розраховуємо значення функціонала L2, що показує число зовнішніх зв'язків вузла (отриманого доданням до вже розподіленого елементу D2 чергового кандидата) з безліччю інших елементів схеми, включаючи D0.

Кількість зовнішніх висновків вузла рівно числу ланцюгів, що зв'язують елементи вузла з елементами, що не входять до вузла. Ті елементи, для яких здійсненна умова L2 В, (де В=17), виключаються на даному кроку з числа кандидатів в вузол, що формується; ці елементи позначені зірочкою.

 

 

де - вузол з l елементами;

Ts - вузли,що сформувалися;

.

 

Для кандидатів,що залишилися розраховуємо функціонал L3. Функціонал L3 - це число ланцюгів, що з'єднують розглядуваний елемент-кандидат з безліччю елементів даного вузла. Для призначення в вузол вибираємо той елемент, що має максимальне значення L3. Якщо таких елементів декілька, то слід вибирати перший по порядку, що має найменшу величину L2. На даному кроку це D5.

Елемент D5 виключаємо з безлічі нерозподілених. Отже, в перший вузол тепер розподілені елементи D2 і D5. Формування вузла буде завершене, коли число елементів в ньому досягне даного (КЕ=5), або не знайдеться жодного кандидата, додавання якого не порушить умови L2£ В (B=17).

В) Для елементів,що залишилися нерозподіленими, розраховуємо функціонали - L2, L3. По вище наведеним правилам визначаємо черговий елемент вузла D4.

Г) В результаті аналогічних розрахунків визначаємо наступний елемент вузла Т1-D1. На цьому компоновка першого вузла завершена, тому що додавання наступного кандидату порушить умову L2£ В (B=17).

Виконуємо компоновку вузла Т2 (табл. 2.1, r=2.). Закінчення формування

цього вузла відбувається по досягненню заданого числа елементів в вузлі

(КЕ=5) та виконання умови L2£ В (B=17). Це елементи: D3, D7.

Д) Елемент D6, що залишився, розміщуємо в вузол Т3 Всі

елементи розподілені.

Результатами компоновки є схеми внутрішньовузлових сполучень вузлів Т1, Т2, Т3.

 

Таблиця 2.1 - Таблиця компоновки елементів схеми

r	Dr1	L1	Gr1	Dr2	L2	L3	Gr2	Dr3	L2	L3	Gr3	Dr4	L2	L3	Gr4	Dr5	L2	L3
1	D1	1	D2	D1	8	1	D2	D1	14	1	D2	D1	17	1	D1	D3	22	-
	D2	4		D3	9	1	D5	D3	16	1	D4	D3	19	-	D2	D6	21	-
	D3	2		D4	9	-		D4	14	2	D5	D6	18	-	D4	D7	24	-
	D4	4		D5	11	2		D6	20	-		D7	21	-	D5
	D5	4		D6	14	-		D7	17	2
	D6	3		D7	11	2
	D7	3
2	D3	2	D3	D6	16	0	D3	D6	23	-
	D6	0		D7	13	2	D7
	D7	2
3	D6