Материал: Лабораторная работа№ 3, 4 Исследование алгоритмов размещения конструктивных элементов и итерационных алгоритмов
7
Среди оставшихся dij находим минимальное число. Оно равно 12 сразу
J=1
у двух позиций: №3 и №6. Берем 1-ю по порядку позицию №3. Помечаем все элементы третьего столбца матрицы D. Проходим вторую строку матрицы R и находим, что в ней максимальный элемент 5, который находится в 5-м столбце. Следовательно, модуль №5 размещаем в позицию №3, а 5-й столбец матрицы R из дальнейшего рассмотрения исключается. Получили
|
1 |
3 |
4 |
6 |
7 |
|
|
1 |
0 |
0 |
2 |
0 |
1 |
|
|
2 |
3 |
[3] 0 0 |
0 |
|
|
||
3 |
0 |
0 |
2 |
0 |
0 |
|
|
R = 4 |
2 |
2 |
0 |
0 |
0 |
|
|
5 |
2 |
0 |
0 |
3 |
0 |
|
|
6 |
0 |
0 |
0 |
0 |
3 |
|
|
7 |
1 |
0 |
0 |
3 |
0 |
|
|
|
1 |
2* |
3* 4 |
5 |
6 |
7 |
|
1 |
0 |
1 |
2 |
3 |
3 |
2 |
5 16 |
2 |
1 |
0 |
1 |
2 |
2 |
1 |
4 |
3 |
2 |
1 |
0 |
1 |
3 |
2 |
3 |
D = 4 3 2 1 0 4 3 2 15 |
|||||||
5 |
3 |
2 |
3 |
4 |
0 |
1 |
4 17 |
6 |
2 |
[1] 2 |
3 |
1 |
0 3 [12] |
||
7 |
5 |
4 |
3 |
2 |
4 |
3 |
0 21 |
7
На следующем шаге отыскиваем min из d6j =12 в строке №6.
J=1
Просматриваем шестую строку матрицы D и среди помеченных элементов 2-го и 3-го столбцов выбираем минимальный. Так определяем, к какой из уже занятых позиций, позиция №6 находится ближе всего: min[d62, d63] = d62 = 1 – ко 2-й. Во второй позиции уже находится модуль №2. Поэтому просматриваем вторую строку матрицы R и выбираем максимальный элемент r21 = 3. Он соответствует 1-му модулю, поэтому элемент №1 размещаем в позицию №6.
Исключаем из дальнейшего рассмотрения первый столбец матрицы R. Получили матрицы
46
|
3 |
4 |
6 |
7 |
1 |
0 |
2 |
0 |
1 |
2 |
3 |
0 |
0 |
0 |
3 |
0 |
2 |
0 |
0 |
R = 4 |
2 |
0 |
0 |
0 |
5 |
0 |
0 |
[3] 0 |
|
6 |
0 |
0 |
0 |
3 |
7 |
0 |
0 |
3 |
0 |
|
|
|
|
|
|
1 |
2* |
3* 4 |
5 |
6* |
7 |
|
|
1 |
0 |
1 |
2 |
3 |
3 |
2 |
5 |
16 |
2 |
1 |
0 |
1 |
2 |
2 |
1 |
4 |
|
3 |
2 |
1 |
0 |
1 |
3 |
2 |
3 |
|
D = 4 |
3 |
2 [1] 0 |
4 |
3 |
2 |
[15] |
||
5 |
3 |
2 |
3 |
4 |
0 |
1 |
4 |
17 |
6 |
2 |
1 |
2 |
3 |
1 |
0 |
3 |
|
7 |
5 |
4 |
3 |
2 |
4 |
3 |
0 |
21 . |
|
|
|
|
|
|
|
|
|
7
Далее выбираем min из dij = 15 в 4-й строке. В четвертой строке матрицы
J=1
D среди помеченных элементов d42, d43, d46 минимальный d43 = 1.Это говорит о том, что до позиции №4 ближе всех позиция №3, в которой уже размещен модуль №5. Поэтому просматриваем пятую строку матрицы R и среди оставшихся в ней элементов находим минимальный: r56 = 3 в шестом столбце. Тогда модуль №6 размещаем в позицию №4 и исключаем из дальнейшего рассмотрения столбец №6 матрицы R:
|
3 |
4 |
7 |
1 |
0 |
2 |
1 |
2 |
[3] 0 |
0 |
|
3 |
0 |
2 |
0 |
R = 4 |
2 |
0 |
2 |
5 |
0 |
0 |
0 |
6 |
0 |
0 |
3 |
7 |
0 |
0 |
0 |
|
|
|
|
47
|
1 |
2* |
3* |
4* |
5 |
6* |
7 |
|
|
|
|||||||
1 |
0 |
[1] 2 |
3 |
3 |
2 |
5 |
[16] |
|
2 |
1 |
0 |
1 |
2 |
2 |
1 |
4 |
|
3 |
2 |
1 |
0 |
1 |
3 |
2 |
3 |
|
D = 4 3 |
2 |
1 |
0 |
4 |
3 |
2 |
|
|
5 |
3 |
2 |
3 |
4 |
0 |
1 |
4 |
17 |
6 |
2 |
1 |
2 |
3 |
1 |
0 |
3 |
|
7 |
5 |
4 |
3 |
2 |
4 |
3 |
0 |
21 . |
7
Вновь выбираем минимальную из оставшихся сумм: d1j = 16 для пози-
J=1
ции №1. Просматриваем первую строку матрицы D и среди помеченных
элементов {d12, d13, d14, d16} находим min: это d12 = 1. Значит, от позиции №1 наименее удалена позиция №2, в которой находится модуль №2. Помечаем все
элементы первого столбца матрицы D. Просматриваем вторую строку матрицы R и выбираем максимальный элемент r23 = 3 для элемента №3. Его устанавливаем в 1-ю позицию, а 3-й столбец матрицы исключаем из дальнейшего рассмотрения:
4 7
1 |
[2] 1 |
|
2 |
0 |
0 |
3 |
2 |
0 |
R = 4 |
0 |
0 |
5 |
0 |
0 |
6 |
0 |
3 |
7 |
0 |
0 |
|
|
|
|
1* |
2* |
3* |
4* |
5 |
6* |
7 |
|
1 |
0 |
1 |
2 |
3 |
3 |
2 |
5 |
|
2 |
1 |
0 |
1 |
2 |
2 |
1 |
4 |
|
3 |
2 |
1 |
0 |
1 |
3 |
2 |
3 |
|
D = 4 |
3 |
2 |
1 |
0 |
4 |
3 |
2 |
|
5 |
3 |
2 |
3 |
4 |
0 |
[1] |
4 |
[17] |
6 |
2 |
1 |
2 |
3 |
1 |
0 |
3 |
|
7 |
5 |
4 |
3 |
2 |
4 |
3 |
0 |
21 . |
|
|
7 |
|
|
|
|
|
|
Далее выбираем min d1j = 17, соответствующую позиции №5. Среди по-
J=1
меченых элементов пятой строки матрицы D {d51, d52, d53, d54, d56} находим, минимальный: d56 = 1. Помечаем все элементы пятого столбца матрицы D. В шестой позиции размещен элемент №1. Поэтому просматриваем первую строку матрицы R, находим max rij=2 для модуля №4. Размещаем модуль №4 в
48
позицию №5, исключаем из дальнейшего рассмотрения четвёртый столбец матрицы R:
1
11
20
30 R = 4 0
50
63
70
|
|
|
I7 |
|
I7 |
|
|
|
I5 |
I6 |
|
I5 |
I6 |
|
|
|
|
|
I2 |
I3 |
I2 |
I3 |
I4 |
|
I4 |
|
|
||
|
I1 |
|
|
I1 |
|
|
|
|
|
|
|
|
а) |
|
|
б) |
|
|
|
|
Рис.3.1 |
|
|
Рис.3.2
49
|
1 |
2 |
3 |
4 |
5 |
6 |
7 |
|
1 |
0 |
1 |
2 |
3 |
3 |
2 |
5 |
|
2 |
1 |
0 |
1 |
2 |
2 |
1 |
4 |
|
3 |
2 |
1 |
0 |
1 |
3 |
2 |
3 |
|
D = 4 |
3 |
2 |
1 |
0 |
4 |
3 |
2 |
|
5 |
3 |
2 |
3 |
4 |
0 |
1 |
4 |
|
6 |
2 |
1 |
2 |
3 |
1 |
0 |
3 |
|
7 |
5 |
4 |
3 |
2 |
4 |
3 |
0 |
21 |
|
|
|
|
|
|
|
|
|
Последний седьмой модуль, следовательно, попадает в оставшуюся свободной седьмую позицию. Результат размещения дан на рис. 3.3.
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t7 |
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t4 |
|
|
t1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t2 |
|
|
t5 |
|
|
t6 |
|
|
||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|||||||||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
t3 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
||||
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
Рис.3.3. |
|
|
|
|
|
|
|
|||||
Суммарная длина соединений получилась равной 35 условным единицам.
4. АЛГОРИТМ ПРЕДВАРИТЕЛЬНОГО РАЗМЕЩЕНИЯ
Алгоритм включает такую последовательность действий [3]:
1. Для каждой строки матрицы R определить сумму элементов в каждой
7
строке матрицы ri = rij , j = 1,…, n.
j=1
2.Найти минимум среди r1, i = k.
3.Поместить элемент k в первую по порядку 1,…,n незанятую позицию 1.
4.В матрице R вычеркнуть k-ю строку, а элементы k-го столбца без
вычеркнутого nk элемента с отрицательным знаком переписать с k-го на 1-е место.
5.Если число строк в матрице не равно нулю, идти к 2.
6.Вычислить матрицу расстояний D.
50