Добавлен: 21.10.2018
Просмотров: 394
Скачиваний: 8
ЛЕКЦИИ 3-4
РАСЧЕТ КРАТЧАЙШИХ ДРЕВОВИДНЫХ СТРУКТУР ПРОИЗВОЛЬНОЙ
КОНФИГУРАЦИИ.
3.1. Расчет кратчайшей древовидной связной сети
Задача определения структуры древовидной конфигурации, которую решил
Прим Р. К. [16] может быть сформулирована следующим образом.
Задано: множество узлов {????
????
}, i =
1, ????
̅̅̅̅̅ проектируемой сети и полный граф
связей ????
????????
, которыми могут быть соединены узлы сети. Требуется определить
древовидную связную сеть, которая имеет наименьшую суммарную
взвешенную длину.
Математическая формулировка задачи отыскания кратчайшей связывающей
сети, соединяющей N узлов, может быть записана в следующем виде:
???? = min
????
????????
∑
∑
????
????????
????
????????
????
????=1
????
????=1
(3.1)
где ????
????????
— взвешенная, например, соотношениями (2.4) - (2.6) длина связи
между i -м и j-м узлами;
????
????????
= {
1, если ????
????????
∈ ????
0, если ????
????????
∉ ????
}
(3.2)
????
????????
— искомые булевы переменные.
Задача, определенная соотношениями (3.1), (3.2), относится к классу
линейных задач с целочисленными булевыми переменными и может быть
решена одним из методов исследования операций.
Однако решение поставленной задачи наиболее эффективно может быть
осуществлено с использованием алгоритма Прима А.К. [16]. В основу
алгоритма построения кратчайшей связывающей сети положены два принципа:
А. Всякий изолированный узел соединяется с ближайшим соседом
(ближайшим соседом рассматриваемого узла является тот, который
находится от рассматриваемого на расстоянии, не большем, чем любой
другой узел).
Б. Всякий изолированный фрагмент соединяется с ближайшим соседом
кратчайшей дугой (изолированный фрагмент — это подмножество узлов,
связанное дугами, но не охватывающее всех заданных узлов.
Рассмотрим подробнее процедуру расчета, реализующую алгоритм Прима.
1. Начало расчета, описание всех переменных.
2. Ввод исходных данных N – количество соединяемых узлов;
М – матрица взвешенных расстояний размерностью N X N, в которой элементы
????
????????
= ∞; Q= 0 – значение целевой функции; Ф = {0} - список узлов, входящих
во фрагмент; ‖????
????????
‖= 0 - матрица результатов расчета структуры.
3. Просматривая исходную матрицу М по строкам и столбцам
???? = 1, ????
̅̅̅̅̅
???? = 1, ????
̅̅̅̅̅, определяем минимальную дугу ????
????????
,
4. Заносим в список Ф узлов, входящих во фрагмент, номера узлов k,l,
соответствующих индексам строк и столбцов найденного элемента ????
????????
.
Элемент матрицы ????
????????
=
????
????????
= 1. Вычисляем текущее значение целевой
функции Q = Q+????
????????
.
5. Вычеркиваем из исходной матрицы М те столбцы , которые вошли в
список Ф узлов, входящих во фрагмент, и получаем скорректированную
матрицу ????
1
.
6. Из скорректированной матрицы
????
1
выделяем строки, номера которых
входят в список Ф. Просматривая указанные строки поэлементно,
находим минимальный элемент ????
????????
.
7. Заносим в список Ф узлов, входящих во фрагмент, номер столбца l,
найденного минимального элемента ????
????????
, соответ-ствующих значениям
????
????????
=
????
????????
= 1. Вычисляем Q = Q+
????
????????
.
8. Если число элементов |Ф|, записанных в списке Ф узлов, входящих в
фрагмент, равно числу узлов N , то переходим к п. 9, если |Ф|< N , то к п.
5.
9. Вывод результата расчета матриц Х и значения целевой функции Q.
Несмотря на простоту, процедура позволяет отыскать решение,
обеспечивающее достижения глобального оптимума, что корректно доказано в
[16].
Пример 3.1. По п.п. 1 и 2 задана исходная матрица М размерностью 5х5:
1
2
3
4
5
1
∞ 37 29 75 78
2 37
∞ 21 61 42
M= 3 29 21
∞ 49 52
4 75 61 49
∞ 57
5 78 42 52 57
∞
3.
????
23
=21.
4. Ф={2,3};
????
23
=
????
23
=1; Q=21.
5. Вычеркиваем 2- и 3-й столбцы матрицы М и получаем ????
1
.
6.
????
31
=29.(минимальный элемент 2- и 3-й строк матрицы).
7. Ф={2,3,1};
????
31
=
????
13
=1; Q=50.
8. |Ф| = 3, переходим к п.5.
5’. Вычеркиваем 1-3-й столбцы М.
6’. ????
25
=42.
7’ Ф={2,3,1,5}; ????
25
=
????
52
=1; Q=92.
8’ и 6’’. ????
34
=49……
7’’. Ф={2,3,1,5,4}; ????
34
=
????
43
=1; Q=141.
8 и 9. Результат
1 2 3 4 5
1 0 0 1 0 0
2 0 0 1 0 1
X= 3 1 1 0 1 0
4 0 0 1 0 0
5 0 1 0 0 0
Рассмотренная процедура позволяет получить за конечное число шагов
кратчайшую связанную сеть, причем принцип А реализуется на 3-м и 4- м
шагах, а шаги 6-8 реализуют принцип В.
Приведенный пример носит иллюстративный характер. Разобранные па
практике структуры имеют большую размерность, однако для определения
кратчайшей древовидной структуры приведенная процедура может быть
успешно использована.
Самоконтроль знаний
Контрольные вопросы
1. Привести вербальную постановку задачи определения кратчайшей связной
сети (КСС).
2. Как в математической постановке задачи определения кратчайшей связной
сети учитывается требования связности и древовидности?
3. Какие варьируемые переменные используются в математической модели и
как они представлены в алгоритме решения
4. Почему в матрице взвешенных расстояний М принимается ????
????????
= ∞ ?
5. Сформулируйте и поясните, в чем состоят достоинства и недостатки
алгоритма Прима?