Алгоритм AC-3 — Вікіпедія

Алгори́тм АС-3 (скор. Алгоритм Дуг Послідовності № 3) — це один із серії алгоритмів, які використовуються для розв'язання зада́ч викона́ння обме́жень (скор. CSP). Він був розроблений Аланом Макворсом у 1977. Перші АС алгоритми вважалися неефективними, а інші, новіші, складними для використання. АС-3 алгоритм є одним із найбільш вживаних. Його часто використовують у дуже простих розв'язувачах задач.

Алгоритм[ред. | ред. код]

АС-3 оперує константами, змінними та доменами (областями) змінних. Змінна може приймати будь-які з декількох дискретних значень; набір значень для конкретної змінної називається доменом. Обмеження — це відношення, що лімітує значення змінної, які вона може мати.

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

Для ілюстрації, ось приклад дуже простої задачі задоволення обмежень: Х (змінна) може приймати значення {0, 1, 2, 3, 4, 5} — набір цих значень є областю Х, або D(X). Відповідно змінна Y має область D(Y)={0, 1, 2, 3, 4, 5}. Разом з обмеженнями С1="X має бути парним" і С2="Х + Y повинні дорівнювати 4" ми маємо CSP, яку може розв'язати алгоритм АС-3. Зверніть увагу, що фактичний граф обмежень, що представляє цю задачу, повинен мати два ребра між X і Y, так як С2 неорієнтований. При цьому графічне представлення, що використовується алгоритмом АС-3 є орієнтованим.

Це досягається наступним шляхом. Спочатку видаляються не парні значення з області Х (цього потребує обмеження С1). Після цього в області D(X) залишаться значення {0, 2, 4}. Потім алгоритм перевіряє дуги між Х і Y (обмеження С2). Для цього обмеження підходять лише пари (X = 0, Y = 4), (X = 2, Y = 2), і (X = 4, Y =0). Потім АС-3 завершує роботу, залишаючи D(X) = {0, 2, 4} і D(Y) = {0, 2, 4}.

АС-3, представлений псевдокодом, виглядає наступним чином:

 Вхідні данні:  *Набір змінних Х  *Набір областей D(X) для кожної змінної х в Х. D(X) містить vx0, vx1... vxn, - можливі значення х  *Набір унарних обмежень R1(x), які мають бути виконані над змінною x  *Набір бінарних обмежень R2(x, y), які мають бути виконані над змінними x та y  Вихідні данні:  *Дуги послідовностей областей для кожної змінної

 function ac3 (X, D, R1, R2)  // Початкові області відповідні до унарних обмежень.      for each x in X          D(x) := { x in D(x) | R1(x) }         // 'worklist' містить усі дуги, які ми хочемо довести як послідовні.      worklist := { (x, y) | there exists a relation R2(x, y) or a relation R2(y, x) }        do          select any arc (x, y) from worklist          worklist := worklist - (x, y)          if arc-reduce (x, y)               if D(x) is empty                  return failure              else                  worklist := worklist + { (z, x) | z != y and there exists a relation R2(x, z) or a relation R2(z, x) }      while worklist not empty    function arc-reduce (x, y)      bool change = false      for each vx in D(x)          find a value vy in D(y) such that vx and vy satisfy the constraint R2(x, y)          if there is no such vy {              D(x) := D(x) - vx              change := true          }      return change

The algorithm has a worst-case time complexity of O(ed³) and space complexity of O(e), where e is the number of arcs and d is the size of the largest domain.