4.2 Алгоритм Хейса
Метод Хейса здійснює пошук найкоротшого шляху в багатошаровому ДРП між двома заданими осередками A і B. Для кожного шару i вводиться своє ДРПi. Однойменні осередки (вільні) можуть бути звязані переходами. Осередки можуть бути або зайнятими, або вільними. Кожному вільному осередку ставиться у відповідність індекс довжини Pi і індекс кількості переходів, причому при переході з шару в шар індекс довжини збільшується на 1. Індекс застосовується для зменшення числа переходів.
В процесі розповсюдження хвилі для кожного шару використовуються наступні масиви: ДРПi - стан осередків i-го шару; Li - поточного фронту хвилі в i-м шарі; Mi - осередки шару i сусідні до осередків з Li. При утворенні чергового фронту для i-го шару разом з осередками з Mi використовуються ті вільні осередки i-го шару, в яких можливий перехід з інших шарів і які мають той же індекс P.
Недолік методу: хвиля розповсюджується послідовно в кожному з шарів і незалежно, це приводить до великих витрат машинного часу.
Приклад: проведення траси D6:1,D4:5
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
||
|
18 |
1 |
|||||||||||||||||||||
|
18 |
17 |
18 |
2 |
|||||||||||||||||||
|
O |
1 |
13 |
O |
3 |
||||||||||||||||||
|
O |
2 |
D5 |
14 |
O |
16 |
15 |
14 |
13 |
14 |
15 |
16 |
17 |
4 |
|||||||||
|
O |
3 |
15 |
O |
15 |
14 |
13 |
12 |
13 |
14 |
15 |
16 |
5 |
||||||||||
|
O |
4 |
15 |
O |
14 |
13 |
12 |
11 |
12 |
13 |
14 |
15 |
18 |
6 |
|||||||||
|
O |
5 |
17 |
O |
13 |
12 |
11 |
10 |
11 |
12 |
13 |
14 |
17 |
18 |
7 |
||||||||
|
O |
6 |
18 |
O |
11 |
10 |
9 |
10 |
11 |
12 |
13 |
16 |
17 |
18 |
8 |
||||||||
|
O |
7 |
19 |
O |
10 |
9 |
8 |
9 |
10 |
11 |
12 |
15 |
16 |
17 |
9 |
||||||||
|
17 |
O |
8 |
20 |
O |
9 |
8 |
7 |
8 |
9 |
10 |
11 |
14 |
15 |
16 |
10 |
|||||||
|
17 |
16 |
O |
9 |
21 |
O |
8 |
7 |
6 |
7 |
8 |
9 |
10 |
13 |
14 |
15 |
11 |
||||||
|
16 |
15 |
O |
10 |
22 |
O |
7 |
6 |
5 |
6 |
7 |
8 |
9 |
12 |
13 |
14 |
12 |
||||||
|
15 |
14 |
O |
11 |
23 |
O |
6 |
5 |
4 |
5 |
6 |
7 |
8 |
11 |
12 |
13 |
13 |
||||||
|
14 |
13 |
O |
12 |
24 |
O |
5 |
4 |
3 |
4 |
5 |
6 |
7 |
10 |
11 |
12 |
14 |
||||||
|
14 |
13 |
12 |
11 |
10 |
9 |
8 |
7 |
4 |
3 |
2 |
3 |
4 |
5 |
6 |
11 |
12 |
13 |
15 |
||||
|
13 |
12 |
11 |
10 |
9 |
8 |
7 |
6 |
3 |
2 |
1 |
2 |
3 |
4 |
5 |
12 |
13 |
14 |
16 |
||||
|
12 |
11 |
10 |
9 |
8 |
7 |
6 |
5 |
2 |
1 |
O |
1 |
13 |
O |
13 |
14 |
15 |
17 |
|||||
|
13 |
12 |
3 |
2 |
O |
2 |
D6 |
14 |
O |
15 |
14 |
15 |
16 |
18 |
|||||||||
|
14 |
13 |
O |
1 |
8 |
O |
5 |
4 |
3 |
O |
3 |
15 |
O |
16 |
15 |
16 |
17 |
19 |
|||||
|
14 |
15 |
O |
2 |
D4 |
9 |
O |
O |
4 |
15 |
O |
17 |
16 |
17 |
18 |
20 |
|||||||
|
15 |
16 |
O |
3 |
10 |
O |
7 |
6 |
O |
5 |
17 |
O |
18 |
17 |
18 |
21 |
|||||||
|
16 |
17 |
O |
4 |
11 |
O |
8 |
7 |
O |
6 |
18 |
O |
18 |
22 |
|||||||||
|
17 |
18 |
O |
5 |
12 |
O |
9 |
8 |
O |
7 |
19 |
O |
23 |
||||||||||
|
18 |
O |
6 |
13 |
O |
10 |
9 |
O |
8 |
20 |
O |
24 |
|||||||||||
|
O |
7 |
14 |
O |
11 |
10 |
O |
9 |
21 |
O |
25 |
||||||||||||
|
12 |
11 |
O |
10 |
22 |
O |
26 |
||||||||||||||||
|
18 |
17 |
16 |
15 |
14 |
13 |
12 |
O |
11 |
23 |
O |
27 |
|||||||||||
|
18 |
17 |
16 |
15 |
14 |
13 |
O |
12 |
24 |
O |
28 |
||||||||||||
|
18 |
17 |
16 |
15 |
14 |
15 |
16 |
17 |
18 |
29 |
|||||||||||||
|
18 |
17 |
16 |
15 |
16 |
17 |
18 |
30 |
Рисунок. 4.2 - Трасування (шар 1)
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
19 |
20 |
21 |
||
|
1 |
18 |
17 |
18 |
|||||||||||||||||||
|
2 |
18 |
17 |
16 |
17 |
18 |
|||||||||||||||||
|
3 |
O |
1 |
13 |
O |
18 |
17 |
16 |
15 |
16 |
17 |
18 |
|||||||||||
|
4 |
O |
2 |
D5 |
14 |
O |
17 |
16 |
15 |
14 |
15 |
16 |
17 |
18 |
|||||||||
|
5 |
O |
3 |
15 |
O |
16 |
15 |
14 |
13 |
14 |
15 |
16 |
17 |
18 |
|||||||||
|
6 |
O |
4 |
15 |
O |
15 |
14 |
13 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
||||||||
|
7 |
O |
5 |
17 |
O |
13 |
12 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
||||||||
|
8 |
O |
6 |
18 |
O |
12 |
11 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
18 |
|||||||
|
9 |
O |
7 |
19 |
O |
11 |
10 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
17 |
|||||||
|
10 |
O |
8 |
20 |
O |
10 |
9 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
16 |
|||||||
|
11 |
O |
9 |
21 |
O |
9 |
8 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
15 |
|||||||
|
12 |
18 |
O |
10 |
22 |
O |
8 |
7 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
14 |
||||||
|
13 |
18 |
17 |
O |
11 |
23 |
O |
7 |
6 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
13 |
|||||
|
14 |
18 |
17 |
16 |
O |
12 |
24 |
O |
6 |
5 |
4 |
5 |
6 |
7 |
8 |
9 |
10 |
11 |
12 |
||||
|
15 |
17 |
16 |
15 |
11 |
12 |
13 |
||||||||||||||||
|
16 |
16 |
15 |
14 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
2 |
3 |
4 |
5 |
12 |
13 |
14 |
|||
|
17 |
15 |
14 |
13 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
1 |
O |
1 |
13 |
O |
13 |
14 |
15 |
||||
|
18 |
14 |
13 |
12 |
9 |
8 |
7 |
6 |
5 |
4 |
3 |
2 |
O |
2 |
D6 |
14 |
O |
14 |
15 |
16 |
|||
|
19 |
15 |
14 |
13 |
O |
1 |
8 |
O |
5 |
4 |
3 |
O |
3 |
15 |
O |
16 |
15 |
16 |
17 |
||||
|
20 |
16 |
15 |
14 |
O |
2 |
D4 |
9 |
O |
6 |
5 |
4 |
O |
4 |
15 |
O |
17 |
16 |
17 |
18 |
|||
|
21 |
17 |
16 |
15 |
O |
3 |
10 |
O |
7 |
6 |
5 |
O |
5 |
17 |
O |
18 |
17 |
18 |
|||||
|
22 |
18 |
17 |
16 |
17 |
O |
4 |
11 |
O |
8 |
7 |
6 |
O |
6 |
18 |
O |
18 |
||||||
|
23 |
18 |
17 |
18 |
O |
5 |
12 |
O |
9 |
8 |
7 |
O |
7 |
19 |
O |
||||||||
|
24 |
18 |
O |
6 |
13 |
O |
10 |
9 |
8 |
O |
8 |
20 |
O |
||||||||||
|
25 |
O |
7 |
14 |
O |
11 |
10 |
9 |
O |
9 |
21 |
O |
|||||||||||
|
26 |
17 |
16 |
15 |
14 |
13 |
12 |
11 |
10 |
O |
10 |
22 |
O |
||||||||||
|
27 |
18 |
17 |
16 |
15 |
14 |
13 |
12 |
11 |
O |
11 |
23 |
O |
||||||||||
|
28 |
O |
12 |
24 |
O |
||||||||||||||||||
|
29 |
18 |
17 |
16 |
15 |
16 |
17 |
18 |
|||||||||||||||
|
30 |
18 |
17 |
16 |
17 |
18 |
Рисунок. 4.3 - Трасування (шар 2)
Таблиця 4.2 - Проведення траси
|
шаг |
L1 |
M1 |
v1 |
L2 |
M2 |
v2 |
|
|
1 |
,( 17, 13) |
,( 17, 12),( 16, 13) |
0 |
,( 17, 13) |
,( 17, 12),( 16, 13) |
0 |
|
|
2 |
,( 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) |
0 |
|
|
3 |
,( 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) |
0 |
|
|
4 |
,( 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) |
1 |
|
|
5 |
,( 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) |
1 |
|
|
6 |
,( 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) |
1 |
|
|
7 |
,( 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) |
1 |
|
|
8 |
,( 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) |
1 |
|
|
9 |
,( 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) |
1 |
|
|
10 |
,( 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) |
1 |
|
|
11 |
,( 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) |
1 |
|
|
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) |
,( 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) |
2 |
|
|
13 |
,( 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) |
2 |
|
|
14 |
,( 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),( 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) |
2 |
|
|
15 |
,( 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) |
3 |
,( 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) |
3 |
|
|
16 |
,( 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) |
3 |
,( 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) |
3 |
|
|
17 |
,( 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) |
4 |
,( 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) |
3 |
|
|
18 |
,( 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) |
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),( 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) |
3 |
|
|
19 |
,( 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) |
,( 23, 5) |
4 |
,( 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, 5) |
3 |
Шляхи одночасно досягли координати ( 23, 5), тому шлях проводится за найменшим значенням ?.
Остаточно шлях має вигляд:
Шар 2:
(17,13),( 17, 12),( 17, 11),( 17, 10),( 17, 9),( 17, 8),( 17, 7),( 17, 6),
Перехід на шар 1:
( 17, 5),( 17, 4),( 17, 3),( 18, 3),( 19, 3),( 20, 3),( 21, 3),( 22, 3),( 23, 3),( 23, 4), ( 23, 5)
- ВСТУП
- 1 ПОБУДОВА КОММУТАЦІЙНОЇ СХЕМИ. ПОДАННЯ КОММУТАЦІЙНОЇ СХЕМИ У ВИГЛЯДІ ГРАФІВ І МАТРИЦЬ
- 2 КОМПОНОВКА ЕЛЕМЕНТІВ СХЕМИ В ВУЗЛИ
- 2.1 Послідовний алгоритм компоновки
- 2.2 Мінімізація числа міжвузлових сполучень
- 3 РОЗМІЩЕННЯ ЕЛЕМЕНТІВ НА ПЛАТІ
- 3.1 Послідовний алгоритм розміщення
- 3.2 Ітераційний алгоритм розміщення елементів на платі
- 4 ТРАСУВАННЯ СПОЛУЧЕНЬ
- 4.1 Алгоритм Лі
- 4.2 Алгоритм Хейса
- 5 РОЗПОДІЛ СПОЛУЧЕНЬ ПО ШАРАХ
- 6 РОЗРОБКА БІБЛІОТЕКИ ЕЛЕМЕНТІВ В САПР PCAD
- 6.1 Створення символу компоненту в PCAD Schematic
- 6.2 Створення корпусу компонентів в PCAD PCB
- 6.3 Створення компоненту за допомогою Library Executive
- 7 РОЗРОБКА СЕМИ ЕЛЕКТРИЧНОЇ ПРИНЦИПОВОЇ В САПР PCAD.
- 7.1 Завантаження бібліотек
- 7.2 Розміщення компонентів на схемі
- Автоматизація проектування комп’ютерних систем
- 2.1 Характеристика виробничої діяльності та систем управління Філія ват "хвоот "Завод друкованих плат"
- 1.2.3.3 Сапр у радіоприладобудуванні (eda-системи)
- 4.5 Конструювання друкованих плат
- Проектування пристроїв
- 3. Проектування пристроїв зв’язку.
- Тема 2. Системи автоматизованого проектування (сап)