Шектеулерді қанағаттандырудағы жергілікті үйлесімділік шарттары

Шектеулерді қанағаттандыруда, жергілікті сәйкестік шарттары – мәселенің шешу кеңістігін қысқартуға көмектесетін, айнымалылар мен шектеулер жиынтығының үйлесімділігін анықтайтын қасиеттер.

20 мин оқу

100%

Дереккөз: Local consistency — Wikipedia

Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.

Мазмұны

Кіріспе

Шектілік қанағаттандыруда жергілікті тұрақтылық шарттары – айнымалылар немесе шектеулердің ішінара жиынтықтарының тұрақтылығымен байланысты шектеу қанағаттандыру мәселелерінің қасиеттері. Олар іздеу кеңістігін қысқарту және мәселені шешуді жеңілдету үшін қолданылады. Түйіндік тұрақтылық, доғалық тұрақтылық және жол тұрақтылығы сияқты жергілікті тұрақтылық шарттарының түрлі нұсқалары бар. Кез келген жергілікті тұрақтылық шартын мәселенің шешімдерін өзгертпей оны өзгертетін түрлендіру арқылы сақтауға болады; мұндай түрлендіру шектеу тарату деп аталады. Шектеу тарату айнымалылардың мәндік облыстарын қысқарту, шектеулерді күшейту немесе жаңа шектеулер жасау арқылы жұмыс істейді. Бұл іздеу кеңістігінің қысқаруына және кейбір алгоритмдермен мәселені шешудің оңайлануына әкеледі. Шектеу тарату қанағаттандырылмаушылықты тексеру құралы ретінде де қолданылуы мүмкін, ол әдетте толық емес, бірақ кейбір жағдайларда толық. Жергілікті тұрақтылық шарттарын әртүрлі сыныптарға бөлуге болады. Бастапқы жергілікті тұрақтылық шарттары кез келген сәйкес ішінара белгілеуді (белгілі бір түрдегі) басқа айнымалыға сәйкес кеңейтуге болатынын талап етеді. Бағытталған тұрақтылық тек басқа айнымалы берілген тәртіп бойынша белгілеудегі айнымалыдан үлкен болған кезде ғана бұл шарттың орындалуын талап етеді. Қатынастық тұрақтылық бірден көп айнымалыға кеңейтулерді қамтиды, бірақ бұл кеңейту тек берілген шектеуді немесе шектеулер жиынтығын қанағаттандыру үшін ғана қажет.

Қорытындылар

Бұл мақалада шектеулерді қанағаттандыру мәселесі айнымалылар жиынтығы, домендер жиынтығы және шектеулер жиынтығы ретінде анықталады. Айнымалылар мен домендер байланысты: айнымалының домені, айнымалының қабылдай алатын барлық мәндерін қамтиды. Шектеу, оның қолжеткісі деп аталатын айнымалылар тізбегінен және олардың бағалаулары жиынтығынан тұрады, бұл бағалаулар шектеуді қанағаттандырады. Осы мақалада қарастырылатын шектеулерді қанағаттандыру мәселелері ерекше формада деп есептеледі. Мәселе нормаланған формада, тиісінше реттелген формада болады, егер әрбір айнымалылар тізбегі ең көп дегенде бір шектеудің немесе дәл бір шектеудің қолжеткісі болса. Екілік шектеулерге ғана қатысты жүйелілік болжамы стандартталған формаға әкеледі. Бұл шарттарды әрқашан бір тізбектегі барлық шектеулерді біріктіру және/немесе тізбектегі барлық мәндерді қанағаттандыратын шектеуді қосу арқылы сақтауға болады. Осы мақалада қолданылған суреттерде екі айнымалы арасындағы байланыстың болмауы, осы екі айнымалы арасында ешқандай шектеу немесе барлық мәндерді қанағаттандыратын шектеу жоқ екенін көрсетеді.

Жергілікті жүйелілік

"Стандартты" жергілікті сәйкестік шарттарының бәрі, барлық сәйкес жарым-жартылай бағалаулардың басқа айнымалыға сондай етіп кеңейтілуін қажет етеді, нәтижесіндегі тағайындама сәйкес болады. Жарым-жартылай бағалау, егер ол тағайындалған айнымалылардың ішкі жиыны болып табылатын барлық шектеулерді қанағаттандырса, сәйкес деп есептеледі.

Тораптық сәйкестік

Тораптық сәйкестік талабы бойынша, айнымалыға қатысты әрбір бірлік шектеу, айнымалының доменіндегі барлық мәндерді қанағаттандыруы керек, және керісінше. Бұл шартты әр айнымалының доменін, сол айнымалыға қатысты барлық бірлік шектеулерді қанағаттандыратын мәндерге дейін қысқарту арқылы оңай орындауға болады. Осының нәтижесінде, бірлік шектеулерді ескермеуге және олар домендерге енгізілген деп қарауға болады. Мысалы, домені {1, 2, 3, 4, 5} және шектеуі x > 2 бар айнымалы берілген болса, тораптық сәйкестік доменді {3, 4, 5} дейін шектейді, ал шектеуді алып тастауға болады. Бұл алдын ала өңдеу қадамы келесі кезеңдерді жеңілдетеді.

Қисық консистенциясы

