Э.Н. Гордеев
4
Конечно, тематика обратных задач – известная серьезная про-
блема дискретной оптимизации. Мы же лишь с помощью результатов
[3–5] указываем на возможность использования в определенных за-
дачах и в определенных методах параметра под названием «радиус
устойчивости».
Далее на простом примере проиллюстрируем еще одну возмож-
ность применения радиуса устойчивости.
Алгоритм восстановления информации с помощью радиуса
устойчивости.
Вновь рассмотрим канал обмена информацией между
пользователями
А
и
В
при наличии доступа злоумышленника
Z
к
этому каналу. Пусть, как и выше, пользователи
А
и
В
используют
решение траекторной задачи для сокрытия информации. Пусть раз-
мерность этой задачи, а также ее тип известны и злоумышленнику.
Неизвестно лишь то, что при этом
А
и
В
используют радиус
устойчивости. Рассмотрим один из примеров такого использования.
Алгоритмы и формулы для радиуса устойчивости и сходных с ним
параметров разработаны для многих комбинаторных задач с различ-
ными типами функционалов, различными метриками в векторном
пространстве весовых векторов, с различными типами и правилами
возмущений.
Если метрика чебышевская, функционал линейный и задача на
минимум, то в [6] показано, что
ρ(
A
) =
( )
( )
min max
j
A i
A
|
i
(
A
) –
j
(
A
)| / (|
i
| + |
j
| – 2|
i
j
|),
(2)
а величина
r
ij
(
A
) = |
i
(
A
) –
j
(
A
)| / (|
i
| + |
j
| – 2|
i
j
|) обладает тем
свойством, что при добавлении ее ко всем элементам
i
и вычитании
из всех элементов
j
длины этих траекторий сравняются. При этом
мы считаем, что все элементы вектора (матрицы)
А
возмущаются
независимо. Там же, в частности, показано, что для любой пары
i
и
j
оптимальной и неоптимальной траекторий возмущения элементов на
величины, меньшие
r
ij
(
A
), не может привести к выравниванию длин.
Отсюда следует, что при увеличении всех элементов
A
, кроме
элементов из оптимальной траектории, на величину, равную полови-
ну радиуса, радиус устойчивости новой задачи с новой матрицей
уменьшится вдвое.
Пусть теперь используется задача не обязательно
NP
-трудная и
необязательно большой размерности.
Отправитель генерирует произвольную матрицу (вектор)
А
и ре-
шает на ней задачу, находя при этом не только оптимальную траек-
торию
i
, но и радиус устойчивости ρ(
A
). Как уже говорилось выше, с
вероятностью единица оптимальная траектория единственна, поэто-
му в редком случае ее неединственности отправитель просто генери-
рует новую задачу.
