|
|
|
|
|
||||||||||||||||||||||||||||||
|
|
Å |
|
|
Å |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Å |
2 |
|
Å |
|
|
|
|
1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
Å |
|
|
|
|
|
|
|
|
|
|
Рис. 3.1
Для эскиза платы (рис. 3.1) составим матрицу расстояний:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
1
0
10
21
31
43
36
22
12
22
34
45
61
53
31
2
10
0
13
24
35
44
33
22
31
43
55
64
52
40
3
21
13
0
13
24
33
22
11
20
31
42
51
40
29
4
31
20
13
0
13
22
11
22
31
20
31
40
29
40
5
13
11
24
13
0
11
22
31
40
31
20
29
40
51
6
41
22
33
22
11
0
13
21
20
33
24
22
13
32
7
50
31
22
11
22
13
0
13
29
42
33
14
24
41
8
22
13
11
22
31
21
13
0
11
24
13
31
22
25
9
24
20
20
31
40
20
29
11
0
13
22
39
31
34
10
34
31
31
20
31
33
42
24
13
0
13
29
20
45
11
45
24
42
31
20
24
33
13
22
13
0
11
11
37
12
61
42
51
40
29
22
14
31
39
29
11
0
13
52
13
53
33
40
29
40
13
24
22
31
20
11
13
0
13
14
10
12
29
40
51
32
41
25
34
45
37
52
13
0
Трассировка по алгоритму Примма заключается в следующей последовательности:
1) Берём любую точку в качестве стартовой.
2) Задаёмся ограничением на локальную степень вершины (кол-во возможных связей).
3) По матрице расстояний находим точку наиболее близкую к любой из уже задействованых точек.
4) Если у обеих вершин ограничение локальной степени недостигнуто, проводим связь между двумя найдеными точками и ‘зачёркиваем’ в матрице расстояний столбец соотв. этой вершине, иначе возвращаемся к п. 3.
5) Повторяем пункты 3-4 пока все точки не будут соеденены (все столбцы ‘вычеркнуты’).
Проведём трассировку методом Примма ‘корпусной’ цепи питания.
В качестве стартовой берём точку 1 и ‘вычёркиваем’ столбец 1. Локальную степень вершины
принимаем равной 4. Самая короткая связь по матрице расстояний у неё с тчк. 2.
Проводим связь. Рассматриваем две строки – 1-ю и 2-ю. Самая короткая связь
между 1 и 8, между которыми и проводится следующая связь. ‘Вычёркивается’ столбец 2. Теперь рассматриваем три
строки – 1-ю, 2-ю, и 8-ю. Наименьшее расстояние имеется между 8 и 3, 8 и 9.
Проводим эти связи ‘вычёркивая’ соотв. столбцы. И т.д.
Повторяем до тех пор, пока все точки не будут соеденены (т.е. все столбцы
матрицы смежности будут ‘вычеркнуты’).
Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12
При использовании материалов активная ссылка на источник обязательна.