При этом следует учесть расходы на исключение дубликатов, кото-
рое проводится сравнением исходных кодов при присоединении оче-
редной функции:
n
−
1
i
=1
q
2
i
=
q
2
(
n
−
1)
n
2
.
Оценкa для всего метода примет вид
ϕ
динамич
(
n
) =
pn
+
pqn
(
n
+ 1)
2
+
q
2
(
n
−
1)
n
2
.
Оценка для метода локальных улучшений.
Этому методу требу-
ется начальное решение, которое можно было бы улучшать. В качестве
начального решения целесообразно взять значение, вычисленное жад-
ным алгоритмом Радо–Эдмондса. Как было показано ранее, затраты
на поиск решения без учета пересечений равны
npq
. В данном методе
осуществляется столько же проходов, сколько и в методе динамическо-
го программирования, т.е.
pn
проходов. На каждом шаге вычисляется
значение целевой функции для полного решения. Такое значений так-
же уже вычислялось, оно равно
qn
+
qn
(
qn
−
1)
2
.
В итоге получаем оценку сложности для метода локальных улуч-
шений:
ϕ
локальн
(
n
) =
pqn
+
pn
+
pn qn
+
qn
(
qn
−
1)
2
.
Оценка для метода ветвей и границ.
Метод ветвей и границ ху-
же других поддается оценке. Во-первых, число его проходов сильно
зависит от входных параметров. Во-вторых, при реализации данного
метода требуется хранить в памяти дерево решений и вычисленные
оценки, что может потребовать чрезвычайно больших вычислитель-
ных ресурсов. Здесь нельзя пренебречь операциями записи, затраты
на которые значительно больше, чем затраты на чтение.
Оценим затраты на чтение так же, как это делалось для других ме-
тодов. Полное число вершин (если потребуется построить все дерево
целиком) будет равно
1 +
p
n
−
p
2
. Для каждой вершины потребует-
ся однократно вычислить мощности частичных решений по всем ее
дочерним вершинам, а также при каждом проходе провести анализ вы-
черкнутых дочерних вершин (сравнение с эталоном). Для сравнения
потребуется
p
элементарных операций.
Оценим затраты на вычисление мощностей частичных решений.
Это будет сумма ряда, учитывающая уровень дерева. Число вершин
на уровне
i
будет равняться
p
i
−
1
, для каждой вершины частичное ре-
шение будет состоять из
(
i
−
1)
q
исходных кодов. К этому частичному
30 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2009. № 3
