Backmarking - Википедия - Backmarking

В удовлетворение ограничений, обратная маркировка это вариант возврат алгоритм.

Backmarking работает как обратное отслеживание, итеративно оценивая переменные в заданном порядке, например, ${ displaystyle x_ {1}, ldots, x_ {n}}$. Это улучшает обратное отслеживание, сохраняя информацию о том, когда в последний раз переменная ${ displaystyle x_ {i}}$ был создан для значения и информации о том, что изменилось с тех пор. Особенно:

Пример, в котором поиск достиг xi = d в первый раз.

1. для каждой переменной ${ displaystyle x_ {i}}$ и ценность ${ displaystyle a}$, алгоритм записывает информацию о последнем разе ${ displaystyle x_ {i}}$ был установлен на ${ displaystyle a}$; в частности, он хранит минимальный индекс ${ displaystyle j$ так что назначение на ${ displaystyle x_ {1}, ldots, x_ {j}, x_ {i}}$ было тогда непоследовательный;
2. для каждой переменной ${ displaystyle x_ {i}}$, алгоритм сохраняет некоторую информацию относительно того, что изменилось с момента последней оценки. ${ displaystyle x_ {i}}$; в частности, он хранит минимальный индекс ${ Displaystyle к <я}$ переменной, которая была изменена с тех пор.

Первая информация собирается и сохраняется каждый раз, когда алгоритм оценивает переменную. ${ displaystyle x_ {i}}$ к ${ displaystyle a}$, и выполняется простой проверкой согласованности текущих назначений для ${ displaystyle x_ {1}, x_ {i}}$, за ${ displaystyle x_ {1}, x_ {2}, x_ {i}}$, за ${ displaystyle x_ {1}, x_ {2}, x_ {3}, x_ {i}}$, так далее.

Когда поиск достигает xi = d во второй раз, часть пути такая же, как и в первый раз.

Вторая информация меняется каждый раз еще один переменная оценивается. В частности, индекс «максимальной неизменной переменной с момента последней оценки ${ displaystyle x_ {i}}$"возможно изменяется каждый раз, когда другая переменная ${ displaystyle x_ {j}}$ меняет значение. Каждый раз произвольная переменная ${ displaystyle x_ {j}}$ изменения, все переменные ${ displaystyle x_ {i}}$ с ${ displaystyle i> j}$ рассматриваются по очереди. Если ${ displaystyle k}$ был их предыдущий связанный индекс, это значение изменяется на ${ displaystyle min (k, j)}$.

Данные, собранные таким образом, используются, чтобы избежать некоторых проверок согласованности. В частности, всякий раз, когда при возврате будет установлено ${ displaystyle x_ {i} = а}$, обратная маркировка сравнивает два индекса относительно ${ displaystyle x_ {i}}$ и пара ${ displaystyle x_ {i} = а}$. Два условия позволяют определить частичную непротиворечивость или несогласованность без проверки ограничений. Если ${ displaystyle k}$ это минимальный индекс переменной, которая изменилась с момента последнего ${ displaystyle x_ {i}}$ был оценен и ${ displaystyle j}$ - минимальный индекс такой, что оценка ${ displaystyle x_ {1}, ldots, x_ {j}, x_ {i}}$ был последовательным в последний раз ${ displaystyle x_ {i}}$ был оценен как ${ displaystyle a}$, тогда:

1. если ${ displaystyle j$, оценка ${ displaystyle x_ {1}, ldots, x_ {j}, x_ {i}}$ по-прежнему непоследовательна, так как ни одна из этих переменных пока не изменилась; в результате больше не требуется проверка согласованности;
2. если ${ displaystyle j geq k}$, оценка ${ displaystyle x_ {1}, ldots, x_ {k}, x_ {i}}$ остается неизменным, как и раньше; это позволяет пропустить некоторые проверки согласованности, но назначение ${ displaystyle x_ {1}, ldots, x_ {i}}$ все еще может быть непоследовательным.

В отличие от других вариантов отслеживания с возвратом, обратная маркировка не уменьшает пространство поиска, а только, возможно, уменьшает количество ограничений, которым удовлетворяет частичное решение.

Рекомендации

• Дехтер, Рина (2003). Обработка ограничений. Морган Кауфманн. ISBN  1-55860-890-7.