Методы предвидения в алгоритмах возврата: обзор и сравнение.

Введение

В алгоритмах с возвратом (backtracking), "look ahead" – это общий термин для подпрограммы, которая пытается предвидеть последствия выбора разветвляющейся переменной для оценки одного из её возможных значений. Две основные цели "look ahead" – выбрать следующую переменную для оценки и определить порядок присваивания ей значений.

Удовлетворение ограничений

В общей задаче поиска решения при ограничениях каждая переменная может принимать значение из своей области допустимых значений. Алгоритм с возвратом, следовательно, итеративно выбирает переменную и проверяет каждое из её возможных значений; для каждого значения алгоритм запускается рекурсивно. Метод "look ahead" используется для оценки последствий выбора конкретной переменной или для определения порядка присвоения ей значений.

Техники прогнозирования

Простейший метод оценки эффекта конкретного назначения переменной называется форвард-чекингом (forward checking). При наличии текущего частичного решения и кандидата на назначение для оценки, он проверяет, может ли другая переменная принять согласованное значение. Иными словами, сначала текущее частичное решение расширяется предварительным значением для рассматриваемой переменной; затем рассматривается каждая другая переменная, которая ещё не назначена, и проверяется, существует ли такое назначение, которое согласуется с расширенным частичным решением. В более общем плане, форвард-чекинг определяет значения для переменных, которые согласуются с расширенным назначением. Более затратной по времени, но потенциально дающей лучшие результаты, техникой прогноза является обеспечение согласованности дуг (arc consistency). А именно, при заданном частичном решении, расширенном значением для новой переменной, обеспечивается согласованность дуг для всех неназначенных переменных. Другими словами, для любых неназначенных переменных удаляются значения, которые не могут быть согласованно расширены на другую переменную. Различие между форвард-чекингом и обеспечением согласованности дуг заключается в том, что первый проверяет согласованность только одной неназначенной переменной за раз, в то время как второй проверяет пары неназначенных переменных на взаимную согласованность. Наиболее распространенным способом использования прогноза для решения задач удовлетворения ограничений является алгоритм поддержания согласованности дуг (MAC). Два других метода, использующих согласованность дуг, – полный и частичный прогноз. Они обеспечивают согласованность дуг, но не для каждой пары переменных. В частности, полный прогноз рассматривает каждую пару неназначенных переменных и обеспечивает согласованность дуг между ними. Это отличается от обеспечения глобальной согласованности дуг, которое может потребовать повторного рассмотрения пары переменных более одного раза. Вместо этого, как только полный прогноз обеспечил согласованность дуг между парой переменных, эта пара больше не рассматривается. Частичный прогноз аналогичен, но рассматривается заданный порядок переменных, и согласованность дуг обеспечивается только один раз для каждой пары. Прогноз, основанный на согласованности дуг, также может быть расширен для работы с согласованностью путей (path consistency) и общей i-согласованностью (i-consistency) или реляционной согласованностью дуг (relational arc consistency).

The simpler technique for evaluating the effect of a specific assignment to a variable is called forward checking. Given the current partial solution and a candidate assignment to evaluate, it checks whether another variable can take a consistent value. In other words, it first extends the current partial solution with the tentative value for the considered variable; it then considers every other variable that is still unassigned, and checks whether there exists an evaluation of that is consistent with the extended partial solution. More generally, forward checking determines the values for that are consistent with the extended assignment. A look ahead technique that may be more time consuming but may produce better results is based on arc consistency. Namely, given a partial solution extended with a value for a new variable, it enforces arc consistency for all unassigned variables. In other words, for any unassigned variables, the values that cannot consistently be extended to another variable are removed. The difference between forward checking and arc consistency is that the former only checks a single unassigned variable at time for consistency, while the second also checks pairs of unassigned variables for mutual consistency. The most common way of using look ahead for solving constraint satisfaction problems is the maintaining arc consistency (MAC) algorithm. Two other methods involving arc consistency are full and partial look ahead. They enforce arc consistency, but not for every pair of variables. In particular, full look considers every pair of unassigned variables , and enforces arc consistency between them. This is different than enforcing global arc consistency, which may possibly require a pair of variables to be reconsidered more than once. Instead, once full look ahead has enforced arc consistency between a pair of variables, the pair is not considered any more. Partial look ahead is similar, but a given order of variables is considered, and arc consistency is only enforced once for every pair with
Look ahead based on arc consistency can also be extended to work with path consistency and general i consistency or relational arc consistency.