NP-полные задачи с точки зрения качества приближенного реше-
ния можно разделить на три класса [3, 4].
1. Задачи, в которых эффективно (т.е. за полиномиальное время)
строятся приближенные решения с любой наперед заданной точно-
стью. Таковы, например, задачи о рюкзаке [4], некоторые задачи тео-
рии расписаний и др.
2. Задачи, в которых эффективно строятся приближенные решения
с априорной оценкой точности. При этом ошибка может быть зара-
нее оценена до работы алгоритма (в отличие от предыдущего случая
ее нельзя устремить к нулю). Таковы, в частности, многие задачи о
покрытии и др.
3. Задачи, вообще не допускающие эффективных приближенных
алгоритмов: получить приближенное решение с заданной оценкой точ-
ности столь же сложно, как и точное решение. К этому классу принад-
лежат задача о коммивояжере, общая задача булева программирования,
задачи о размещениях и многие другие [3].
Как показывает анализ, задача оптимального выбора вариантов за-
щиты вычислительной сети относится к третьему классу.
Для решения данной задачи можно использовать следующие клас-
сы приближенных методов: методы локальной оптимизации, методы
случайного поиска и комбинированные методы, или методы локально-
стохастической оптимизации.
Методы случайного поиска для решения задачи выбора вариантов
защиты от угроз безопасности ВС предприятия не очень удобны, так
как трудно организовать управляемый случайный поиск из-за особен-
ностей ограничений.
Остановимся на рассмотрении одного изметодов локальной опти-
мизации – метода вектора спада [5]. Достоинствами этого метода явля-
ются его простота и то, что существует аналитическое выражение для
вычисления верхней оценки числа его шагов. Рассмотрим метод векто-
ра спада применительно к решению задачи выбора вариантов защиты
от угрозбезопасности вычислительной сети предприятия.
Постановка задачи.
Введем обозначения.
1.
A
=
{
a
1
, a
2
, . . . , a
n
}
— множество возможных угроз безопасно-
сти;
N
=
{
1
,
2
, . . . , n
}
— множество индексов угроз.
2.
B
=
{
b
1
, b
2
, . . . , b
m
}
— множество средств защиты от угроз безо-
пасности;
M
=
{
1
,
2
, . . . , m
}
— множество индексов вариантов защи-
ты.
3.
T
= [
t
0
, t
max
]
— рассматриваемый период функционирования.
4.
p
i
,
∀
i
∈
N, p
i
∈
[0
,
1]
— возможность (вероятность) проявления
i
-й угрозы на интервале
T
определяется по данным статистики или с
помощью экспертов.
74 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2008. № 2
