Локальна сумісність

Ідея перевірки локальної сумісності лягла в основу швидкого методу розповсюдження обмежень, який є значно потужнішим порівняно з попередньою перевіркою. Стани локальної сумісності є властивостями задач виконання обмежень (CSP). Перевірка локальної сумісності забезпечується розширенням методу розповсюдження обмежень. Найвідомішими сумісностями є: сумісність дуг, сумісність вузла і сумісність шляху.

Положення

Розповсюдження обмеження (constraint propagation) — це загальна назва методів розповсюдження на інші змінні наслідків застосування деякого обмеження до однієї змінної; в даному випадку необхідно розповсюдити обмеження з WA і Q на NT і SA, а потім — на обмеження між NT і SA, щоб виявити зазначену несумісність. До того ж бажано, щоб така операція виконувалася швидко: немає сенсу обмежувати таким чином обсяг пошуку, якщо буде витрачатися більше часу на поширення обмежень, ніж на виконання простого пошуку.

Локальна сумісність (K-сумісність)

Строгіші форми розповсюдження обмеження можна визначити за допомогою поняття k-сумісності. Задача CSP є k-сумісною, якщо для будь-якої множини k-1 змінних і для будь-якого сумісного присвоювання значень цим змінним будь-якій k-й змінній завжди можна присвоїти деяке сумісне значення. Наприклад, 1-сумісність означає, що сумісною є кожна окрема змінна сама по собі, це поняття називають також сумісністю вузла. Далі, 2-сумісність — те саме, що й сумісність дуги, а 3-сумісність означає, що будь-яка пара суміжних змінних завжди може бути доповнена третьою сусідньою змінною; це поняття іменується також сумісністю шляху.

Будь-який граф називається строго k-сумісним, якщо він є k-сумісним, а також (к-1)-сумісним, (к-2)-сумісним, … і т. д. аж до 1-сумісного. Тепер припустимо, що є деяка задача CSP з вузлами n, яка зроблена строго n-сумісною (тобто строго k-сумісною для k=n). Тоді це завдання можна вирішити без повернень. Для цього спочатку можна вибрати сумісне значення для x₁. В такому випадку існує гарантія, що вдасться обрати значення для х₂, оскільки граф є 2-сумісним, для х₃, оскільки він — 3-сумісний, і т. д. Для кожної змінної x_i необхідно виконати пошук тільки серед d значень в її області визначення, щоб знайти значення, сумісний з x₁ .., x_i-1. Це означає, що гарантується перебування рішення за час O(nd). Безумовно, за таку можливість також доводиться платити: будь-який алгоритм забезпечення n-сумісності в найгіршому випадку повинен вимагати часу, експоненційно залежного від n.

Сумісність дуг

Ідея перевірки сумісності дуг лягла в основу швидкого методу розповсюдження обмежень. У цьому випадку термін дуга позначає орієнтоване ребро в графі обмежень, таке як дуга від SA до NSW. Якщо розглядаються поточні області визначення SA і NSW, то дуга є сумісною, якщо для кожного значення х змінної SA існує деяке значення у змінної NSW, сумісний із х. У третьому рядку на рис. 3 поточними областями визначення SA і NSW є {blue} і (red, blue) відповідно. При SA = blue існує сумісне присвоювання для NSW, а саме NSW = red, тому дуга від SA до NSW сумісна. З іншого боку, зворотна дуга від NSW до SA несумісна, оскільки стосовно присвоєння NSW = blue не існує сумісного присвоювання для SA. Цю дугу можна зробити сумісною, видаливши значення blue з області визначення NSW.

На тому ж етапі в процесі пошуку перевірку сумісності дуг можна також застосувати до дуги від SA до NT Третій рядок таблиці, наведеної на рис. 3, показує, що обидві змінні мають область визначення {blue}. Результатом стає те, що значення blue повинно бути видалено з області визначення SA, після чого ця область визначення залишається порожньою. Таким чином, застосування перевірки сумісності дуг привело до раннього виявлення несумісності.

Перевірку сумісності дуг можна використовувати або як етап попередньої обробки перед початком процесу пошуку, або як етап розповсюдження обмеження (аналогічно попередній перевірці) після кожного присвоювання під час пошуку. (Останній алгоритм іноді називають MAC, скорочено позначаючи метод підтримки сумісності дуг — Maintaining Arc Consistency.) І в тому і в іншому випадку процес перевірки необхідно виконувати повторно, до тих пір, поки не перестануть виявлятися будь-які несумісності. Це пов'язано з тим, що при видаленні (з метою усунення деякої несумісності дуг) будь-якого значення з області визначення деякої змінної може з'явитися нова несумісність дуг в тих дугах, які вказують на цю змінну. У повному алгоритмі перевірки сумісності дуг, АС-3, використовується черга для відстеження дуг, які повинні бути перевірені на несумісність (лістинг 1). Кожна дуга (x_i, x_j) по черзі «знімається з порядку денного» і перевіряється; якщо з області визначення x_i необхідно видалити будь-які значення, то кожна дуга (Х_k, x_i), яка вказує на x_i, повинна бути повторно вставлена в чергу для перевірки. Складність перевірки сумісності дуг можна проаналізувати наступним чином: будь-яка бінарна задача CSP має щонайбільше O(n²) дуг; кожна дуга (x_k, x_i) може бути «внесена до порядку денного» тільки d раз, оскільки область визначення x_i має щонайбільше d значень, доступних для видалення; перевірка сумісності будь дуги може бути виконана за час O(d²), тому в найгіршому випадку витрати часу становлять O(n²d³). Хоча такий метод є значно дорожчим у порівнянні з попередньою перевіркою, всі ці додаткові витрати зазвичай окупаються

