7 / 18
Шаг 2. Выполнить следующие действия (сам параллелотоп
[x]
i
после проверки удаляется из множества
X
):
1) если
[
f
] ([x]
i
)
∩
[
l
] =
∅
, то продолжить работу;
2) если
[
f
] ([x]
i
)
⊆
[
l
]
, или
[
f
] ([x]
i
)
∩
[
l
]
6
=
∅
,
ω
([x]
i
)
< w
, то
проверка завершена “удачно”;
3) в случае невыполнения действий 1 и 2 найти параллелотопы
[x]
0
= [
x
1
]
i
×
. . .
×
h
mid
([
x
k
]
i
) ; [
x
k
]
i
i
×
. . .
×
[
x
n
]
i
и
[x]
00
= [
x
1
]
i
×
×
. . .
×
h
[
x
k
]
i
;
mid
([
x
k
]
i
)
i
×
. . .
×
[
x
n
]
i
, где
k
— номер компоненты
параллелотопа
[x]
i
с наибольшей шириной, и добавить их в множе-
ство
X
.
Шаг 3. Если
i <
|
X
|
, то увеличить значение
i
на единицу и перейти
к шагу 2, а если
i
=
|
X
|
— перейти к шагу 4.
Шаг 4. Заменить множество
X
множеством
˜X
, сообщить, что про-
верка завершена “неудачно”.
Алгоритмы реализации операторов сжатия.
На вход всех опе-
раторов сжатия подается параллелотоп
[s]
.
Алгоритм SAS-оператора
(для работы необходим параметр шири-
ны
w
и число попыток
A
). Последовательность выполнения указанно-
го алгоритма приведена ниже.
Шаг 1. Найти
h
˜Υ
i
= [
f
] ([
s
])
.
Шаг 2. Для каждой компоненты вектора
[
s
i
]
найти такое наимень-
шее целое число
n
i
, что
ω
([
s
i
])
n
i
≤
w
.
Шаг 3. Каждый интервал
[
s
i
]
представить в виде объединения не-
пересекающихся интервалов
n
i
S
j
=1
s
j
i
. Таким образом, создается разби-
ение начального параллелотопа
[s] =
N
S
k
=1
[s]
k
, где
N
=
n
Y
i
=1
n
i
.
Шаг 4. Найти
h
˜Υ
i
= min
n
[
f
] ([s]
k
)
o
k
=
j
1
,...,j
A
,
h
˜Υ
i
,
min
n
[
f
] ([s]
k
)
o
k
=
j
1
,...,j
A
,
h
˜Υ
i
— результирующий сжатый интер-
вал, где
j
1
, . . . , j
A
— случайно выбранные натуральные числа из ин-
тервала
[1;
N
]
.
Алгоритм RPS-оператора
(для работы необходимо число точек
A
). Последовательность выполнения указанного алгоритма приведена
ниже.
Шаг 1. Генерировать
A
случайных точек
ξ
i
∈
[s]
,
i
= 1
, . . . , A
.
Шаг 2. Найти
h
˜Υ
i
= [
f
] ([s])
,
min
i
=1
,...,A
f
(
ξ
i
)
— результирующий
сжатый интервал.
ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2016. № 1 39