бэкмаркинг

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

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

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

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

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

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

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

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

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

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

Ссылки

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