Шектеулерді қанағаттандыру мәселелерін шешудегі гибридтік алгоритмдер
Hybrid algorithm (constraint satisfaction)
Шектеулерді қанағаттандыру мәселелерін шешу үшін жасанды интеллект пен операциялық зерттеудегі гибридтік алгоритмдер: әртүрлі әдістердің үйлесімі, тиімділік & артық шектеулер.
Ағылшыншамен салыстырыңыз: абзацты басыңыз — түпнұсқа терезеде ашылады. Абзац астындағы EN түймесі оны мәтін ішінде көрсетеді.
Кіріспе
Жасанды интеллект және шектеулерді қанағаттандыру саласындағы операциялық зерттеулерде гибридті алгоритм екі түрлі әдістің үйлесімі арқылы шектеулерді қанағаттандыру мәселесін шешеді, мысалы, айнымалыны жағдайландыру (кері іздеу, кері секіру және т.б.) және шектеутерді логикалық қорытынды шығару (доғаның сәйкестігі, айнымалыны жою және т.б.). Гибридті алгоритмдер әр түрлі әдістердің тиімді қасиеттерін, оларды тиімді шеше алатын мәселелерге қолдану арқылы пайдаланады. Мысалы, іздеу көптеген шешімдері бар мәселелер үшін тиімді, ал логикалық қорытынды шығару, артық шектеулермен жүктелген мәселелердің шешімі жоқ екенін дәлелдеуде тиімді.
Within artificial intelligence and operations research for constraint satisfaction a hybrid algorithm solves a constraint satisfaction problem by the combination of two different methods, for example variable conditioning (backtracking, backjumping, etc.) and constraint inference (arc consistency, variable elimination, etc.) Hybrid algorithms exploit the good properties of different methods by applying them to problems they can efficiently solve. For example, search is efficient when the problem has many solutions, while inference is efficient in proving unsatisfiability of overconstrained problems.
Ағаш ыдырау гибридті алгоритмі
Тағы бір гибридтік іздеу/қорытындылау алгоритмі ағаш ыдырау арқылы жұмыс істейді. Жалпы, шектеулерді қанағаттандыру мәселесін алдымен ағаш ыдырауын жасау арқылы, содан кейін арнайы алгоритмді қолдану арқылы шешуге болады. Мұндай алгоритмдердің бірі түйіндер арасында шектеулерді таратуға, содан кейін әрбір түйіндегі кіші мәселені шешуге негізделген. Бұл тарату – қосылған түйіндегі түйіннің әсерін көрсететін жаңа шектеулерді құрудан тұрады. Нақтырақ айтқанда, егер екі түйін қосылса, олар ортақ айнымалыларды бөліседі. Бірінші түйіннің шектеулеріне сәйкес осы айнымалылардың рұқсат етілген мәндері бірінші түйіннің екінші түйіннің айнымалыларына қалай әсер ететінін көрсетеді. Алгоритм осы мәндерді қанағаттандыратын шектеуді құру арқылы жұмыс істейді және осы жаңа шектеуді екінші түйінге қосады. Барлық шектеулер жапырақтардан тамырға және кері тамырға таратылған кезде, барлық түйіндерде оларға қатысты барлық шектеулер болады. Сондықтан мәселені әрбір түйінде шешуге болады. Гибридтік тәсілге түйіндер ішінде таралатын жаңа шектеулерді құру үшін айнымалыларды жою әдісін және әрбір жеке түйінде іздеу алгоритмін (мысалы, кері іздеу, кері секіру, жергілікті іздеу) қолдану арқылы қол жеткізуге болады.
Another hybrid search/inference algorithm works on the tree decomposition. In general, a constraint satisfaction problem can be solved by first creating a tree decomposition and then using a specialized algorithm. One such algorithm is based on first propagating constraints among nodes, and then solving the subproblem in each node. This propagation consists in creating new constraints that represent the effects of the constraints in a node over a joined node. More precisely, if two nodes are joined, they share variables. The allowed evaluations of these variables according to the constraints of the first node tell how the first node affects the variables of the second node. The algorithm works by creating the constraint satisfied by these evaluations and incorporating this new constraint in the second node. When all constraints have been propagated from the leaves to the root and back to the root, all nodes contain all constraints that are relevant to them. The problem can therefore be solved in each node. A hybrid approach can be taken by using variable elimination for creating the new constraints that are propagated within nodes, and a search algorithm (such as backtracking, backjumping, local search) on each individual node.