Алгори́тм АС-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.
Ця стаття не містить . (квітень 2012) |
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algori tm AS 3 skor Algoritm Dug Poslidovnosti 3 ce odin iz seriyi algoritmiv yaki vikoristovuyutsya dlya rozv yazannya zada ch vikona nnya obme zhen skor CSP Vin buv rozroblenij u 1977 Pershi AS algoritmi vvazhalisya neefektivnimi a inshi novishi skladnimi dlya vikoristannya AS 3 algoritm ye odnim iz najbilsh vzhivanih Jogo chasto vikoristovuyut u duzhe prostih rozv yazuvachah zadach AlgoritmAS 3 operuye zminnimi ta domenami oblastyami zminnih Zminna mozhe prijmati bud yaki z dekilkoh diskretnih znachen nabir znachen dlya konkretnoyi zminnoyi nazivayetsya domenom Obmezhennya ce sho limituye znachennya zminnoyi yaki vona mozhe mati CSP mozhe rozglyadatisya yak oriyentovanij graf v yakomu vuzli ce zminni zadachi z rebrami abo dugami mizh nimi sho ob yednani obmezhennyami AS 3 pereviryaye dugi mizh parami zminnih h u Vin vidalyaye ti znachennya z oblasti h i u yaki ne uzgodzhuyutsya z obmezhennyami h i u Algoritm zberigaye kolekciyu dug yaki she ne perevireni koli z oblasti zminnoyi bud yaki znachennya vidaleni vsi dugi obmezhen vklyuchayuchi zminnu okrim potochnoyi dodayutsya do kolekciyi Algoritm garantovano zupinitsya koli hocha b odna duga abo zminna bude vidalena tak yak oblasti ye kincevimi Dlya ilyustraciyi os priklad duzhe prostoyi zadachi zadovolennya obmezhen H zminna mozhe prijmati znachennya 0 1 2 3 4 5 nabir cih znachen ye oblastyu H abo D X Vidpovidno zminna Y maye oblast D Y 0 1 2 3 4 5 Razom z obmezhennyami S1 X maye buti parnim i S2 H Y povinni dorivnyuvati 4 mi mayemo CSP yaku mozhe rozv yazati algoritm AS 3 Zvernit uvagu sho faktichnij graf obmezhen sho predstavlyaye cyu zadachu povinen mati dva rebra mizh X i Y tak yak S2 neoriyentovanij Pri comu grafichne predstavlennya sho vikoristovuyetsya algoritmom AS 3 ye oriyentovanim Ce dosyagayetsya nastupnim shlyahom Spochatku vidalyayutsya ne parni znachennya z oblasti H cogo potrebuye obmezhennya S1 Pislya cogo v oblasti D X zalishatsya znachennya 0 2 4 Potim algoritm pereviryaye dugi mizh H i Y obmezhennya S2 Dlya cogo obmezhennya pidhodyat lishe pari X 0 Y 4 X 2 Y 2 i X 4 Y 0 Potim AS 3 zavershuye robotu zalishayuchi D X 0 2 4 i D Y 0 2 4 AS 3 predstavlenij psevdokodom viglyadaye nastupnim chinom Vhidni danni Nabir zminnih H Nabir oblastej D X dlya kozhnoyi zminnoyi h v H D X mistit vx0 vx1 vxn mozhlivi znachennya h Nabir unarnih obmezhen R1 x yaki mayut buti vikonani nad zminnoyu x Nabir binarnih obmezhen R2 x y yaki mayut buti vikonani nad zminnimi x ta y Vihidni danni Dugi poslidovnostej oblastej dlya kozhnoyi zminnoyi function ac3 X D R1 R2 Pochatkovi oblasti vidpovidni do unarnih obmezhen for each x in X D x x in D x R1 x worklist mistit usi dugi yaki mi hochemo dovesti yak poslidovni 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 Cya stattya ne mistit posilan na dzherela Vi mozhete dopomogti polipshiti cyu stattyu dodavshi posilannya na nadijni avtoritetni dzherela Material bez dzherel mozhe buti piddano sumnivu ta vilucheno kviten 2012