Проектування друкованих плат пристроїв комп’ютерних систем
Курсовой проект - Компьютеры, программирование
Другие курсовые по предмету Компьютеры, программирование
O1 13O O2D514O O315O16 O415O161516 O517O1615141516 O618O151413141516 O719O14131213141516 O820O1312111213141516 O921O121110111213141516 O1022O1110910111213141516 16O1123O1098910111213141516 1615O12 24O9878910111213141516 161514131211109876789101112131415161514131211109876567891011121314151413121110987654O1 13O1213141514131211109876543O2D614O1314151615141312O1 8O432O315O141516 16151413O2D49O321O415O1516 161514O310O432O517O16 1615O411O543O618O 16O512O654O719O 17O613O765O820O 16O7 14O876O921O 16151413121110987O1022O 1615141312111098O1123O 161514131211109O12 24O 16151413121110111213141516 1615141312111213141516 Рисунок. 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
123456789101112131415161718192021 18 1 181718 2 O1 13O 3 O2D514O1615141314151617 4 O315O1514131213141516 5 O415O141312111213141518 6 O517O13121110111213141718 7 O618O11109101112131617188 O719O109891011121516179 17O820O98789101114151610 1716O921O8767891013141511 1615O1022O765678912131412 1514O1123O654567811121313 1413O12 24O543456710111214 1413121110987432345611121315 131211109876321234512131416 1211109876521O1 13O13141517 131232O2D614O1514151618 1413O1 8O543O315O1615161719 1415O2D49OO415O1716171820 1516O310O76O517O181718 21 1617O411O87O618O18 22 1718O512O98O719O 23 18O613O109O820O 24 O7 14O1110O921O 25 1211O1022O 26 18171615141312O1123O 27 181716151413O12 24O 28 181716151415161718 29 18171615161718 30Рисунок. 4.2 - Трасування (шар 1)
1234567891011121314151617181920211 181718 2 1817161718 3 O1 13O18171615161718 4 O2D514O1716151415161718 5 O315O161514131415161718 6 O415O15141312131415161718 7 O517O13121112131415161718 8 O618O12111011121314151617189 O719O11109101112131415161710 O820O109891011121314151611 O921O9878910111213141512 18O1022O876789101112131413 1817O1123O76567891011121314181716O12 24O65456789101112151716151112131616151498765432123451213141715141387654321O1 13O1314151814131298765432O2D614O14151619151413O1 8O543O315O1615161720161514O2D49O654O415O1716171821171615O310O765O517O181718 2218171617O411O876O618O18 23 181718O512O987O719O 24 18O613O1098O820O 25 O7 14O11109O921O 26 1716151413121110O1022O 27 1817161514131211O1123O 28 O12 24O 29 18171615161718 30 1817161718 Рисунок. 4.3 - Трасування (шар 2)
Таблиця 4.2 - Проведення траси
шагL1M1v1L2M2v21,( 17, 13),( 17, 12),( 16, 13)0,( 17, 13),( 17, 12),( 16, 13)02,( 17, 12),( 16, 13),( 15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12)0,( 17, 12),( 16, 13),( 17, 11),( 16, 12),( 16, 14),( 18, 12)03,( 15, 13),( 16, 14),( 17, 11),( 16, 12),( 18, 12),( 19, 12),( 18, 11),( 16, 11),( 15, 12),( 14, 13),( 15, 14),( 16, 15)0,( 17, 11),( 16, 12),( 16, 14),( 18, 12),( 16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15)04,( 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)0,( 16, 11),( 17, 10),( 18, 11),( 19, 12),( 16, 15),( 16, 10),( 17, 9),( 18, 10),( 19, 11),( 20, 12),( 14, 13),( 16, 16)15,( 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)1,( 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)16,( 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)2,( 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)17,( 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)2,( 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)18,( 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)2,( 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)19,( 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)2,( 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)110,( 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)3,( 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)111,( 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)3,( 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)112,( 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)3,( 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)213,( 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)3,( 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)214,( 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)3,( 17, 3),( 19, 3),( 18, 2),( 26, 9),( 27, 10),( 7, 11),