Егер оның қабылданған мәндерінің әрқайсысы екінші айнымалының қабылданған мәндерімен үйлесімді болса, шектеуді қанағаттандыру мәселесінің айнымалысы екіншісімен доғалық сәйкестікте болады. Формальды түрде, егер айнымалысының доменінің әрбір мәні үшін айнымалысының доменінде айнымалысы мен айнымалысы арасындағы екілік шектеуді қанағаттандыратын мәні болса, айнымалысы айнымалысымен доғалық сәйкестікте болады. Мәселе доғалық сәйкестікте болады, егер әрбір айнымалы басқа әрбір айнымалымен доғалық сәйкестікте болса. Мысалы, шектеуін қарастырайық, онда айнымалылар 1-ден 3-ке дейінгі доменде өзгереді. ештеңе 3-ке тең бола алмайтындықтан, мәніне доға жоқ, сондықтан оны алып тастау қауіпсіз. Сол сияқты, ештеңе 1-ге тең бола алмайтындықтан, доға жоқ, сондықтан оны алып тастауға болады. Доғалық сәйкестікті нақты екілік шектеуге қатысты да анықтауға болады: егер бір айнымалының әрбір мәні екінші айнымалының мәнімен шектеуді қанағаттандырса, онда екілік шектеу доғалық сәйкестікте болады. Бұл доғалық сәйкестіктің анықтамасы жоғарыдағы анықтамаға ұқсас, бірақ нақты шектеуге қатысты берілген. Бұл айырмашылық, әсіресе, нормаланбаған мәселелер үшін маңызды, онда жоғарыдағы анықтама екі айнымалы арасындағы барлық шектеулерді қарастырады, ал бұл анықтама тек нақты шектеуді қарастырады. Егер айнымалы екінші айнымалымен доғалық сәйкестікте болмаса, оны оның доменінен кейбір мәндерді алып тастау арқылы жасауға болады. Бұл доғалық сәйкестікті қамтамасыз ететін шектеу тарату түрі: ол айнымалының доменінен екінші айнымалының мәніне сәйкес келмейтін әрбір мәнді алып тастайды. Бұл түрлендіру мәселенің шешімдерін сақтайды, өйткені алынып тасталған мәндер ешқандай шешімде болмайды. Шектеу таратуы барлық айнымалы жұптары үшін осы алып тастауды қайталау арқылы бүкіл мәселені доғалық сәйкестікке жеткізе алады. Бұл процесте берілген айнымалы жұбын бірнеше рет қарастыру қажет болуы мүмкін. Шындығында, айнымалының доменінен мәндерді алып тастау басқа айнымалылардың онымен доғалық сәйкестікте болмауына себеп болуы мүмкін. Мысалы, егер айнымалысы айнымалысымен доғалық сәйкестікте болса, бірақ алгоритм айнымалысының доменін азайтады, онда айнымалысының айнымалысымен доғалық сәйкестігі енді сақталмайды және оны қайтадан қамтамасыз ету қажет. Жай ғана алгоритм айнымалы жұптары бойынша циклды жүргізеді, доғалық сәйкестікті қамтамасыз етеді және домендердің ешқайсысы цикл бойы өзгермегенше циклды қайталайды. AC-3 алгоритмі соңғы талдалғаннан бері өзгертілмеген шектеулерді елемеу арқылы бұл алгоритмнен жақсырақ. Атап айтқанда, ол бастапқыда барлық шектеулерді қамтитын шектеулер жиынтығында жұмыс істейді; әр қадамда ол шектеуді алып, доғалық сәйкестікті қамтамасыз етеді; егер бұл операция басқа шектеуде доғалық сәйкестіктің бұзылуына әкелсе, ол осы шектеуді талдау үшін шектеулер жиынтығына қайтарады. Осылайша, доғалық сәйкестік шектеуде күштелгеннен кейін, егер оның бір айнымалысының домені өзгермесе, бұл шектеу қайта қарастырылмайды.

A variable of a constraint satisfaction problem is arc consistent with another one if each of its admissible values are consistent with some admissible value of the second variable. Formally, a variable is arc consistent with another variable if, for every value in the domain of there exists a value in the domain of such that satisfies the binary constraint between and A problem is arc consistent if every variable is arc consistent with every other one. For example, consider the constraint where the variables range over the domain 1 to 3. Because can never be 3, there is no arc from 3 to a value in so it is safe to remove. Likewise, can never be 1, so there is no arc, therefore it can be removed. Arc consistency can also be defined relative to a specific binary constraint: a binary constraint is arc consistent if every value of one variable has a value of the second variable such that they satisfy the constraint. This definition of arc consistency is similar to the above, but is given specific to a constraint. This difference is especially relevant for non normalized problems, where the above definition would consider all constraints between two variables while this one considers only a specific one. If a variable is not arc consistent with another one, it can be made so by removing some values from its domain. This is the form of constraint propagation that enforces arc consistency: it removes, from the domain of the variable, every value that does not correspond to a value of the other variable. This transformation maintains the problem solutions, as the removed values are in no solution anyway. Constraint propagation can make the whole problem arc consistent by repeating this removal for all pairs of variables. This process might have to consider a given pair of variables more than once. Indeed, removing values from the domain of a variable may cause other variables to become no longer arc consistent with it. For example, if is arc consistent with but the algorithm reduces the domain of , arc consistency of with does not hold any longer, and has to be enforced again. A simplistic algorithm would cycle over the pairs of variables, enforcing arc consistency, repeating the cycle until no domains change for a whole cycle. The AC 3 algorithm improves over this algorithm by ignoring constraints that have not been modified since they were last analyzed. In particular, it works on a set of constraints that initially contains all constraints; at each step, it takes a constraint and enforces arc consistency; if this operation may have produced a violation of arc consistency over another constraint, it places that constraint back in the set of constraints to analyze. This way, once arc consistency is enforced on a constraint, this constraint is not considered again unless the domain of one of its variables is changed.

Жолдың сәйкестігі (k-сәйкестігі)

Жол тұрақтылығы – доға тұрақтылығына ұқсас қасиет, бірақ бір ғана емес, екі айнымалы жұбын қарастырады. Егер жұптың кез келген тұрақты мәні басқа айнымалыға барлық екілік шектеулер орындалатындай етіп кеңейтілсе, онда айнымалылар жұбы үшінші айнымалымен жол тұрақтылығын сақтайды. Формальды түрде, егер және арасындағы екілік шектеуді қанағаттандыратын кез келген мән жұбы үшін, доменде және арасындағы және арасындағы шектеулерді қанағаттандыратын мән болса, онда олар жол тұрақтылығын сақтайды. Жол тұрақтылығын қамтамасыз ететін шектеу таратуы шектеуден қанағаттандыратын белгілі бір тапсырманы жою арқылы жұмыс істейді. Шындығында, жол тұрақтылығын басқа айнымалыға кеңейтілмейтін екілік шектеудегі барлық мәндерді жою арқылы қамтамасыз етуге болады. Доға тұрақтылығындағыдай, бұл жою үшін екілік шектеуді бірнеше рет қарастыру қажет болуы мүмкін. Доға тұрақтылығындағыдай, алынған мәселе бастапқы мәселенің сол шешімдерін сақтайды, себебі жойылған мәндер ешқандай шешімде болмайды. Жол тұрақтылығын қамтамасыз ететін шектеу таратуы жаңа шектеулерді енгізе алады. Егер екі айнымалы екілік шектеумен байланысты болмаса, олар кез келген мән жұбына рұқсат беретін жасырын шектеумен байланысты болып саналады. Дегенмен, кейбір мән жұптары шектеу тарату арқылы жойылуы мүмкін. Нәтижесінде алынған шектеу енді барлық мән жұптарымен қанағаттандырылмайды. Сондықтан ол енді жасырын, қарапайым шектеу емес. "Жол тұрақтылығы" атауы бастапқы анықтамадан шыққан, онда бір жұп айнымалы және олардың арасындағы жол қарастырылған, бір жұп емес. Екі анықтама бір жұп айнымалы үшін әртүрлі болғанымен, олар бүкіл мәселеге қатысты эквивалентті.

