Page 117 - 4495

на можливих преференцій.
Відповідність між цими преференціями була вже описана для не-
чіткої CSP, з використанням якої можливо моделювати обмеження з
пріоритетами, що описуються так само, як і обмеження з оцінкою не-

обхідності для ймовірнісної CSP.
У загальному випадку через преференції кортежів легко виража-
ти преференції обмежень. Наприклад, найбільше можлива преферен-

ція присвоюється всім кортежам, які задовольняють задане обмежен-
ня, а всім іншим кортежам присвоюється протилежна преференція.

Протилежне перетворення замінює обмеження c : D ...  D  W
1 k
множиною обмеженняc ,..., , де k - потужність цієї множини (кіль-
c
1 k
кість її елементів), тобто:
k  card w W   D ...  D : c )(  w .
1 k
Однак, це перетворення може бути використане тільки в тому ви-

падку, якщо k - скінченна для всіх обмежень. Як приклад, ілюструю-
чий той факт, що така умова може бути незадоволена, можна навести
преференцію, задану як відстань між двома дійсними числами. Щоб k

було скінченним, потрібно брати до уваги тільки скінченні домени
змінних. Так ми отримаємо скінченну кількість присвоєнь, тобто вер-
хня межа k відповідатиме кількостям присвоєнь.

Метамоделі
Уже було згадано про зв’язки між двома головними метамоделя-
ми, оцінною та напівкільцевою CSP. Коротко підсумуємо ці форма-

льні зв’язки, які детально вивчались у преференціях [66, 74].
Найбільша різниця між моделями полягає у здатності напівкіль-
цевої CSP виражати часткове впорядкування, тоді як оцінна CSP мо-
же задавати тільки загальний порядок на множині оцінок. Часткові

впорядкування можуть бути корисними для багатокритеріальної оп-
тимізації, оскільки добуток двох c - напівкілець є c- напівкільцем з
визначеним на ньому частковим впорядкуванням.

Оскільки в напівкільцевій CSP домени змінних повинні бути скі-
нченними, трансформація обмежень між напівкільцевою та оцінною
CSP є здійсненною. Припущення про загальний порядок навіть надає
цим моделям однакову теоретичну основу. Вже розглядалась відпові-

дність між преференціями кортежів та обмежень. Напівкільцева та
оцінна структури пов’язані також тим, що і в тій, і в іншій адитивна
напівкільцева операція закінчується операцією min , яку застосовують

в оцінній CSP для порівняння оцінок різних присвоєнь.
Остання представлена метамодель, часткове задоволення послаб-

117