WikiDer > Ограниченное обучение

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

Определение

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

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

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

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

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

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

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

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

Графическое обучение

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

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

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

Обратное обучение

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

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

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

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

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

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

Смотрите также

• Прогнозирование (возврат)
• Обратный прыжок

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

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