Жалпылау

Арка мен жол консистенттілігін екілік емес шектеулерге, айнымалылардың жұптарының орнына топтамаларын қолдану арқылы жалпылауға болады. Егер айнымалылардың кез келген консистентті бағалауы басқа айнымалының мәнімен консистенттілікті сақтай отырып кеңейтілсе, онда айнымалылардың топтамасы басқа айнымалымен консистентті болады. Бұл анықтама барлық проблемаларға оңай түсінікті түрде қолданылады. 2-консистенттіліктің ерекше жағдайы арка консистенттілігімен сәйкес келеді (осы мақалада барлық проблемалар түйіндік консистентті деп есептеледі). Ал 3-консистенттілік жол консистенттілігімен тек барлық шектеулер екілік болған жағдайда ғана сәйкес келеді, себебі жол консистенттілігі үштік шектеулерді қарастырмайды, ал 3-консистенттілік қарастырады. Арка консистенттілігін жалпылаудың тағы бір тәсілі – гиперарка консистенттілігі немесе жалпыланған арка консистенттілігі, ол шектеуді қанағаттандыру үшін бір айнымалының кеңейтілуін қажет етеді. Яғни, егер айнымалының кез келген мәні шектеуді қанағаттандыратындай етіп, шектеудің басқа айнымалыларына кеңейтілсе, онда айнымалы шектеумен консистентті гиперарка болып табылады.

Ерекше жағдайлар

Салыстырмалы тұрақтылық туралы кейбір анықтамалар немесе нәтижелер тек ерекше жағдайларда ғана қолданылады. Домендер бүтін сандардан тұрғанда, байланған тұрақтылықты анықтау мүмкін. Осы тұрақтылық түрі домендердің ең шекті мәндерінің – яғни, айнымалының қабылдай алатын ең кішкентай және ең үлкен мәндерінің – тұрақтылығына негізделген. Егер шектеулер алгебралық немесе логикалық болса, доғалық тұрақтылық жаңа шектеу қосуға немесе ескі шектеуді синтаксистік тұрғыдан өзгертуге баламалы, және мұны шектеулерді тиісті түрде біріктіру арқылы іске асыруға болады.

Арнайы шектеулер

Кейбір шектеулер жиі қолданылады. Мысалы, кейбір айнымалылардың барлығы әртүрлі деген шектеу жиі қолданылады. Мұндай шектеулерге қақпақ сәйкестігін қамтамасыз ету үшін тиімді арнайы алгоритмдер бар. Бірнеше айнымалыны әртүрлі болуға мәжбүрлейтін шектеу әдетте alldifferent([X1, ..., Xn]) деп жазылады. Бұл шектеу әр түрлі айнымалылардың барлық жұптарының теңсіздігіне тең, яғни кез келген айнымалының домені бір мәнге дейін төмендетілген кезде, бұл мән доғаның сәйкестігін жүзеге асыру кезінде шектеу тарату арқылы барлық басқа домендерден алынып тасталуы мүмкін. Мамандандырылған шектеуді пайдалану жеке бинарлық теңсіздіктерге жатпайтын қасиеттерді пайдалануға мүмкіндік береді. Бірінші қасиет - барлық айнымалылар доменіндегі элементтердің жалпы саны кем дегенде айнымалылардың санына тең болуы керек. Нақтырақ айтқанда, доғалық сәйкестік орнатылғаннан кейін тағайындалмаған айнымалылардың саны олардың домендерінің бірігіндегі мәндер санынан аспауы тиіс. Әйтпесе, шектеу орындалмайды. Бұл жағдай әртүрлі формадағы шектеуде оңай тексерілуі мүмкін, бірақ теңсіздіктер желісінің доғалық сәйкестігіне сәйкес келмейді. Бірде-бір әр түрлі шектеудің екінші қасиеті - гипер доғаның тұрақтылығын екі жақты сәйкестендіру алгоритмін қолдану арқылы тиімді тексеруге болады. Атап айтқанда, график екі түйін жиынтығы ретінде айнымалылар мен мәндермен құрылады және ондағы сәйкестікті тексеру үшін арнайы екі жақты графикті сәйкестендіру алгоритмі орындалады. Әдетте қолданылатын шектеудің басқа түрі - жинақтаушы (cumulative) шектеу. Ол кестелеу және орналастыру мәселелеріне енгізілген. Мысалы, cumulative([S1, ..., Sm], [D1, ..., Dm], [R1, ..., Rm], L) әрқайсысының басталу уақыты si, ұзақтығы di және ресурстың мөлшері ri бар m іс-әрекеттердің жағдайын ресмилендіру үшін пайдаланылуы мүмкін. Шектеуде ресурстардың жалпы қол жетімді мөлшері L деп көрсетілген. Жинақтаушы шектеулер үшін арнайы шектеу тарату әдістері бар; қай айнымалы домендерінің бір мәнге дейін төмендетілгеніне байланысты әр түрлі әдістер қолданылады. Логикалық шектеулер бағдарламалауда қолданылатын үшінші арнайы шектеу - элемент (element) шектеу. Шектеу логикасы бағдарламалауда тізімдерге айнымалылардың мәндері ретінде рұқсат етіледі. Егер L тізім болса және X осы тізімнің I-інші элементі болса, онда шектеу element(I, L, X) орындалады. Бұл шектеулер үшін арнайы шектеу тарату ережесі бар. Мысалы, егер L және I бір мәндік доменге дейін қысқартылса, X үшін бірегей мән анықталуы мүмкін. Жалпы алғанда, X-тің мүмкін емес мәндері L-дің доменінен және керісінше шығаруға болады.

