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
   87   88   89   90   91   92   93   94   95   96   97