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

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

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

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

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

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

Починаємо компоновку вузла Т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), виключаються на даному кроку з числа кандидатів в вузол, що формується; ці елементи позначені зірочкою.

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

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 - Таблиця компоновки елементів схеми