Page 92 - 4495
P. 92
ЛЕКЦІЯ 15-16
ФОРМАЛЬНІ СТРУКТУРИ НА ОСНОВІ ОБМЕЖЕНЬ
Розглянемо основні підходи до розв’язання проблеми задоволен-
ня обмежень з преференціями. Означення наступних термінів є клю-
човим для розуміння кожної структури: обмеження (constraint), про-
блема (problem), ступінь задоволення (satisfaction degree), розв’язок
(solution), ступінь зв’язності (consistency degree).
Обмеження визначається як деяке розширення класичного почат-
кового обмеження. Означення проблеми природно розширює ідею
CSP беручи до уваги означення обмеження. Ступінь задоволення об-
числює як кожне присвоєння задовольняє обмеження в проблемі,
тобто, він призначений для порівняння особливих присвоєнь. Основ-
на ідея за означенням розв’язку трохи відрізняється для специфічних
структур. Деякі з них описують розв’язок як достатнє присвоєння,
тоді як інші вимагають його оптимальності. Комплексний погляд на
різні означення представляє ступінь зв’язності, що для кожного оці-
нює простір оптимальних присвоєнь, що задовольняє початковим
умовам. Мета – структури дають можливість базовим структурам
можуть також пояснювати поняття структури. Їхні специфікації опи-
сують основні структури як класи (чи приклади) мета – структур.
Задоволення обмежень з ваговими коефіцієнтами
Проблема задоволення обмежень розглядається з точки зору за-
стосування ряду технік: вагових коефіцієнтів, вартісних коефіцієнтів,
штрафних коефіцієнтів та оптимізаційних технік [55]. Основна ідея
даних підходів полягає в мінімізації значень для певних кортежів в
усіх обмеженнях. Розглядаються різні означення, наприклад для ва-
гових коефіцієнтів обмежень з метою їх мінімізації для випадку неза-
доволених обмежень. Найбільш часто вживаним прикладом задач
CSP з ваговими коефіцієнтами є задача MAX – CSP, що реалізує ідею
задоволення максимальної кількості накладених обмежень[56].
Означення 1 (обмеження, проблема) Обмеженням з ваговим ко-
ефіцієнтом є пара ( , ( ))c w c , з c як класичним обмеженням і ( )w c W ,
що задає ваговий коефіцієнт обмеження c як елемента впорядкованої
множини W . Множина W впорядкована згідно з відношенням впоря-
92