утверждению 1, для всех ситуаций
(
Z, x
)
таких, что
Z Y
, установка
x
на множество
Z
возможна. Из определения порядка в упорядочен-
ном множестве
Q
(
x
)
следует, что каждой паре
(
Z, x
)
соответствует
вершина белого цвета диаграммы Хассе
g
, причем
g
≤
p
.
Если установка
x
на
Y
невозможна, то ситуации
(
Y, x
)
отвечает
черная вершина
p
диаграммы Хассе, а все вершины
g
(
g
≥
p
), соответ-
ствующие большим запрещенным ситуациям, должны быть окрашены
в черный цвет согласно утверждению 2.
Таким образом, если некоторая вершина
q
2
Q
(
x
)
является бе-
лой, то все элементы, принадлежащие порядковому идеалу
I
(
q
) =
=
{
q
0
2
Q
(
x
)
|
q
0
≤
q
}
, также белые. Если
q
— черная, то и все эле-
менты порядкового фильтра
F
(
q
) =
{
q
00
2
Q
(
x
)
|
q
00
≥
q
}
имеют это
свойство.
Итак, задачу определения условий геометрического доступа для
элемента
x
можно представить в форме игры двух игроков — ЛПР
и природы. Игра ведется по следующим правилам. Дано частично-
упорядоченное множество
(
Q,
≤
)
, все вершины которого являются не-
окрашенными. Первый ход ЛПР заключается в выборе неокрашенной
вершины из этого множества. Ответ второго игрока состоит в опре-
делении цвета предложенной для проверки вершины. Если вершина
получила черный цвет, то все вершины порядкового фильтра (верхне-
го конуса) окрашиваются в черный цвет. Если проверяемая вершина
получила белый цвет, то все вершины порядкового идеала (нижнего
конуса) окрашиваются в белый цвет. Второй ход ЛПР делает на нео-
крашенном фрагменте исходного частичного порядка и т.д. Требуется
полностью окрасить данный частичный порядок за наименьшее число
ходов.
Например, для частичного порядка
Q
(8)
(см. рис. 3) процедура
окраски может быть выполнена за два приема. На рис. 4 приведены
ходы первого игрока (
1, 3
) и ответы природы (
2, 4
).
Описанная игра относится к классу неантагонистических, посколь-
ку второй игрок не заинтересован в проигрыше первого и в процессе
Рис. 4. Окраска частичного порядка
Q
(8):
1, 3
— ходы ЛПР;
2, 4
— ответы природы
82 ISSN 0236-3933. Вестник МГТУ им. Н.Э. Баумана. Сер. “Приборостроение”. 2013. № 3