Some kinds of constraints are commonly used. For example, the constraint that some variables are all different are often used. Efficient specialized algorithms for enforcing arc consistency on such constraints exist. The constraint enforcing a number of variables to be different is usually written or alldifferent([X1, ,Xn]). This constraint is equivalent to the non equality of all pairs of different variables, that is, for every When the domain of a variable is reduced to a single value, this value can be removed from all other domains by constraint propagation when enforcing arc consistency. The use of the specialized constraint allows for exploiting properties that do not hold for individual binary disequalities. A first property is that the total number of elements in the domains of all variables must be at least the number of variables. More precisely, after arc consistency is enforced, the number of unassigned variables must not exceed the number of values in the union of their domains. Otherwise, the constraint cannot be satisfied. This condition can be checked easily on a constraint in the alldifferent form, but does not correspond to arc consistency of the network of disequalities. A second property of the single alldifferent constraint is that hyper arc consistency can be efficiently checked using a bipartite matching algorithm. In particular, a graph is built with variables and values as the two sets of nodes, and a specialized bipartite graph matching algorithm is run on it to check the existence of such a matching. A different kind of constraint that is commonly used is the cumulative one. It was introduced for problems of scheduling and placement. As an example, cumulative([S1, ,Sm], [D1, ,Dm], [R1, ,Rm], L) can be used to formalize the condition in which there are m activities, each one with starting time si, duration di and using an amount ri of a resource. The constraint states that the total available amount of resources is L. Specialized constraint propagation techniques for cumulative constraints exists; different techniques are used depending on which variable domains are already reduced to a single value. A third specialized constraint that is used in constraint logic programming is the element one. In constraint logic programming, lists are allowed as values of variables. A constraint element(I, L, X) is satisfied if L is a list and X is the I th element of this list. Specialized constraint propagation rules for these constraints exist. As an example, if L and I are reduced to a single value domain, a unique value for X can be determined. More generally, impossible values of X can be inferred from the domain of and vice versa.

Бағыттылық сәйкестігі

Бағыттық сәйкестік – берілген айнымалылар тізбегі бойынша айнымалыларға мәндер тағайындайтын алгоритм үшін арналған қисық, жол және сәйкестіктің ерекше түрі. Олар бағытсыз аналогтарына ұқсас, бірақ тек кейбір айнымалыларға дұрыс тағайындалған сәйкестікті, тізбек бойынша олардан кейін келетін басқа айнымалыға да дұрыс кеңейтуді талап етеді.

Бағыттамалық доға мен жолдың сәйкестігі

Егер алгоритм өзгермелілерді , ретімен бағаласа, сәйкестік тек қана төменгі индексті өзгермелілердің мәндері жоғары индексті өзгермелілердің мәндерімен сәйкес келетініне кепілдік берген жағдайда ғана пайдалы. Өзгермеліге мән таңдағанда, тағайындалмаған өзгермелінің барлық мәндерімен сәйкес келмейтін мәндерді ескермеуге болады. Шындығында, егер осы мәндер қазіргі ішінара бағалаумен сәйкес келсе де, алгоритм кейін тағайындалмаған өзгермелі үшін сәйкес мән табуға сәтсіздікке ұшырайды. Екінші жағынан, бұрын бағаланған өзгермелілермен сәйкестікті қамтамасыз етудің қажеті жоқ: егер алгоритм ағымдағы ішінара бағалауға сәйкес келмейтін мәнді таңдаса, сәйкессіздік әйтеуір анықталады. Егер өзгермелілерді бағалау реті , болса, шектеуді қанағаттандыру мәселесі бағытталған түрде доғалық сәйкестікке ие, егер әрбір өзгермелі кез келген басқа өзгермелімен сәйкес болса. Бағытталған жол сәйкестігі де ұқсас, бірақ екі өзгермелінің жол бойынша сәйкес болуы үшін ғана қажет. Күшті бағытталған жол сәйкестігі – бұл бағытталған жол сәйкестігі мен бағытталған доға сәйкестігінің біріктірілген түрі. Сәйкестіктің басқа да түрлері үшін де ұқсас анықтамалар беруге болады.

Арка мен жолдың біркелкілігі үшін шектеудің таралуы

Бағытталған доғаның тұрақтылығын қамтамасыз ететін шектеу тарату, айнымалыларды соңғыдан біріншіге қарай итерациялайды, әр қадамда одан төменгі индекске ие әрбір айнымалының доғалық тұрақтылығын қамтамасыз етеді. Егер айнымалылардың реті , болса, бұл алгоритм айнымалылар бойынша ; үшін , ол индексі төменгі әрбір айнымалының доғалық сәйкестігін қамтамасыз етеді . Бағытталған доғалық тұрақтылығы жоқ мысал: кез келген мәнге сәйкес келмейді және кез келген мәнге сәйкес келмейді. және арасында шектеу жоқ (тиісті қабырғалар жойылған). Бағытталған доғалық тұрақтылықты қамтамасыз ету , -ден басталады және онымен доғалық тұрақтылықты қамтамасыз ету үшін мәнді жояды. Бағытталған доғалық тұрақтылықты қамтамасыз ету , -мен жалғасады. Бұрыннан жойылғандықтан, екі және де жойылады. Бағытталған жолдың тұрақтылығы және күшті бағытталған жолдың тұрақтылығы доғалық тұрақтылық үшін қолданылатын алгоритмдарға ұқсас алгоритмдермен қамтамасыз етілуі мүмкін. Олар ; әрбір айнымалы үшін екі айнымалы қарастырылады, және олардың жол сәйкестігі қамтамасыз етіледі. Егер мәселеде және арасында шектеу болмаса, операция қажет емес. Дегенмен, егер арасында шектеу болмаса да, тривиальды шектеу деп есептеледі. Егер шектеу тарату қанағаттандыратын тапсырмалар жиынтығын азайтатын болса, ол тиімді түрде жаңа тривиальды емес шектеуді жасайды. Шекара тарату күшті бағытталған жолдың тұрақтылығын қамтамасыз етеді, бірақ сонымен қатар доғалық тұрақтылықты да қамтамасыз етеді.

Бағыттамалық сәйкестік және қанағаттанушылық

