Проектування друкованих плат пристроїв комп’ютерних систем. Курсовая работа (т). Информационное обеспечение, программирование.
💣 👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
Информационное обеспечение, программирование
Вы можете узнать стоимость помощи в написании студенческой работы.
Помощь в написании работы, которую точно примут!
Похожие работы на - Проектування друкованих плат пристроїв комп’ютерних систем
Нужна качественная работа без плагиата?
Не нашел материал для своей работы?
Поможем написать качественную работу Без плагиата!
« АВТОМАТИЗАЦІЯ ПРОЕКТУВАННЯ КОМП’ЮТЕРНИХ СИСТЕМ »
на
тему « Проектування друкованих плат
пристроїв комп’ютерних систем »
Пояснювальна
записка до курсової роботи:
·
Оволодіння
навиками формування опису логічного елементу в середовищі системи проектування
PCAD. Структура формованого опису повинна відповідати стандартній структурі
опису логічного елементу, прийнятого в системі проектування PCAD.
·
Вивчення
принципів і оволодіння навиками проектування принципових електричних схем в
редакторі PCAD Schematic. У цьому редакторі здійснюється розміщення умовного
графічного позначення (УГП) елементів на робочому полі редактора, проведення
електричних споучень між елементами, привласнення елементам позиційних
позначень, формування шин і т.п.
·
Оволодіння
навиками трасування печатних сполучень в САПР PCAD.
1 ПОБУДОВА КОММУТАЦІЙНОЇ СХЕМИ. ПОДАННЯ
КОММУТАЦІЙНОЇ СХЕМИ У ВИГЛЯДІ ГРАФІВ І МАТРИЦЬ
2 КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ
2.1 Послідовний алгоритм компоновки
2.2 Мінімізація числа міжвузлових сполучень.
3 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ
3.1 Послідовний алгоритм розміщення
3.2 Ітераційний алгоритм розміщення елементів на
платі
5 РОЗПОДІЛ СПОЛУЧЕНЬ ПО ШАРАХ
6 РОЗРОБКА БІБЛІОТЕКИ ЕЛЕМЕНТІВ В САПР PCAD
6.1 Створення символу компоненту в PCAD Schematic
6.2 Створення корпусу компонентів в PCAD PCB
6.3 Створення компоненту за допомогою Library
Executive
7 РОЗРОБКА СЕМИ ЕЛЕКТРИЧНОЇ ПРИНЦИПОВОЇ В САПР
PCAD
7.2 Розміщення компонентів на схемі
7.3 Розміщення електричних ланцюгів
8 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ В САПР PCAD
8.1 Упаковка схеми на друкарську плату
8.2 Розміщення компонентів на платі
9 ТРАСУВАННЯ ПЕЧАТНИХ СПОЛУЧЕНЬ ПЕЧАТНОЇ ПЛАТИ В
САПР PCAD
9.2 Установка зазорів між провідниками
9.3 Автотрасувальник Quick Route
10 ТЕХНОЛОГІЧНИЙ КОНТРОЛЬ ПЕЧАТНОЇ ПЛАТИ.
Курсова робота
орієнтована на синтез та дослідження проектування друкованих плат, застосування
алгоритмів розміщення елементів (послідовний алгоритм та оптимізація) на
друкованій платі, компоновки (послідовний алгоритм та метод парних перестановок
для оптимізації), трасування сполучень (алгоритми Лі та Хейса), розподілу по
шарах.
Також в курсовій
роботі передбачається використання спецілаізованого програмного забезпечення –
системи автоматизації проектування PCAD, а саме оволодіння навиками формування
опису логічного елементу в середовищі системи проектування PCAD, вивчення
принципів і оволодіння навиками проектування принципових електричних схем в
редакторі PCAD Schematic, оволодіння навиками трасування печатних сполучень в
САПР PCAD.
Елементами
комутаційної схеми є автономні конструктивні одиниці - мікросхеми. Для переходу
від принципової схеми до комутаційної необхідно на принциповій схемі виділити
групи елементів, що складають окремі мікросхеми і замінити їх одним елементом
комутаційної схеми.
Перехід від
електричної принципової схеми до комутаційної схеми виконується в наступній
послідовності:
Всі елементи
схеми зображуються в вигляді умовних графічних позначок, у вигляді
прямокутника, всередині якого записаний порядковий номер елементу (мікросхеми).
При цьому різноманітні логічні елементи, розташовані в одному корпусі мікросхеми.
Контакти роз’єму, т. т. Всі вхідні і вихідні сигнали, вважаються контактами
фіктивного елементу D0.
На рис. 1.3.
наведена комутаційна схема, відповідна принциповій схемі, зображеній на рис.
1.2. Всі електричні ланцюги комутаційної схеми послідовно нумеруються: V1,
V2,...V38.
Кожний
електричний ланцюг (безліч еквіпотенційних виводів елементів називається
комплексом. Існує також поняття елементного комплексу. Елементний комплекс - це
безліч елементів комутаційної схеми, об'єднаних одним електричним ланцюгом. Всі
елементні комплекси на комутаційній схемі необхідно пронумерувати послідовним
рядом чисел, починаючи з одиниці. Номера елементних комплексів доцільно
проставляти у контактів всіх елементів, об'єднаних одним елементним комплексом.
Граф елементних
комплексів (ГЕК) складається з: вершин, відповідних елементам (тип D); вершин,
відповідних елементним комплексам (тип V); ребер, відповідних електричним
сполученням.
ГЕК можна описати
за допомогою матриці елементних комплексів Q
де m - кількість
елементів D; n - кількість ланцюгів.
Рисунок.
1.4 -
Матриця елементних комплексів (продовження)
На рис. 1.5
наведений зважений граф схеми (ЗГС). Він складається з: вершин, відповідних
елементам D 0 , D 1 ,... …, D 9 , і ребер, що
з'єднають ці вершини. Ребро, що з'єднує вершини графа D i і D j
з приписаною йому вагою, показує наявність і кількість зв'язків між елементами
схеми E i і E j .
ЗГС можна уявити
в вигляді матриці сполучень R (рис 1.6):
R=¦¦ r ¦¦ m ´ m , r ij - число зв'язків D i
і D j .
Матриця R
симетрична відносно головної діагоналі. Крім Того rii=0, i=0, …, m-1.
Компоновка
елементів може здійснюватися різноманітними методами. В курсовій роботі застосований
послідовний алгоритм компоновки.
Сутність задачі
полягає в розподілі комутаційної схеми на частини (вузли) з наступними
обмеженнями: кількість елементів (КЕ) вузла не повинна перевищувати 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), виключаються на
даному кроку з числа кандидатів в вузол, що формується; ці елементи позначені
зірочкою.
Для кандидатів
,що залишилися розраховуємо функціонал 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 - Таблиця
компоновки елементів схеми
Основою даного
алгоритму компоновки є використання ітераційного процесу обміну місцями
елементів, що належать різноманітним вузлам з метою мінімізації числа
міжвузлових сполучень.
Розглянемо
ітераційний алгоритм компоновки. Необхідно виконати компоновку елементів схеми
в вузли (кількість елементів N=7) з урахуванням заданих обмежень (кількість
елементів в вузлі не повинно перевищувати заданого значення КЕ). Можна вважати,
що в кожному вузлі міститься максимальна кількість елементів (КЕ=6 для
розглядуваного прикладу). В випадку, коли в якому-або вузлі число елементів К
менш КЕ, необхідно додатково ввести Ng=KE-K фіктивних елементів, не зв'язаних з
іншими елементами схеми.
За початковий
можна прийняти варіант компоновки, отриманий після виконання послідовного
алгоритму. Виконаємо мінімізацію міжвузлових сполучень для початкового
варіанту.
Приріст числа
міжвузлових сполучень при обміні місцями елементів буде рівно [1]:
Lx (Ly) і Fx (Fy)
відповідно зовнішні і внутрішні сполучення елементів Dx, Dy.
При розрахунку
зовнішніх сполучень необхідно враховувати сполучення тільки між розглядуваними
вузлами Т1, Т2. Зовнішні зв'язки з D0 можна не враховувати.
Рисунок.
2.1 -
Мінімізація міжвузлових сполучень (крок 1)
Рисунок.
2.2-
Мінімізація міжвузлових сполучень (крок 2)
Введемо фіктивний
елемент 8 у вузол Т2
Рисунок.
2.3 -
Мінімізація міжвузлових сполучень (крок 3)
Рисунок.
2.4 -
Остаточний варіант компоновки
Рисунок.
2.5 -
Комутаційна схема внутрішньовузлових сполучень вузла Т1
Рисунок.
2.6 -
Комутаційна схема внутрішньовузлових сполучень вузла Т2
Рисунок.
2.7 -
Комутаційна схема внутрішньовузлових сполучень вузла Т3
Рисунок.
2.8 - Схема
міжвузлових сполучень
Мета етапу -
оптимальне розміщення елементів на платі, використовуючи послідовний алгоритм.
Критеріями
оптимальності є: сумарна довжина сполучень на платі, число пересічень
сполучень, число шарів комутації. Для рішення задачі розміщення застосований
послідовний алгоритм .
Суттєвість задачі
розміщення полягає в наступному. Необхідно вибрати набір позицій для розміщення
елементів. Позиції (посадочні місця) типового елементу заміни розмістити в вузлах
координатної сітки, як, наприклад, показано на рис. 3.1. Крок сітки, що
вимірюється в умовних одиницях, рівний 1. Нумерація позицій в загальному
випадку може бути довільною, однак нумерацію потрібно виробляти так, щоб
відстань між n i і n i+1 була мінімальною. Перший стовпчик сітки
відводиться для роз’єму.
Вхідними даними
для рішення задачі розміщення є матриця сполучень R (рис. 1.6) і матриця
відстаней Р=¦¦ р ij ¦¦ n ´ n , в який елемент р ij
дорівнює відстані між центрами позицій n i і n j . Матриця Р
- симетрична, з нульовою головною діагоналлю (р ii =0, i=1, 2,..., n).
Для набору
позицій, показаного на рис. 3.1 матриця Р має вигляд:
Cутність
послідовного алгоритму розміщення полягає в наступному:
Вибір першого елементу
по максимальній кількості зв'язків з роз’ємом (з елементом D0).
Вибір наступного
елементу по максимальній кількості зв'язків з елементами, розміщеними на
попередніх кроках.
Для даного
варіанту алгоритм розміщення виконується наступним чином. Елемент D0 вважається
розміщеним. Тому викреслюється нульовий стовпчик матриці R (рис. 1.6), а з
нульового рядка вибирається максимальний елемент і в позицію n 1
розміщується елемент D5, бо він має найбільше число зв'язків( r 05 =7)
з елементом D0, тобто з роз’ємом. Якщо в даному рядку матриці є декілька
елементів з максимальною вагою, то вибирається будь-який.
Кількість
зв'язків з елементами, розміщеними на попередніх кроках
Обираємо макс.
Кількість зв’язків - D6
L(D6)(N2)=R(6,5)*d(N1,N2)+R(6,0)*d(N0,N2)=1*1+7*1=8
L(D6)(N3)=R(6,5)*d(N1,N3)+R(6,0)*d(N0,N3)=1*2+7*1=9
L(D6)(N4)=R(6,5)*d(N1,N4)+R(6,0)*d(N0,N4)=1*3+7*1=10
L(D6)(N5)=R(6,5)*d(N1,N5)+R(6,0)*d(N0,N5)=1*4+7*2=18
L(D6)(N6)=R(6,5)*d(N1,N6)+R(6,0)*d(N0,N6)=1*3+7*2=17
L(D6)(N7)=R(6,5)*d(N1,N7)+R(6,0)*d(N0,N7)=1*2+7*2=16
Кількість
зв'язків з елементами, розміщеними на попередніх кроках
Обираємо макс.
Кількість зв’язків - D4
L(D4)(N3)=R(4,5)*d(N1,N3)+R(4,0)*d(N0,N3)+R(4,6)*d(N2,N3)=2*2+2*1+3*1=9
L(D4)(N4)=R(4,5)*d(N1,N4)+R(4,0)*d(N0,N4)+R(4,6)*d(N2,N4)=2*3+2*1+3*2=14
L(D4)(N5)=R(4,5)*d(N1,N5)+R(4,0)*d(N0,N5)+R(4,6)*d(N2,N5)=2*4+2*2+3*3=21
L(D4)(N6)=R(4,5)*d(N1,N6)+R(4,0)*d(N0,N6)+R(4,6)*d(N2,N6)=2*3+2*2+3*2=16
L(D4)(N7)=R(4,5)*d(N1,N7)+R(4,0)*d(N0,N7)+R(4,6)*d(N2,N7)=2*2+2*2+3*1=11
Кількість
зв'язків з елементами, розміщеними на попередніх кроках
Обираємо макс.
Кількість зв’язків - D7
L(D7)(N4)=R(7,5)*d(N1,N4)+R(7,0)*d(N0,N4)+R(7,6)*d(N2,N4)+R(7,4)*d(N3,N4)=0+7*1+0+0=7
L(D7)(N5)=R(7,5)*d(N1,N5)+R(7,0)*d(N0,N5)+R(7,6)*d(N2,N5)+R(7,4)*d(N3,N5)=0+7*2+0+0=14
L(D7)(N6)=R(7,5)*d(N1,N6)+R(7,0)*d(N0,N6)+R(7,6)*d(N2,N6)+R(7,4)*d(N3,N6)=0+7*2+0+0=14
L(D7)(N7)=R(7,5)*d(N1,N7)+R(7,0)*d(N0,N7)+R(7,6)*d(N2,N7)+R(7,4)*d(N3,N7)=0+7*2+0+0=14
Кількість
зв'язків з елементами, розміщеними на попередніх кроках
Обираємо макс.
Кількість зв’язків - D1
L(D1)(N5)=R(1,5)*d(N1,N5)+R(1,0)*d(N0,N5)+R(1,6)*d(N2,N5)+R(1,4)*d(N3,N5)+R(1,7)*d(N4,N5)=2*4+4*2+0+0+0=16
L(D1)(N6)=R(1,5)*d(N1,N6)+R(1,0)*d(N0,N6)+R(1,6)*d(N2,N6)+R(1,4)*d(N3,N6)+R(1,7)*d(N4,N6)=2*3+4*2+0+0+0=14
L(D1)(N7)=R(1,5)*d(N1,N7)+R(1,0)*d(N0,N7)+R(1,6)*d(N2,N7)+R(1,4)*d(N3,N7)+R(1,7)*d(N4,N7)=2*2+4*2+0+0+0=12
Кількість
зв'язків з елементами, розміщеними на попередніх кроках
Обираємо макс.
Кількість зв’язків - D3
L(D3)(N5)=R(3,5)*d(N1,N5)+R(3,0)*d(N0,N5)+R(3,6)*d(N2,N5)+R(3,4)*d(N3,N5)+R(3,7)*d(N4,N5)+R(3,1)*d(N7,N5)=0+4*2+0+0+2*1+0=10
L(D3)(N6)=R(3,5)*d(N1,N6)+R(3,0)*d(N0,N6)+R(3,6)*d(N2,N6)+R(3,4)*d(N3,N6)+R(3,7)*d(N4,N6)+R(3,1)*d(N7,N6)=0+4*2+0+0+2*2+0=12
Згідно з ТЗ –
метод парних перестановок.
Обираються 2
елементи e(i) та e(j) з позиціями t(e(i)) та t(e(j)) відповідно. Знаходиться
множина елементів Р:
Якщо значення
більша за 0, елементи можна поміняти місцями.
Рисунок.
3.10 -
Ітераційне розміщення (початок)
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-3
P(2,5)=D1, D3, D4, D6, D7 =====> delta=-3
P(2,6)=D1, D3, D4, D5, D7 =====> delta=0
P(3,4)=D2, D5, D6, D7 =====> delta=-10
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-4
P(3,6)=D2, D4, D5, D7 =====> delta=-9
P(4,7)=D2, D3, D5, D6 =====> delta=-5
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-3
P(6,7)=D2, D3, D4, D5 =====> delta=-6
Рисунок.
3.11 -
Ітераційне розміщення (крок 1)
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-9
P(2,5)=D1, D3, D4, D6, D7 =====> delta=-1
P(2,6)=D1, D3, D4, D5, D7 =====> delta=-8
P(3,4)=D2, D5, D6, D7 =====> delta=-12
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6
P(3,6)=D2, D4, D5, D7 =====> delta=-13
P(4,7)=D2, D3, D5, D6 =====> delta=-9
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-3
P(6,7)=D2, D3, D4, D5 =====> delta=-10
Рисунок.
3.12 -
Ітераційне розміщення (крок 2)
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-8
P(2,5)=D1, D3, D4, D6, D7 =====> delta=0
P(2,6)=D1, D3, D4, D5, D7 =====> delta=-6
P(3,4)=D2, D5, D6, D7 =====> delta=-10
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6
P(3,6)=D2, D4, D5, D7 =====> delta=-11
P(4,7)=D2, D3, D5, D6 =====> delta=-9
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-7
P(6,7)=D2, D3, D4, D5 =====> delta=-10
Рисунок.
3.13 -
Ітераційне розміщення (крок 3)
P(2,4)=D1, D3, D5, D6, D7 =====> delta=-7
P(2,5)=D1, D3, D4, D6, D7 =====> delta=0
P(2,6)=D1, D3, D4, D5, D7 =====> delta=-8
P(3,4)=D2, D5, D6, D7 =====> delta=-12
P(3,5)=D1, D2, D4, D6, D7 =====> delta=-6
P(3,6)=D2, D4, D5, D7 =====> delta=-10
P(4,7)=D2, D3, D5, D6 =====> delta=-10
P(5,7)=D1, D2, D3, D4, D6 =====> delta=-7
P(6,7)=D2, D3, D4, D5 =====> delta=-10
Нумерація виводів
мікросхем (рис. 3.15) та конструктивне розміщення елементів на графічній платі
після виконання алгоритму розміщення зображено на рис. 3.16.
Рисунок.
3.15 -
Нумерація виводів мікросхем
Рисунок.
3.16 -
Орієнтація мікросхем на платі
Аналогічно
проводиться розміщення в вузлах Т1, Т2, Т3.
Рисунок.
3.17 -
Координатна сітка для вузлів Т1, Т2
Рисунок.
3.18 -
Розміщення елементів в узлі Т1
Рисунок.
3.19 -
Розміщення елементів в узлі Т2
В узлі Т3 тільки
1 елемент, тому його розміщення не розглядається.
Для сполучення
виводів мікросхем в відповідності з електричною принциповою схемою необхідно
використати заданий алгоритм трасування. В процесі трасування слід виконати
наступні основні етапи:
1) отримання
списку сполучень (табл. 4.1),
2) визначення
порядку прокладки сполучень,
Використовуючи
один з заданих алгоритмів здійснюється попереднє трасування на одній площині. В
процесі трасування необхідно мінімізувати геометричні параметри сполучень:
довжину, число пересічень, кількість згибів.
Таблиця
4.1- Список
сполучень вузла Т1
Суттєвість
хвильового алгоритму Лі полягає в наступному:
1. Плата
розбивається на прямокутні осередки, в результаті чого утвориться дискретне
робоче поле (ДРП).
2. Задається
деяка функція F, що є критерієм якості шляху. В якості вагової функції F
необхідно брати відстань від осередка А до розглядуваного осередка.
3. Осередку А
ставимо в відповідність вагу 0, сусіднім з ній осередкам вага 1 і т. д. При
цьому виникає числова хвиля, що буде розповсюджуватися від осередка А до
осередка В, і як тільки фронт хвилі досягне осередка В, розповсюдження хвилі
закінчується.
4. При русі від
осередка В до осередка А по пройденим осередкам так, щоб числа зменшувалися
монотонно, одержуємо трасу, що з'єднує осередки А і В.
Процес розповсюдження
числової хвилі і проведення траси повторюється для всіх сполучень з табл. 4.1.
Приклад проведення траси D6: 04 і D4: 06 показаний на рис. 4.1.
Рисунок.
4.1 -
Проведення траси D6: 04 і D4: 06
Метод Хейса здійснює пошук найкоротшого шляху в багатошаровому ДРП між
двома заданими осередками A і B. Для кожного шару i вводиться своє ДРПi.
Однойменні осередки (вільні) можуть бути зв'язані переходами. Осередки можуть
бути або зайнятими, або вільними. Кожному вільному осередку ставиться у
відповідність індекс довжини Pi і індекс кількості переходів, причому при
переході з шару в шар індекс довжини збільшується на 1. Індекс застосовується
для зменшення числа переходів.
В процесі
розповсюдження хвилі для кожного шару використовуються наступні масиви: ДРПi -
стан осередків i-го шару; Li - поточного фронту хвилі в i-м шарі; Mi - осередки
шару i сусідні до осередків з Li. При утворенні чергового фронту для i-го шару
разом з осередками з Mi використовуються ті вільні осередки i-го шару, в яких
можливий перехід з інших шарів і які мають той же індекс P.
Недолік методу: хвиля розповсюджується послідовно в кожному з шарів і
незалежно, це приводить до великих витрат машинного часу.
Приклад: проведення траси D6:1,D4:5
,(
15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)
,(
17, 11),( 16, 12),( 16, 14),( 18, 12)
,(
15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)
,(
19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)
,(
17, 11),( 16, 12),( 16, 14),( 18, 12)
,(
16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)
,(
19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)
,(
19, 11),( 15, 11),( 14, 12),( 13, 13),( 14, 14),( 15, 15),( 16, 16)
,(
16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)
,(
16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)
,(
19, 11),( 15, 11),( 14, 12),( 13, 13),( 14, 14),( 15, 15),( 16, 16)
,(
17, 9),( 19, 10),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15),( 15,
16),( 16, 17)
,(
16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)
,(
16, 9),( 17, 8),( 18, 9),( 19, 10),( 20, 11),( 21, 12),( 14, 12),( 13, 13),(
14, 14),( 16, 17)
,(
17, 9),( 19, 10),( 14, 11),( 13, 12),( 12, 13),( 13, 14),( 14, 15),( 15,
16),( 16, 17)
,(
21, 12),( 17, 8),( 16, 9),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),(
14, 16),( 15, 17)
,(
16, 9),( 17, 8),( 18, 9),( 19, 10),( 20, 11),( 21, 12),( 14, 12),( 13, 13),(
14, 14),( 16, 17)
,(
16, 8),( 17, 7),( 18, 8),( 20, 10),( 21, 11),( 22, 12),( 14, 11),( 13, 12),(
12, 13),( 13, 14),( 14, 15)
,(
21, 12),( 17, 8),( 16, 9),( 13, 11),( 12, 12),( 11, 13),( 12, 14),( 13, 15),(
14, 16),( 15, 17)
,(
17, 7),( 16, 8),( 15, 9),( 21, 11),( 22, 12),( 12, 11),( 11, 12),( 10, 13),(
11, 14),( 12, 15),( 13, 16),( 14, 17)
,(
16, 8),( 17, 7),( 18, 8),( 20, 10),( 21, 11),( 22, 12),( 14, 11),( 13, 12),(
12, 13),( 13, 14),( 14, 15)
,(
16, 7),( 17, 6),( 18, 7),( 21, 10),( 22, 11),( 23, 12),( 13, 11),( 12, 12),(
11, 13),( 12, 14),( 13, 15),( 14, 16)
,(
17, 7),( 16, 8),( 15, 9),( 21, 11),( 22, 12),( 12, 11),( 11, 12),( 10, 13),(
11, 14),( 12, 15),( 13, 16),( 14, 17)
,(
17, 6),( 16, 7),( 15, 8),( 22, 11),( 23, 12),( 11, 11),( 10, 12),( 9, 13),(
10, 14),( 11, 15),( 12, 16),( 13, 17)
,(
16, 7),( 17, 6),( 18, 7),( 21, 10),( 22, 11),( 23, 12),( 13, 11),( 12, 12),(
11, 13),( 12, 14),( 13, 15),( 14, 16)
,(
16, 6),( 17, 5),( 18, 6),( 22, 10),( 23, 11),( 24, 12),( 12, 11),( 11, 12),(
10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)
,(
17, 6),( 16, 7),( 15, 8),( 22, 11),( 23, 12),( 11, 11),( 10, 12),( 9, 13),(
10, 14),( 11, 15),( 12, 16),( 13, 17)
,(
17, 5),( 16, 6),( 15, 7),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11,
16),( 12, 17),( 23, 11),( 24, 12)
,(
16, 6),( 17, 5),( 18, 6),( 22, 10),( 23, 11),( 24, 12),( 12, 11),( 11, 12),(
10, 13),( 11, 14),( 12, 15),( 13, 16),( 14, 17)
,(
16, 5),( 18, 5),( 23, 10),( 24, 11),( 25, 12),( 11, 11),( 10, 12),( 9, 13),(
10, 14),( 11, 15),( 12, 16),( 13, 17),( 14, 18)
,(
17, 5),( 16, 6),( 15, 7),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),( 11,
16),( 12, 17),( 23, 11),( 24, 12)
,(
17, 4),( 16, 5),( 15, 6),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10,
16),( 11, 17),( 14, 19),( 24, 11),( 25, 12)
,(
16, 5),( 18, 5),( 23, 10),( 24, 11),( 25, 12),( 11, 11),( 10, 12),( 9, 13),(
10, 14),( 11, 15),( 12, 16),( 13, 17),( 14, 18)
,(
24, 10),( 25, 11),( 26, 12),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),(
11, 16),( 12, 17),( 13, 18),( 14, 19)
,(
17, 4),( 16, 5),( 15, 6),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),( 10,
16),( 11, 17),( 14, 19),( 24, 11),( 25, 12)
,(
17, 3),( 16, 4),( 15, 5),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9,
16),( 10, 17),( 13, 19),( 15, 19),( 14, 20),( 25, 11),( 26, 12)
,(
24, 10),( 25, 11),( 26, 12),( 10, 11),( 9, 12),( 8, 13),( 9, 14),( 10, 15),(
11, 16),( 12, 17),( 13, 18),( 14, 19)
,(
25, 10),( 26, 11),( 27, 12),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),(
10, 16),( 11, 17),( 12, 18),( 13, 19),( 14, 20),( 15, 19)
,(
17, 3),( 16, 4),( 15, 5),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9,
16),( 10, 17),( 13, 19),( 15, 19),( 14, 20),( 25, 11),( 26, 12)
,(
18, 3),( 17, 2),( 16, 3),( 15, 4),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7,
15),( 8, 16),( 9, 17),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19),( 26,
11),( 27, 12)
,(
25, 10),( 26, 11),( 27, 12),( 9, 11),( 8, 12),( 7, 13),( 8, 14),( 9, 15),(
10, 16),( 11, 17),( 12, 18),( 13, 19),( 14, 20),( 15, 19)
,(
18, 3),( 26, 10),( 27, 11),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9,
16),( 10, 17),( 11, 18),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19)
,(
18, 3),( 17, 2),( 16, 3),( 15, 4),( 7, 11),( 6, 12),( 5, 13),( 6, 14),( 7,
15),( 8, 16),( 9, 17),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19),( 26,
11),( 27, 12)
,(
18, 2),( 16, 2),( 15, 3),( 14, 4),( 19, 3),( 7, 10),( 6, 11),( 5, 12),( 4,
13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 11, 19),( 12, 20),( 13, 21),( 15,
21),( 16, 20),( 17, 19),( 27, 11),( 28, 12)
,(
18, 3),( 26, 10),( 27, 11),( 8, 11),( 7, 12),( 6, 13),( 7, 14),( 8, 15),( 9,
16),( 10, 17),( 11, 18),( 12, 19),( 13, 20),( 14, 21),( 15, 20),( 16, 19)
,(
17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),( 6, 12),( 5, 13),( 6,
14),( 7, 15),( 8, 16),( 9, 17),( 10, 18),( 11, 19),( 12, 20),( 13, 21),( 15,
21),( 16, 20),( 17, 19)
,(
18, 2),( 16, 2),( 15, 3),( 14, 4),( 19, 3),( 7, 10),( 6, 11),( 5, 12),( 4,
13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 11, 19),( 12, 20),( 13, 21),( 15,
21),( 16, 20),( 17, 19),( 27, 11),( 28, 12)
,(
29, 12),( 28, 11),( 27, 10),( 20, 3),( 19, 2),( 15, 2),( 14, 3),( 13, 4),( 6,
10),( 5, 11),( 4, 12),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 10, 19),( 11,
20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)
,(
17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),( 6, 12),( 5, 13),( 6,
14),( 7, 15),( 8, 16),( 9, 17),( 10, 18),( 11, 19),( 12, 20),( 13, 21),( 15,
21),( 16, 20),( 17, 19)
,(
26, 8),( 27, 9),( 16, 3),( 17, 2),( 18, 1),( 19, 2),( 20, 3),( 6, 11),( 5,
12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 9, 18),( 10, 19),( 11,
20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)
,(
29, 12),( 28, 11),( 27, 10),( 20, 3),( 19, 2),( 15, 2),( 14, 3),( 13, 4),( 6,
10),( 5, 11),( 4, 12),( 4, 14),( 5, 15),( 6, 16),( 7, 17),( 10, 19),( 11,
20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)
,(
20, 4),( 21, 3),( 27, 9),( 28, 10),( 29, 11),( 30, 12),( 29, 13),( 18, 18),(
19, 19),( 18, 20),( 17, 21),( 9, 19),( 10, 20),( 11, 21),( 5, 10),( 4, 11),(
4, 15),( 5, 16),( 6, 17),( 13, 3),( 12, 4)
,(
26, 8),( 27, 9),( 16, 3),( 17, 2),( 18, 1),( 19, 2),( 20, 3),( 6, 11),( 5,
12),( 4, 13),( 5, 14),( 6, 15),( 7, 16),( 8, 17),( 9, 18),( 10, 19),( 11,
20),( 12, 21),( 16, 21),( 17, 20),( 18, 19)
,(
29, 12),( 27, 8),( 26, 7),( 21, 3),( 20, 2),( 19, 1),( 17, 1),( 16, 2),( 15,
3),( 6, 10),( 5, 11),( 4, 12),( 3, 13),( 4, 14),( 5, 15),( 6, 16),( 7, 17),(
8, 18),( 9, 19),( 10, 20),( 11, 21),( 17, 21),( 18, 20),( 19, 19)
,(
20, 4),( 21, 3),( 27, 9),( 28, 10),( 29, 11),( 30, 12),( 29, 13),( 18, 18),(
19, 19),( 18, 20),( 17, 21),( 9, 19),( 10, 20),( 11, 21),( 5, 10),( 4, 11),(
4, 15),( 5, 16),( 6, 17),( 13, 3),( 12, 4)
,(
22, 3),( 21, 4),( 27, 8),( 28, 9),( 29, 10),( 30, 11),( 30, 13),( 29, 14),(
19, 18),( 19, 20),( 20, 19),( 18, 21),( 8, 19),( 9, 20),( 10, 21),( 5, 17),(
4, 16),( 4, 10),( 12, 3),( 11, 4)
,(
29, 12),( 27, 8),( 26, 7),( 21, 3),( 20, 2),( 19, 1),( 17, 1),( 16, 2),( 15,
3),( 6, 10),( 5, 11),( 4, 12),( 3, 13),( 4, 14),( 5, 15),( 6, 16),( 7, 17),(
8, 18),( 9, 19),( 10, 20),( 11, 21),( 17, 21),( 18, 20),( 19, 19)
,(
20, 1),( 21, 2),( 22, 3),( 16, 1),( 15, 2),( 14, 3),( 26, 6),( 27, 7),( 29,
11),( 30, 12),( 29, 13),( 19, 18),( 20, 19),( 19, 20),( 18, 21),( 5, 10),( 4,
11),( 3, 12),( 2, 13),( 3, 14),( 4, 15),( 5, 16),( 6, 17),( 7, 18),( 8, 19),(
9, 20),( 10, 21)
,(
22, 3),( 21, 4),( 27, 8),( 28, 9),( 29, 10),( 30, 11),( 30, 13),( 29, 14),(
19, 18),( 19, 20),( 20, 19),( 18, 21),( 8, 19),( 9, 20),( 10, 21),( 5, 17),(
4, 16),( 4, 10),( 12, 3),( 11, 4)
,(
22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),(
20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),(
2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15,
1),( 14, 2),( 13, 3),( 23, 3),( 22, 4),( 27, 7),( 28, 8),( 29, 9),( 30, 10),(
30, 14),( 29, 15),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 9, 21),( 8, 20),(
7, 19),( 2, 13),( 11, 3),( 10, 4),( 4, 17)
,(
20, 1),( 21, 2),( 22, 3),( 16, 1),( 15, 2),( 14, 3),( 26, 6),( 27, 7),( 29,
11),( 30, 12),( 29, 13),( 19, 18),( 20, 19),( 19, 20),( 18, 21),( 5, 10),( 4,
11),( 3, 12),( 2, 13),( 3, 14),( 4, 15),( 5, 16),( 6, 17),( 7, 18),( 8, 19),(
9, 20),( 10, 21)
,(
22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),(
20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),(
2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15,
1),( 14, 2),( 13, 3),( 26, 5),( 27, 6)
,(
22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),(
20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),(
2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15,
1),( 14, 2),( 13, 3),( 23, 3),( 22, 4),( 27, 7),( 28, 8),( 29, 9),( 30, 10),(
30, 14),( 29, 15),( 20, 18),( 21, 19),( 20, 20),( 19, 21),( 9, 21),( 8, 20),(
7, 19),( 2, 13),( 11, 3),( 10, 4),( 4, 17)
,(
23, 4),( 24, 3),( 27, 6),( 28, 7),( 29, 8),( 30, 9),( 30, 15),( 29, 16),( 21,
18),( 22, 19),( 21, 20),( 20, 21),( 8, 21),( 7, 20),( 6, 19),( 2, 12),( 1,
13),( 2, 14)
,(
22, 4),( 23, 3),( 22, 2),( 21, 1),( 29, 10),( 30, 11),( 30, 13),( 29, 14),(
20, 18),( 21, 19),( 20, 20),( 19, 21),( 4, 10),( 3, 11),( 2, 12),( 1, 13),(
2, 14),( 3, 15),( 4, 16),( 5, 17),( 6, 18),( 7, 19),( 8, 20),( 9, 21),( 15,
1),( 14, 2),( 13, 3),( 26, 5),( 27, 6)
,(
22, 1),( 23, 2),( 24, 3),( 23, 4),( 29, 9),( 30, 10),( 30, 14),( 29, 15),(
14, 1),( 13, 2),( 12, 3),( 27, 5),( 21, 18),( 22, 19),( 21, 20),( 20, 21),(
8, 21),( 7, 20),( 6, 19),( 5, 18),( 4, 17),( 3, 16),( 2, 15),( 1, 14),( 1,
12),( 2, 11),( 3, 10)
,(
23, 4),( 24, 3),( 27, 6),( 28, 7),( 29, 8),( 30, 9),( 30, 15),( 29, 16),( 21,
18),( 22, 19),(
Похожие работы на - Проектування друкованих плат пристроїв комп’ютерних систем Курсовая работа (т). Информационное обеспечение, программирование.
Сайты Для Проверки Итоговых Сочинений
Этапы Магистерской Диссертации
Сочинение Егэ 2022 Сколько Абзацев
Реферат: Внешнеполитический аспект политики Турецкой республики на Ближнем Востоке
Сочинение по теме Достоевский: Идиот
Контрольная работа по теме Режим дня детей и подростков
Курсовая Работа На Тему Метод Монте-Карло И Его Применение
Реферат: Выявление и диагностика туберкулеза легких в учреждениях первичной медико–санитарной помощи
Курсовая Работа На Тему Проблемы Занятости И Безработицы В Украине
Сочинение По Произведению Первый Учитель
Механизм Обеспечения Экономической Безопасности Государства Реферат
Реферат по теме Молодіжні рухи в україні 19-20 сторіччя
Как Оформить Анкетирование В Дипломной Работе
Лабораторная Работа Определение Индукции Магнитного Поля
Реферат: Plato Vs Aristotle Essay Research Paper How
Коммерческая Практика Отчет
Курсовая работа по теме Комплексная механизация технологических процессов на ферме в 500 голов с разработкой технологических линий
Реферат по теме Метожы аналитической химии
Контрольная работа: Максім Іванавіч Гарэцкі
Онкология Хирургия Темы Дипломных Работ
Похожие работы на - "Знание—сила" (Философия Френсиса Бекона)
Реферат: Ceasar Charater Analysis Essay Research Paper Character
Дипломная работа: Структура и инфраструктура рынка