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(ed3) and space complexity of O(e), where e is the number of arcs and d is the size of the largest domain.