Бағыттық сәйкестік, шектеуді қанағаттандыратын ішінара шешімдердің жоғары индексті басқа айнымалыға сәйкес келуін қамтамасыз етеді. Дегенмен, ол әртүрлі айнымалыларға жасалған кеңейтулердің бір-бірімен сәйкес келетініне кепілдік бермейді. Мысалы, ішінара шешімді тұрақты түрде бір немесе екінші айнымалыға кеңейтуге болады, бірақ бұл екі кеңейту бір-бірімен сәйкес келмейді. Мұндай жағдай екі рет туындамайды, және егер ешқандай домен бос болмаса және ешқандай шектеу қанағаттандырылмайтын болса, бағыттық сәйкестік қанағаттандырылатынын қамтамасыз етеді. Бірінші жағдай – айнымалылардың реттелген тізбегімен сипатталатын, ені 1-ге тең шектеу графигі бар бинарлық шектеу мәселесі. Мұндай реттеу тек қана шектеулер графигі ағаш болған жағдайда ғана мүмкін. Егер осылай болса, графиктің ені реттелген тізбек бойынша төменгі орналасқан түйіндердің максималды санын шектейді. Бағыттық доғаның сәйкестігі, әрбір сәйкес айнымалыға жасалған тағайындаманы жоғары орналасқан түйіндерге кеңейтуге кепілдік береді, ал ені 1 болса, түйін бірден артық төменгі түйінге қосылмайды. Осылайша, төменгі айнымалыға мән берілгеннен кейін, оның мәні оған қосылған барлық жоғары айнымалыларға сәйкес кеңейтіледі. Бұл кеңейту кейіннен қайшылыққа әкелмейді, себебі графиктің ені 1 болғандықтан, басқа төменгі айнымалы жоғары айнымалыға қосылмайды. Нәтижесінде, егер шектеу мәселесінің айнымалылар тізбегіне қатысты ені 1 болса (яғни, оның графигі ағаш болса) және мәселе сол тізбек бойынша бағыттық сәйкестікке ие болса, онда шешімді (бар болса) айнымалыларды тізбек бойынша қайталап тағайындау арқылы табуға болады. Егер ешқандай домен бос болмаса және ешқандай шектеу қанағаттандырылмайтын болса, бағыттық сәйкестік қанағаттандырылатынының екінші жағдайы – күшті бағыттық жол сәйкестігін қолданатын, 2 ені бар графигі бар бинарлық шектеу мәселесі. Шындығында, мұндай сәйкестік әрбір айнымалыға немесе айнымалылар жұбына жасалған тағайындаманы жоғары айнымалыға кеңейтуге кепілдік береді, ал ені 2 болса, бұл айнымалы төменгі айнымалылардың басқа жұбына қосылмайды. Ендік орнына индуцирленген енді қарастырудың себебі – бағыттық жол сәйкестігін қолдану шектеулерді қосуы мүмкін. Шындығында, егер екі айнымалы бір шектеуде болмаса, бірақ жоғары айнымалымен шектеуде болса, олардың кейбір мәндері жол сәйкестігін бұзуы мүмкін. Мұндай жұптарды жою жаңа шектеуді тудырады. Нәтижесінде, шектеу таратуы бастапқыдан көбірек жиектері бар мәселені тудыруы мүмкін. Алайда, барлық осы жиектер міндетті түрде индуцирленген графикте болады, себебі олардың барлығы бір түйіннің екі ата-анасы арасында орналасқан. 2 ені, әрбір сәйкес ішінара бағалауды шешімге дейін кеңейтуге кепілдік береді, бірақ бұл ен құрылған графиктің қасиетіне байланысты. Нәтижесінде, күшті бағыттық жол сәйкестігінің шешімдердің болуын қамтамасыз етуі үшін индуцирленген ені 2 болуы қажет.

Directional consistency guarantees that partial solutions satisfying a constraint can be consistently extended to another variable of higher index. However, it does not guarantee that the extensions to different variables are consistent with each other. For example, a partial solution may be consistently extended to variable or to variable , but yet these two extensions are not consistent with each other. There are two cases in which this does not happen, and directional consistency guarantees satisfiability if no domain is empty and no constraint is unsatisfiable. The first case is that of a binary constraint problem with an ordering of the variables that makes the ordered graph of constraint having width 1. Such an ordering exists if and only if the graph of constraints is a tree. If this is the case, the width of the graph bounds the maximal number of lower (according to the ordering) nodes a node is joined to. Directional arc consistency guarantees that every consistent assignment to a variable can be extended to higher nodes, and width 1 guarantees that a node is not joined to more than one lower node. As a result, once the lower variable is assigned, its value can be consistently extended to every higher variable it is joined with. This extension cannot later lead to inconsistency. Indeed, no other lower variable is joined to that higher variable, as the graph has width 1. As a result, if a constraint problem has width 1 with respect to an ordering of its variables (which implies that its corresponding graph is a tree) and the problem is directionally arc consistent with respect to the same ordering, a solution (if any) can be found by iteratively assigning variables according to the ordering. The second case in which directional consistency guarantees satisfiability if no domain is empty and no constraint is unsatisfiable is that of binary constraint problems whose graph has induced width 2, using strong directional path consistency. Indeed, this form of consistency guarantees that every assignment to a variable or a pair of variables can be extended to a higher variable, and width 2 guarantees that this variable is not joined to another pair of lower variables. The reason why the induced width is considered instead of the width is that enforcing directional path consistency may add constraints. Indeed, if two variables are not in the same constraint but are in a constraint with a higher variable, some pairs of their values may violate path consistency. Removing such pairs creates a new constraint. As a result, constraint propagation may produce a problem whose graph has more edges than the original one. However, all these edges are necessarily in the induced graph, as they are all between two parents of the same node. Width 2 guarantees that every consistent partial evaluation can be extended to a solution, but this width is relative to the generated graph. As a result, induced width being 2 is required for strong directional path consistency to guarantee the existence of solutions.

Бағытты i-салмақтылығы

