Шектеулерді қанағаттандыру мәселелері

Кіріспе

Шектеулерді қанағаттандыру қажеттілігі бар объектілер жиынтығы

Шектеулерді қанағаттандыру проблемалары (ШҚП) – математикалық сұрақтар, олар белгілі бір шектеулер мен талаптарды қанағаттандыруы тиіс объектілер жиынтығы ретінде анықталады. ШҚП проблемадағы элементтерді айнымалылар бойынша шекті шектеулердің біртекті жиынтығы ретінде көрсетеді, ол шектеуді қанағаттандыру әдістерімен шешіледі. ШҚП жасанды интеллект және операциялық зерттеулер салаларында зерттеу нысаны болып табылады, өйткені олардың тұжырымдамасындағы жүйелілік көптеген байланыссыз мәселелерді талдау және шешу үшін ортақ негіз береді. ШҚП көбінесе жоғары күрделілікпен сипатталады, сондықтан оларды ақылға қонымды уақыт ішінде шешу үшін эвристикалық және комбинаторлық іздеу әдістерін үйлестіру қажет. Шектеулі бағдарламалау (ШБ) – осы проблемаларды шешуге бағытталған зерттеу саласы. Сонымен қатар, Бульдік қанағаттандыру проблемасы (SAT), теориялар бойынша қанағаттандыру (SMT), аралас бүтін санды бағдарламалау (MIP) және жауаптар жиынтығын бағдарламалау (ASP) – бұл шектеуді қанағаттандыру проблемасының нақты түрлерін шешуге бағытталған зерттеу салалары. Шектеуді қанағаттандыру проблемасы ретінде модельдеуге болатын мәселелердің мысалдары:

Түрді анықтау
Сегіз патшайым жұмбағы
Карта бояу мәселесі
Максималды кесім мәселесі
Судоку, кроссвордтар, футошики, Какуро (Кросс-сумма), Нумбрикс/Хидато және көптеген басқа логикалық жұмбақтар

Олар көбінесе ШБ, ASP, Бульдік SAT және SMT шешушілерге арналған оқулықтармен бірге ұсынылады. Жалпы жағдайда, шектеу проблемалары әлдеқайда қиын болуы мүмкін және кейбір осы қарапайым жүйелерде бейнеленбейді. "Нақты өмірдегі" мысалдарға автоматтандырылған жоспарлау, лексикалық мағынасын ажырату, музыкатану, өнім конфигурациясы және ресурстарды бөлу жатады. ШҚП-ге шешімнің болуы шешім қабылдау мәселесі ретінде қарастырылуы мүмкін. Бұл шешімді табу арқылы немесе толық іздеуден кейін шешім таба алмау арқылы шешілуі мүмкін (стохастикалық алгоритмдер әдетте толық қорытындыға ешқашан жетпейді, ал бағытталған іздеулер жеткілікті шағын проблемалар бойынша көбінесе жетеді). Кейбір жағдайларда ШҚП-де шешімдер басқа математикалық қорытындылау процесі арқылы алдын ала белгілі болуы мүмкін.

Шешім

Шектелген домендердегі шектеулерді қанағаттандыру мәселелері әдетте іздеудің бір түрін қолдану арқылы шешіледі. Ең көп қолданылатын техникалар – кері жолмен іздеу, шектеулерді тарату және жергілікті іздеудің түрлері. Бұл техникалар көбінесе біріктіріледі, мысалы, VLNS әдісінде, ал қазіргі зерттеулер сызықтық бағдарламалау сияқты басқа технологияларды қамтиды. Кері жолмен іздеу – рекурсивті алгоритм. Ол айнымалылардың ішінара бекітілуін сақтайды. Бастапқыда барлық айнымалылар бекітілмеген. Әр қадамда бір айнымалы таңдалады және оған кезекпен барлық мүмкін мәндер беріледі. Әрбір мән үшін ішінара бекітілудің шектеулермен үйлесімділігі тексеріледі; үйлесімділік болған жағдайда рекурсивті шақыру жасалады. Барлық мәндер қаралғаннан кейін алгоритм кері қайтады. Бұл қарапайым кері жолмен іздеу алгоритмінде үйлесімділік – барлық өзгермелілері бекітілген барлық шектеулердің орындалуы ретінде анықталады. Кері жолмен іздеудің бірнеше түрі бар. Артық белгілеу үйлесімділікті тексерудің тиімділігін арттырады. Артқа секіру кейбір жағдайларда «бірнеше айнымалыны» кері сүйреп, іздеудің бір бөлігін сақтауға мүмкіндік береді. Шектеулерді үйрену жаңа шектеулерді анықтап, сақтайды, оларды кейін іздеудің бір бөлігін болдырмау үшін пайдалануға болады. Алға қарау да кері жолмен іздеуде айнымалыны немесе мәнді таңдаудың салдарларын болжауға тырысу үшін жиі қолданылады, соның салдарынан кіші мәселенің қанағаттандырылатын немесе қанағаттандырылмайтын екенін алдын ала анықтауға көмектеседі. Шектеулерді тарату техникалары – шектеулерді қанағаттандыру мәселесін өзгерту үшін қолданылатын әдістер. Нақтырақ айтқанда, олар жергілікті үйлесімділікті қамтамасыз ететін әдістер, олар айнымалылар мен/немесе шектеулер тобының үйлесімділігіне қатысты шарттар. Шектеулерді таратудың әр түрлі қолданыстары бар. Біріншіден, ол мәселені оған тең, бірақ әдетте шешу оңайрақ мәселеге айналдырады. Екіншіден, ол мәселенің қанағаттандырылатын немесе қанағаттандырылмайтын екенін дәлелдей алады. Бұл әрқашан бола бермейді, алайда бұл шектеулерді таратудың кейбір түрлері үшін және/немесе белгілі бір мәселелер үшін орын алады. Жергілікті үйлесімділіктің ең танымал және қолданылатын түрлері – доғалық үйлесімділік, гипердоғалық үйлесімділік және жолдық үйлесімділік. Ең танымал шектеулерді тарату әдісі – доғалық үйлесімділікті қамтамасыз ететін AC 3 алгоритмі. Жергілікті іздеу әдістері – толық емес қанағаттандыру алгоритмдері. Олар мәселенің шешімін таба алады, бірақ мәселе қанағаттандырылатын болса да, сәтсіздікке ұшырауы мүмкін. Олар айнымалылар бойынша толық бекітілуді қайталап жақсарту арқылы жұмыс істейді. Әр қадамда айнымалылардың шағын санының мәні өзгертіледі, жалпы мақсат – осы бекітілумен қанағаттандырылатын шектеулердің санын арттыру. Min конфликттер алгоритмі – CSP-ге тән жергілікті іздеу алгоритмі және осы принципке негізделген. Іс жүзінде жергілікті іздеу осы өзгерістер кездейсоқ таңдауларға да байланысты болғанда жақсы жұмыс істейді. Іздеуді жергілікті іздеумен біріктіру дамытылды, нәтижесінде гибридті алгоритмдер пайда болды.

