Обучение с ограничениями

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

Определение

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

Если частичное решение $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ противоречиво, экземпляр задачи подразумевает ограничение, утверждающее, что $x_{i}=a_{i}$ не может быть правдой для всех $i\in [1,k]$ в то же время. Однако запись этого ограничения бесполезна, поскольку это частичное решение больше не встретится из-за способа выполнения обратного поиска.

С другой стороны, если подмножество этой оценки противоречиво, соответствующее ограничение может быть полезно при последующем поиске, поскольку то же самое подмножество частичной оценки может снова встретиться при поиске. Например, алгоритм может столкнуться с оценкой, расширяющей подмножество $x_{2}=a_{2},x_{5}=a_{5},x_{k-1}=a_{k-1}$ предыдущей частичной оценки. Если это подмножество противоречиво и алгоритм сохранил этот факт в форме ограничения, дальнейший поиск не требуется, чтобы сделать вывод о том, что новая частичная оценка не может быть расширена для формирования решения.


Поиск зашел в тупик.	Несоответствие может быть вызвано значениями $x_{1}$ и $x_{4}$ только. Этот факт можно сохранить в новом ограничении.	Если алгоритм достигает тех же значений $x_{1}$ и $x_{4}$ И снова новое ограничение блокирует поиск.

Эффективность обучения в ограничениях

Повышение эффективности обучения в ограничениях балансируется между двумя факторами. С одной стороны, чем чаще нарушается записанное ограничение, тем чаще возврат назад позволяет избежать бесполезного поиска. Небольшие несовместимые подмножества текущего частичного решения обычно лучше больших, поскольку они соответствуют ограничениям, которые легче нарушить. С другой стороны, обнаружение небольшого противоречивого подмножества текущей частичной оценки может потребовать времени, и польза может не быть сбалансирована последующим сокращением времени поиска.

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

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

Обучение на основе графов

Если алгоритм доказывает все значения $x_{k+1}$ быть несовместимым с $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ , то эта оценка была последовательной, так как в противном случае алгоритм не смог бы оценить $x_{k+1}$ совсем; в результате ограничения нарушаются на величину $x_{k+1}$ вместе с $x_{1}=a_{1},\ldots ,x_{k}=a_{k}$ все содержат $x_{k+1}$ .

В результате противоречивая оценка является ограничением истинности оценки $x_{1},\ldots ,x_{k}$ к переменным, которые находятся в ограничении с $x_{k+1}$ , при условии, что это ограничение не содержит неназначенных переменных.

Ограничения обучения, представляющие эту частичную оценку, называются обучением на основе графов. Он использует то же обоснование, что и прыжки назад на основе графов . Эти методы называются «основанными на графах», поскольку они основаны на парах переменных в одном и том же ограничении, которое можно найти из графа, связанного с проблемой удовлетворения ограничений.

Обучение с возвратом

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

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

Обслуживание ограничений

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

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

Ограниченное обучение сохраняет ограничения только в том случае, если несогласованная частичная оценка, которую они представляют, меньше заданного числа ограничений. Обучение, ограниченное релевантностью, отбрасывает ограничения (или вообще не сохраняет их), которые считаются нерелевантными в текущей точке пространства поиска; в частности, он отбрасывает или не сохраняет все ограничения, которые представляют собой противоречивые частичные оценки, которые отличаются от текущей частичной оценки не более чем по заданному фиксированному числу переменных.

См. также

Ссылки

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