Алгоритм перевірки сумісності дуг АС-3

function АС-3 (csp) returns визначення завдання CSP, можливо, зі скороченими областями визначення змінних
  inputs: csp, бінарна задача CSP зі змінними {Xi, Х2, ..., Хп}
  local variables: queue, чергу, складається з дуг, яка спочатку включає всі дуги з визначення завдання csp
  while черга queue не пуста do
    (Xi, Xj) ← Remove-First (gueue)
    if Remove-Inconsistent-Values (Xi, Xj) then
      for each Xk in Neighbors [Xi] do
        додати (Xk, Xi) до черги queue
function Remove-Inconsistent-Values(Xi, Xj) returns Значення true тоді й тільки тоді, коли відбулося видалення деякого значення
  removed ← false
  for each х in Domain [Xi] do
    if жодне із значень у в області визначення Domain [Xj] не дозволяє використовувати (х, у) для задоволення обмеження, встановленого між Xi і Xj
      then видалити х з області визначення Domain [Xi]
      removed <— true
  return removed

Після застосування алгоритму АС-3 або кожна дуга є сумісною, або деяка змінна має порожню область визначення, вказуючи на те, що цю задачу CSP неможливо зробити сумісною по дугах (і тому дана задача CSP не може бути вирішена). Позначення «АС-3» запропоновано розробником даного алгоритму, оскільки це — третя версія, представлена в його статті

Сумісність шляху

x1 і x2 не сумісні шляхом, до х3. Вони можуть бути зроблені сумісні шляхом, якщо видалити сині значення з R12.

Сумісність шляху схожа на сумісність дуг, але передбачає пари змінних замість однієї. Пара змінних є шляхо-сумісною до третьої, якщо кожна сумісність пари може бути розширена на іншу змінну при тому що обмеження для двох змінних залишаються виконуваними. Формально x_i і x_j є шляхо-сумісні до x_k, якщо для кожної пари значень (a, b), що задовольняє подвійному обмеженню між x_i і x_j, існує значення с в області x_k таке, що (a, c) і (b, c) задовольняє обмеження між x_i і x_k і між x_j і x_k, відповідно.

Форма розповсюдження обмежень, що забезпечує сумісність шляху працює шляхом видалення деяких застосувань, що виконуються з обмежень. Дійсно, сумісність шляху може бути забезпечена шляхом видалення з двійкового обмеження всіх оцінок, які не можуть бути поширені на інший змінні. Що стосується сумісності дуги, то подібне видалення, можливо, призведе до розгляду двійкового обмеження кілька разів.

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

Для забезпечення сумісноті шляху x1 та x2 з x3 прибираємо дугу зверху. Значення x1 and x2 більше не є вільними, бо пов'язані новим актуальним обмеженням.

Форма розповсюдження обмежень, що забезпечує сумісність шляху може ввести нові обмеження. Коли дві змінні не пов'язані між собою двійковим обмеженням, вони віртуально пов'язані обмеженням що дозволяє будь-яку кількість значень. Однак, деякі пари значень можуть бути видалені з розповсюдження обмежень. В результаті обмеження більше не задовольняє всі пари значень. Таким чином, це вже не віртуальний, тривіальні обмеження.

Застосування

Всі форми локальної сумісності можуть бути забезпечені за допомогою розповсюдження обмежень, яке може зменшити області змінних і наборів застосувань, що задовольнить обмеження і може ввести нові обмеження. Кожного разу, коли розповсюдження обмежень створює порожню область або нездійсненні обмеження, вихідна задача нездійсненна. Таким чином, всі форми локальної сумісності можуть бути використані для визначення здійсненності. Точніше, вони можуть бути використані як неповні алгоритми нездійсненності, так як вони можуть довести, що проблема є нездійсненною, але в цілому не в змозі довести, що завдання здійсненне. Такі алгоритми апроксимації можуть бути використані алгоритмами пошуку (backtracking, backjumping, local search, etc.), як евристики для повідомлення чи може часткове рішення бути розширенн, щоб задовольнити всі обмеження без подальшого його аналізу.

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

Локальна сумісність доводить здійснимість в деяких обмежених випадках (див. Складність задоволення обмежень). Це той випадок, для деякого особливого роду проблем і/або для деяких видів локальної сумісності. Наприклад, забезпечення узгодженості сумісності дуг на бінарних ациклічних задачах дозволяє сказати, чи є задача здійснимою.

Література

• Stuart, Russell; Peter Norvig (2004). Artificial Intelligence: A Modern Approach. Prentice Hall. ISBN 3-8273-7089-2. Архів оригіналу за 7 листопада 2017. Процитовано 15 березня 2012.
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3. Архів оригіналу за 7 листопада 2017. Процитовано 15 березня 2012.