Page 138 - 4495

Неідемпотентне, загальне впорядкування

Вагова напівкі- Вагова CSP Лексико- Лексикографічна
льцева CSP графічна CSP напівкільцева
CSP

Локальна напівкі-
Імовірнісна CSP
льцева CSP Поліноміальне
часткове удо-
Неідемпотентне, час-
Ідемпотентне, загальне сконаленя
ткове впорядкування
впорядкування

Рисунок 3 – Зв’язки між моделями

:
Нехай маємо множину найбільших значень p p , , p , де кожне
1 h
p є найбільшим значенням серед всіх напівкільцевих значень
i
( ,a  , )a . Кожне напівкільцеве значення ( ,a  , )a будь – якого корте-
1 h 1 h
жу з ІО з компаратором «краще по сумарній вазі» перетворюється в

a p (h 1)   a p a . Напівкільцеве значення  перетворюється у  .
1 h 1 h
Аналогічно задаються потрібні перетворення для компараторів
«краще за кількістю незадоволених» та «краще за найменшими квад-

ратами».
Лексикографічна напівкільцева CSP
Лексикографічна CSP відповідає першому необов’язковому рів-

неві ІО з компаратором «лексикографічно краще». Нехай маємо най-
більше значення p із мультимножинами т A всіх напівкільцевих
j j
значень ( ,A  , A . Перетворення f кожного напівкільцевого елемента
)
 1 h
)
A  ( ,A  , A виглядає таким чином:
1 h



f ( ) (A  A т т A ) такі, що iA  { (a a  ap h i ) A }.
1 h i i
Напівкільцеве значення  в напівкільцевій CSP з компаратором

138