Constraint satisfaction problems on finite domains are typically solved using a form of search. The most used techniques are variants of backtracking, constraint propagation, and local search. These techniques are also often combined, as in the VLNS method, and current research involves other technologies such as linear programming. Backtracking is a recursive algorithm. It maintains a partial assignment of the variables. Initially, all variables are unassigned. At each step, a variable is chosen, and all possible values are assigned to it in turn. For each value, the consistency of the partial assignment with the constraints is checked; in case of consistency, a recursive call is performed. When all values have been tried, the algorithm backtracks. In this basic backtracking algorithm, consistency is defined as the satisfaction of all constraints whose variables are all assigned. Several variants of backtracking exist. Backmarking improves the efficiency of checking consistency. Backjumping allows saving part of the search by backtracking "more than one variable" in some cases. Constraint learning infers and saves new constraints that can be later used to avoid part of the search. Look ahead is also often used in backtracking to attempt to foresee the effects of choosing a variable or a value, thus sometimes determining in advance when a subproblem is satisfiable or unsatisfiable. Constraint propagation techniques are methods used to modify a constraint satisfaction problem. More precisely, they are methods that enforce a form of local consistency, which are conditions related to the consistency of a group of variables and/or constraints. Constraint propagation has various uses. First, it turns a problem into one that is equivalent but is usually simpler to solve. Second, it may prove satisfiability or unsatisfiability of problems. This is not guaranteed to happen in general; however, it always happens for some forms of constraint propagation and/or for certain kinds of problems. The most known and used forms of local consistency are arc consistency, hyper arc consistency, and path consistency. The most popular constraint propagation method is the AC 3 algorithm, which enforces arc consistency. Local search methods are incomplete satisfiability algorithms. They may find a solution of a problem, but they may fail even if the problem is satisfiable. They work by iteratively improving a complete assignment over the variables. At each step, a small number of variables are changed in value, with the overall aim of increasing the number of constraints satisfied by this assignment. The min conflicts algorithm is a local search algorithm specific for CSPs and is based on that principle. In practice, local search appears to work well when these changes are also affected by random choices. An integration of search with local search has been developed, leading to hybrid algorithms.

Шешім қабылдау проблемалары

CSP-лер есептеу күрделілігі теориясы және шекті модельдер теориясында да зерттеледі. Маңызды дихотомия теоремасы бойынша, әрбір қатынастар жиыны үшін, осы жиыннан таңдалған қатынастарды ғана қолдана отырып бейнеленетін барлық CSP жиыны P немесе NP-толық болады. Осылайша, CSP NP-нің белгілі ең ірі қосалқы жиыны болып табылады, ол NP аралық проблемаларынан аулақ болады, олардың болуы Ладнер теоремасымен P ≠ NP болжамында көрсетілген. Шефердің дихотомия теоремасы барлық қолжетімді қатынастар Буль операторлары болған жағдайда қолданылады, яғни доменнің өлшемі 2-ге тең болғанда. Шефердің дихотомия теоремасы кейін қатынастардың кеңірек класына жалпыландырылды, ал толық дихотомия теоремасы алғаш рет Федер-Варди болжамы ретінде ұсынылды және ақырында Андрей Булатов пен Дмитрий Жук тәуелсіз түрде дәлелдеді. Жеңілдетіліп шешілетін CSP-лердің көпшілігінде шектеулердің гиперграфының ағаш ені шектеулі болады (және шектеу қатынастары жиынында ешқандай шектеулер жоқ) немесе шектеулер кез келген формада болуы мүмкін, бірақ шектеу қатынастары жиынының маңызды емес біртұрлы емес полиморфизмдері бар. Кез келген CSP конъюнктивтік сұраныстың кіріктірілу мәселесі ретінде де қарастырылуы мүмкін.