Бағыттық сәйкестік – өзгермелілерге жасалған әрбір дәйекті тапсырманы реті жоғарырақ басқа өзгермеліге дәйекті түрде кеңейтуге болатындығының кепілі. Күшті бағыттық сәйкестік ұқсас түрде анықталады, бірақ барлық айнымалылардың топтары қарастырылады. Егер мәселе күшті бағыттық сәйкестікке ие болса, ені шектеулі болса, және бос домендер немесе қанағаттандырылмаған шектеулер болмаса, онда оның шешімі бар. Кез келген мәселені күшті бағыттық сәйкестікке келтіруге болады, бірақ бұл операция оның сәйкес графигінің енін арттыруы мүмкін. Бағыттық сәйкестікті қамтамасыз ететін шектеу тарату процедурасы бағыттық доғалық сәйкестік және жол сәйкестігі үшін қолданылатын процедураға ұқсас. Өзгермелілер ретімен қарастырылады, соңғысынан біріншісіне қарай. Белгілі бір өзгермелі үшін алгоритм одан төмен индекске ие және осы өзгермелімен шектеуде болатын барлық өзгермелілердің топтарын қарастырады. Осы өзгермелілердің сәйкестігі тексеріледі және мүмкін болса, осы барлық өзгермелілер арасындағы шектеуден қанағаттандыратын тапсырмаларды алып тастау арқылы (бар болса, немесе әйтпесе жаңасын жасау арқылы) күшпен орындалады. Бұл процедура күшті бағыттық сәйкестікке ие мысал тудырады. Дегенмен, ол мысалға жаңа шектеулер қосуы мүмкін. Нәтижесінде, бастапқы мәселенің ені болса да, алынған мысалдың ені үлкен болуы мүмкін. Егер осылай болса, бағыттық күшті сәйкестік, тіпті ешқандай домен бос болмаса және ешқандай шектеу қанағаттандырылмаса да, қанағаттандырылуын білдірмейді. Алайда, шектеу таратуы тек қазіргі уақытта қарастырылып отырғаннан төменгі өзгермелілерге шектеулер қосады. Нәтижесінде, алгоритм осы өзгермелімен айналысқаннан кейін ешқандай шектеу өзгертілмейді немесе қосылмайды. Белгілі бір енді қарастырудың орнына, оны қарастырылып жатқан әрбір өзгермелінің ата-аналарының санына өзгертуге болады (өзгермелінің ата-аналары – өзгермеліден төмен индекске ие және осы өзгермелімен шектеуде болатын өзгермелілер). Бұл әрбір қадамда берілген өзгермелінің барлық ата-аналарын қарастыруға сәйкес келеді. Басқаша айтқанда, соңғысынан біріншісіне дейінгі әрбір өзгермелі үшін оның барлық ата-аналары олардың мәндерін сәйкес келетіндермен шектейтін жаңа шектеуге кіреді. Бұл алгоритмді бұрынғысының өзгеруі ретінде қарастыруға болады, онда әрбір түйіннің ата-аналарының санына өзгерген мән, ол бейімделуші сәйкестік деп аталады. Бұл алгоритм мәселенің еніне тең бағыттық сәйкестікті күшпен орындайды. Алынған мысал тек егер ешқандай домен немесе шектеу бос болмаса ғана қанағаттандырылады. Егер осылай болса, шешімді оңай табуға болады, тағайындалмаған өзгермеліні кездейсоқ мәнге қайталана орнату және осы ішінара бағалауды басқа өзгермелілерге тарату арқылы. Бұл алгоритм әрқашан полиномиалдық уақытта орындалмайды, өйткені күшті бағыттық сәйкестікті күшпен орындау арқылы енгізілген шектеулер саны экспоненциалдық көлемді ұлғайтуы мүмкін. Алайда, егер күшті бағыттық сәйкестікті күшпен орындау мысалдың көлемін суперполиномиалдық түрде арттырмаса, бұл мәселе полиномиалдық уақытта шешіледі. Нәтижесінде, егер мысал тұрақтымен шектелген енді индукцияласа, оны полиномиалдық уақытта шешуге болады.

Directional consistency is the guarantee that every consistent assignment to variables can be consistently extended to another variable that is higher in the order. Strong directional consistency is defined in a similar way, but all groups of at most variables are considered. If a problem is strongly directionally consistent and has width less than and has no empty domain or unsatisfiable constraint, it has solutions. Every problem can be made strongly directionally consistent, but this operation may increase the width of its corresponding graphs. The constraint propagation procedure that enforces directional consistency is similar to that used for directional arc consistency and path consistency. The variables are considered in turn, from the last to the first according to the order. For variable , the algorithm considers every group of variables that have index lower than and are in a constraint with Consistency of these variables with is checked and possibly enforced by removing satisfying assignments from the constraint among all these variables (if any, or creating a new one otherwise). This procedure generates a strongly directional consistent instance. However, it may also add new constraints to the instance. As a result, even if the width of the original problem is , the width of the resulting instance may be greater. If this is the case, directional strong consistency does not imply satisfiability even if no domain is empty and no constraint is unsatisfiable. However, constraint propagation only adds constraints to variables that are lower than the one it is currently considering. As a result, no constraint over a variable is modified or added once the algorithm has dealt with this variable. Instead of considering a fixed , one can modify it to the number of parents of each considered variable (the parents of a variable are the variables of index lower than the variable and that are in a constraint with the variable). This corresponds to considering all parents of a given variables at each step. In other words, for each variable from the last to the first, all its parents are included in a new constraint that limits their values to the ones that are consistent with Since this algorithm can be seen as a modification of the previous one with a value that is changed to the number of parents of each node, it is called adaptive consistency. This algorithm enforces strongly directional consistency with equal to the induced width of the problem. The resulting instance is satisfiable if and only if no domain or constraint is made empty. If this is the case, a solution can be easily found by iteratively setting an unassigned variable to an arbitrary value, and propagating this partial evaluation to other variables. This algorithm is not always polynomial time, as the number of constraints introduced by enforcing strong directional consistency may produce an exponential increase of size. The problem is however solvable in polynomial time if the enforcing strong directional consistency does not superpolynomially enlarge the instance. As a result, if an instance has induced width bounded by a constant, it can be solved in polynomial time.

Құраны жою

Шектеуді жою – қанағаттандыру алгоритмі. Оны адаптивті консистенцияны қайта құру ретінде анықтауға болады. Оның анықтамасында шектеулерді сақтауға арналған контейнерлер – бөліктер қолданылады, әр айнымалыға сәйкес бөлік бар. Шектеу әрқашан ең жоғары айнымалының бөлігіне жатады. Шектеуді жою алгоритмі жоғары айнымалыдан төменгі айнымалыға қарай жүзеге асырылады. Әр қадамда осы айнымалының бөлігіндегі шектеулер қарастырылады. Анықтама бойынша, бұл шектеулер тек төменгі айнымалыларды ғана қамтиды. Алгоритм осы төменгі айнымалылар арасындағы шектеуді өзгертеді (егер бар болса, болмаса жаңасын жасайды). Атап айтқанда, олардың мәндерін осы айнымалының бөлігіндегі шектеулермен сәйкес келуге мүмкіндік береді. Егер жаңа шектеу болса, ол тиісті бөлікке орналастырылады. Бұл шектеу тек төменгі айнымалыларды қамтитындықтан, ол төменгі айнымалылардың бөлігіне қосылады.

Бұл алгоритм адаптивті консистенцияны қамтамасыз етуге тең. Олар екеуі де айнымалының барлық «ата-аналарымен» консистенциясын қамтамасыз етеді және айнымалы қарастырылғаннан кейін жаңа шектеулер қосылмайды, нәтижесінде артқа қайтусыз шешілетін мысал пайда болады. Олар жасайтын мысалдың графигі индукцияланған графиктің ішкі графигі болғандықтан, егер индукцияланған ен тұрақтымен шектелсе, алынған мысал бастапқы мысалдың өлшеміне полиномдық болады. Осылайша, егер мысалдың индукцияланған ені тұрақтымен шектелсе, оны екі алгоритмнің көмегімен полиномдық уақытта шешуге болады.

