Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка 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.