Функционалдық мәселелер

ФП және #P функционалдық сыныптары арасында ұқсас жағдай бар. Ладнер теоремасының жалпылауы бойынша, егер ФП ≠ #P болса, онда ФП-да да, #P-да да толық емес проблемалар бар. Шешімді анықтау жағдайындағыдай, #CSP-дегі проблема қатынастар жиынтығымен сипатталады. Әрбір проблема Буль формуласын кіріс ретінде қабылдайды, ал міндет – қанағаттандыратын тапсырмалардың санын есептеу болып табылады. Бұл одан әрі жалпылауға болады, үлкен домен өлшемдерін пайдаланып және әрбір қанағаттандыратын тапсырмаға салмақ қойып, осы салмақтардың қосындысын есептеу арқылы. Кез келген күрделі салмақты #CSP проблемасы ФП-да немесе #P қиын болып табылады.

Нұсқалар

Шектеулерді қанағаттандыру мәселесінің классикалық моделі өзгермейтін, икемсіз шектеулердің моделін анықтайды. Бұл қатаң модель проблемаларды оңай көрсетуді қиындататын кемшілік. Модельді түрлі проблемаларға бейімдеу үшін негізгі ШҚМ анықтамасына бірнеше түзетутер ұсынылды.

Динамикалық CSP

Динамикалық CSP (DCSP) проблеманың бастапқы формулировкасы қандай да бір жолмен өзгерген кезде пайдалы, әдетте, себебі қоршаған ортаның әсерінен қарастырылатын шектеулер жиынтығы өзгеріп отырады. DCSP – бұл статикалық CSP-лердің тізбегі, олардың әрқайсысы алдыңғысына қарағанда өзгертілген нұсқасы болып табылады, онда айнымалылар мен шектеулер қосылуы (шектеу) немесе алынып тасталуы (босату) мүмкін. Проблеманың бастапқы формулировкаларында алынған ақпарат келесі формулировкаларды жетілдіру үшін қолданылуы мүмкін. Шешу әдісі ақпаратты беру жолына қарай жіктеледі:
Оракулдар: тізбектегі алдыңғы CSP-лерге табылған шешімдер ағымдағы CSP-ні бастапқыдан шешуге бағыт беру үшін эвристика ретінде пайдаланылады. Жергілікті түзету: әрбір CSP алдыңғы CSP-нің ішінара шешімінен бастап есептеледі және жергілікті іздеу арқылы қақтығыстарға себеп болатын шектеулер түзетіледі. Шектеулерді жазу: іздестірудің әр кезеңінде үйлесімсіз шешімдер тобының оқуын көрсету үшін жаңа шектеулер анықталады. Бұл шектеулер жаңа CSP проблемаларына көшіріледі.

Икемді CSP

Классикалық CSP шектеулерді қатал деп қарастырады, яғни олар міндетті (әрбір шешім олардың бәрін қанағаттандыруы тиіс) және өзгеріссіз (толық қанағаттандырылуы керек, әйтпесе толық бұзылады) болады. Икемді CSP-лер бұл талаптарды жеңілдетеді, шектеулерді ішінара босатып, шешімнің олардың бәріне де сәйкес келмеуіне мүмкіндік береді. Бұл, басымдықтарға негізделген жоспарлаудағы басымдықтарға ұқсас. Икемді CSP-лердің кейбір түрлері: MAX CSP, онда бірнеше шектеулерді бұзуға рұқсат етіледі және шешімнің сапасы қанағаттандырылған шектеулер санымен өлшенеді. Салмақты CSP – бұл MAX CSP-нің бір түрі, онда шектеудің әрбір бұзылуы алдын ала белгіленген басымдыққа сәйкес салмақпен есептеледі. Сондықтан, үлкен салмаққа ие шектеуді қанағаттандыру артықшылыққа ие. Fuzzy CSP шектеулерді бұлыңғыр қатынастар ретінде модельдейді, онда шектеудің қанағаттану деңгейі оның айнымалыларының мәндерінің үздіксіз функциясы болып табылады, толық қанағаттанғаннан толық бұзылғанға дейін өзгереді.

Орталықтандырылмаған CSP

DCSP-да әр шектеу айнымалысы дербес географиялық орналасқан жерге ие деп есептеледі. Айналымдар арасындағы ақпарат алмасуға қатаң талаптар қойылады, осы шектеулерді қанағаттандыру мәселесін шешу үшін толыққанды таратылған алгоритмдерді пайдалану қажет.