Қарым-қатынас тұрақтылығы

Бұрынғы бірқалыптылық анықтамалары тапсырмалардың сәйкестігі туралы болса, қатынастық бірқалыптылық тек берілген шектеуді немесе шектеулер жиынтығын қанағаттандыруды қамтиды. Нақтырақ айтқанда, қатынастық сәйкестілік – кез келген сәйкес ішінара тапсырманы белгілі бір шектеу немесе шектеулер жиынтығы қанағаттандырылатындай етіп кеңейтуге болады дегенді білдіреді. Формальды түрде, айнымалыларға қатысты шектеу, егер оның айнымалыларының біріне сәйкес келсе, кез келген сәйкес тапсырманы сол айнымалыға осындай жолмен кеңейтуге болады. «Жай» сәйкестілік пен қатынастық доға сәйкестілігінің арасындағы айырмашылық – соңғысы тек берілген шектеуді қанағаттандыру үшін кеңейтілген тапсырманы талап етеді, ал біріншісі барлық қатысты шектеулерді қанағаттандыруды талап етеді. Бұл анықтаманы бірнеше шектеуге және бірнеше айнымалыға қолдануға болады. Атап айтқанда, қатынастық жол сәйкестігі қатынастық доға сәйкестігіне ұқсас, бірақ біреуінің орнына екі шектеу қолданылады. Екі шектеу, егер олардың барлық айнымалыларына сәйкес келетін кез келген сәйкес тапсырма, бірақ қарастырылып отырған біреуі екі шектеуді қанағаттандыратындай етіп кеңейтілсе, айнымалымен қатынастық жол сәйкестігінде болады. Екіден астам шектеулер үшін қатынастық сәйкестілік анықталады. Қатынастық сәйкестілік шектеулер жиынтығын және осы шектеулердің барлық аясындағы айнымалыны қамтиды. Атап айтқанда, егер олардың аясындағы барлық басқа айнымалыларға кез келген сәйкес тапсырманы осы шектеулер қанағаттандырылатындай етіп айнымалыға кеңейтуге болады, онда бұл шектеулер айнымалымен сәйкес келеді. Мәселе қатынастық сәйкес болады, егер шектеулердің кез келген жиынтығы олардың барлық аясындағы кез келген айнымалымен қатынастық сәйкес болса. Күшейтілген қатынастық сәйкестілік жоғарыда көрсетілгендей анықталады: қатынастық сәйкестілік бір емес, бірнеше айнымалы үшін де анықталуы мүмкін. Шектеулер жиынтығы қатынастық сәйкес болады, егер олардың айнымалыларының кез келген ішкі жиынына кез келген сәйкес тапсырманы барлық айнымалыларға барлық шектеулерді қанағаттандыратын мәнге дейін кеңейтуге болады. Бұл анықтама жоғарыдағы анықтаманы толыққанды түрде кеңейте алмайды, өйткені мәндерді кеңейтуге болатын айнымалылар міндетті түрде барлық шектеулердің аясында болуы керек. Егер айнымалылардың реті берілген болса, қатынастық сәйкестік айнымалыларға мән беруді реттегі басқа айнымалылардан кейін ғана жасаумен шектелуі мүмкін. Бұл өзгертілген жағдай бағытталған қатынастық сәйкестік деп аталады.

While the previous definitions of consistency are all about consistency of assignments, relational consistency involves satisfaction of a given constraint or set of constraints only. More precisely, relational consistency implies that every consistent partial assignment can be extended in such a way that a given constraint or set of constraints is satisfied. Formally, a constraint on variables is relational arc consistent with one of its variables if every consistent assignment to can be extended to in such a way is satisfied. The difference between "regular" consistency and relational arc consistency is that the latter only requires the extended assignment to satisfy a given constraint, while the former requires it to satisfy all relevant constraints. This definition can be extended to more than one constraint and more than one variable. In particular, relational path consistency is similar to relational arc consistency, but two constraints are used in place of one. Two constraints are relational path consistent with a variable if every consistent assignment to all their variables but the considered one can be extended in such a way the two constraints are satisfied. For more than two constraints, relational consistency is defined. Relational consistency involves a set of constraints and a variable that is in the scope of all these constraints. In particular, these constraints are relational consistent with the variable if every consistent assignment to all other variables that are in their scopes can be extended to the variable in such a way these constraints are satisfied. A problem is relational consistent if every set of constraints is relational consistent with every variable that is in all their scopes. Strong relational consistency is defined as above: it is the property of being relational consistent for every
Relational consistency can also be defined for more variables, instead of one. A set of constraints is relational consistent if every consistent assignment to a subset of of their variables can be extended to an evaluation to all variables that satisfies all constraints. This definition does not exactly extends the above because the variables to which the evaluations are supposed to be extendible are not necessarily in all scopes of the involved constraints. If an order of the variables is given, relational consistency can be restricted to the cases when the variables(s) the evaluation should be extendable to follow the other variables in the order. This modified condition is called directional relational consistency.

Қарым-қатынас сәйкестігі және қанағаттанушылық

