Backmarking - Backmarking - Wikipedia

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

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

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

для каждой переменной ${ displaystyle x_ {i}}$ и ценность ${ displaystyle a}$ , алгоритм записывает информацию о последнем разе ${ displaystyle x_ {i}}$ был установлен на ${ displaystyle a}$ ; в частности, он хранит минимальный индекс ${ displaystyle j$ так что назначение на ${ displaystyle x_ {1}, ldots, x_ {j}, x_ {i}}$ было тогда непоследовательный;
для каждой переменной ${ 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}$ , тогда:

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

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

Backmarking - Backmarking - Wikipedia

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