Обратная маркировка

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

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

Пример, в котором поиск достиг первого раза. ${\displaystyle x_{i}=d}$

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

Первая информация собирается и сохраняется каждый раз, когда алгоритм оценивает переменную как , и выполняется путем простой проверки согласованности текущих назначений для , для , для и т. д. ${\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}}$

Когда поиск выполняется во второй раз, часть пути совпадает с первым. ${\displaystyle x_{i}=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}=a}$ ${\displaystyle x_{i}}$ ${\displaystyle x_{i}=a}$ ${\displaystyle k}$ ${\displaystyle x_{i}}$ ${\displaystyle j}$ ${\displaystyle x_{1},\ldots ,x_{j},x_{i}}$ ${\displaystyle x_{i}}$ ${\displaystyle a}$

1. если , то оценка по -прежнему остается противоречивой, как и прежде, поскольку ни одна из этих переменных до сих пор не изменилась; в результате дополнительная проверка согласованности не требуется; ${\displaystyle j<k}$ ${\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.