Шектілік қанағаттандыру мәселесі қатынастық тұрғыдан дәйекті болуы мүмкін, бос домені немесе қанағаттандырылмаған шектеуі болмауы мүмкін, бірақ бәрібір қанағаттандырылмауы мүмкін. Дегенмен, мұндай болмайтын жағдайлар да бар. Бірінші жағдай – домендері ең көп дегенде элементтерді қамтитын, күшті қатынастық дәйектілікке ие мәселе. Бұл жағдайда, айнымалылардың дәйекті бағалауын әрқашан бір ғана басқа айнымалыға дейін кеңейтуге болады. Егер мұндай бағалау болса және сол айнымалы болса, онда айнымалының алуға болатын тек бірнеше мүмкін мәні болады. Егер осы мәндердің барлығы бағалаумен үйлесімсіз болса, онда бағалау мен оның мүмкін мәндерінің бірі бұзылған (қажетті түрде бірегей емес) шектеулер болады. Нәтижесінде, бағалау осы немесе одан да аз шектеулерді қанағаттандыру үшін кеңейтілмейді, күшті қатынастық дәйектілік шартын бұзады. Екінші жағдай, домендерге емес, шектеулердің сипаттамасына қатысты. Егер кез келген бағалау, оның барлық айнымалылары үшін, біреуін қоспағанда, қалған айнымалының барлық мүмкін мәндерімен немесе оның көпшілігімен шектеуді қанағаттандыру үшін кеңейтілсе, онда шектеу тығыз болады. Тығыз шектеулері бар мәселелер күшті қатынастық дәйектілікке ие болған жағдайда ғана қанағаттандырылады. Үшінші жағдай – қатарлы дөңгелек матрицалармен бейнеленетін бинарлық шектеулер. Бинарлық шектеуді екі өлшемді матрица арқылы көрсетуге болады , мұнда -ның доменіндегі мәні мен -ның доменіндегі мәні шектеуді қанағаттандыра ма, жоқ па, соған байланысты 0 немесе 1 болады. Матрицаның қатары, егер ондағы 1-дер тізбекпен орналасқан болса (формальды түрде, егер екі элемент 1-ге тең болса, арасындағы барлық элементтер де 1-ге тең болады), дөңгелек болып саналады. Матрицаның барлық қатарлары дөңгелек болса, онда ол қатарлы дөңгелек матрица болады. Күшті қатынастық жол дәйектілігін қанағаттандыруға теңестіретін жағдай – бұл барлық шектеулерді қатарлы дөңгелек матрицалармен бейнелейтін айнымалылардың реті бар шектеулерді қанағаттандыру мәселесі. Бұл нәтиже, жұптық ортақ элементі бар дөңгелек қатарлар жиынтығында да жалпы ортақ элемент болатындығына негізделген. Айнымалыларға бағалауды қарастыратын болсақ, -шы айнымалы үшін рұқсат етілген мәндер кейбір шектеулерден қатарларды таңдау арқылы анықталады. Атап айтқанда, айнымалының әрқайсысы үшін, онымен байланысты шектеуді көрсететін матрицадағы оның мәніне қатысты қатар, соңғысының рұқсат етілген мәндерін көрсетеді. Бұл қатарлар дөңгелек болғандықтан және жол дәйектілігіне байланысты олардың жұптық ортақ элементтері бар, олардың да ортақ ортақ элементі бар, ол басқаларымен үйлесімді соңғы айнымалының мәнін көрсетеді.

A constraint satisfaction problem may be relationally consistent, have no empty domain or unsatisfiable constraint, and yet be unsatisfiable. There are however some cases in which this is not possible. The first case is that of strongly relational consistent problem when the domains contain at most elements. In this case, a consistent evaluation of variables can be always extended to a single other variable. If is such an evaluation and is the variable, there are only possible values the variable can take. If all such values are inconsistent with the evaluation, there are (non necessarily unique) constraints that are violated by the evaluation and one of its possible values. As a result, the evaluation cannot be extended to satisfy all these or less constraints, violating the condition of strong relational consistency. The second case is related to a measure of the constraints, rather than the domains. A constraint is tight if every evaluation to all its variables but one can be extended to satisfy the constraint either by all possible values of the other variable or by at most of its values. Problem having tight constraints are satisfiable if and only if they are strongly relationally consistent. The third case is that of binary constraints that can be represented by row convex matrices. A binary constraint can be represented by a bidimensional matrix , where is 0 or 1 depending on whether the th value of the domain of and the th value of the domain of satisfy the constraint. A row of this matrix is convex if the 1's it contains are consecutive (formally, if two elements are 1, all elements in between are 1 as well). A matrix is row convex if all its rows are convex. The condition that makes strong relational path consistency equivalent to satisfiability is that of constraint satisfaction problems for which there exists an order of the variables that makes all constraint to be represented by row convex matrices. This result is based on the fact that a set of convex rows having a common element pairwise also have a globally common element. Considering an evaluation over variables, the allowed values for the th one are given by selecting some rows from some constraints. In particular, for every variable among the ones, the row relative to its value in the matrix representing the constraint relating it with the one represents the allowed values of the latter. Since these row are convex, and they have a common element pairwise because of path consistency, they also have a shared common element, which represents a value of the last variable that is consistent with the other ones.

Жергілікті тұрақтылықтың қолданылуы

Жергілікті консистенцияның барлық түрлері шектеу тарату арқылы қамтамасыз етілуі мүмкін, бұл айнымалылар домендерін және шектеуді қанағаттандыратын тапсырмалар жиынтығын азайтуға, сондай-ақ жаңа шектеулерді енгізуге әкелуі мүмкін. Егер шектеу тарату бос доменді немесе қанағаттандырылмайтын шектеуді тудырса, бастапқы мәселе қанағаттандырылмайды. Сондықтан, жергілікті консистенцияның барлық түрлерін қанағаттандыру шамасы ретінде пайдалануға болады. Нақтырақ айтқанда, оларды толық емес қанағаттандыру емеуі алгоритмдері ретінде қолдануға болады, себебі олар мәселенің қанағаттандырылмайтынын дәлелдей алады, бірақ көбінесе мәселенің қанағаттандырылатынын дәлелдей алмайды. Мұндай шамаланған алгоритмдерді іздеу алгоритмдері (қайтару, артқа секіру, жергілікті іздеу және т.б.) жартылай шешімді одан әрі талдаусыз барлық шектеулерді қанағаттандыру үшін кеңейтуге болатынын анықтау үшін эвристика ретінде пайдалануы мүмкін. Тіпті егер шектеу тарату бос доменді немесе қанағаттандырылмайтын шектеуді тудырмаса да, ол домендерді азайтуға немесе шектеулерді күшейтуге мүмкін. Егер осылай болса, мәселенің іздеу кеңістігі азаяды, демек мәселені шешу үшін қажетті іздеу көлемі азаяды. Жергілікті консистенция кейбір шектеулі жағдайларда қанағаттандыруға болатынын дәлелдейді (қ. қараңыз, Шектеулерді қанағаттандырудың күрделігі#Шектеулер). Бұл кейбір ерекше мәселелер үшін және/немесе жергілікті консистенция түрлері үшін орынды. Мысалы, бинарлық ациклді мәселелерде доғалық консистенцияны қамтамасыз ету мәселенің қанағаттандырылатынын анықтауға мүмкіндік береді. Күшті бағытталған консистенцияны қамтамасыз ету бірдей тәртіп бойынша туындаған ені бар мәселелердің қанағаттандырылатынын көрсетуге мүмкіндік береді. Адаптивті бағытталған консистенция кез келген мәселенің қанағаттандырылатынын анықтауға мүмкіндік береді.