Просмотр вперед (возврат)

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

Удовлетворение ограничений

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

Техники заглядывания вперед

В этом примере x ₁ предварительное присвоение x _{2 =1.} =2 и рассматривается

каждая из неназначенных переменных x ₃ и x ₄ ли Прямая проверка только проверяет , соответствует частичному присвоению, удаляя значение 2 из их доменов.

Более простой метод оценки эффекта конкретного присвоения переменной называется опережающей проверкой . ^[1] Учитывая текущее частичное решение и потенциальное присвоение для оценки, он проверяет, может ли другая переменная принимать согласованное значение. Другими словами, сначала оно расширяет текущее частичное решение ориентировочным значением рассматриваемой переменной; затем он рассматривает все остальные переменные $x_{k}$ который все еще не назначен, и проверяет, существует ли оценка $x_{k}$ что согласуется с расширенным частичным решением. В более общем смысле, упреждающая проверка определяет значения для $x_{k}$ которые соответствуют расширенному заданию.

Просмотр согласованности дуги вперед также проверяет, согласуются ли значения x ₃ и x ₄ друг с другом (красные линии), удаляя также значение 1 из их доменов.

Метод прогнозирования, который может занять больше времени, но может дать лучшие результаты, основан на постоянстве дуги . А именно, учитывая частичное решение, расширенное значением для новой переменной, оно обеспечивает согласованность дуг для всех неназначенных переменных. Другими словами, для любых неназначенных переменных удаляются значения, которые невозможно последовательно расширить на другую переменную. Разница между прямой проверкой и согласованностью дуги заключается в том, что первая проверяет на согласованность только одну неназначенную переменную за раз, а вторая также проверяет пары неназначенных переменных на взаимную согласованность. Наиболее распространенным способом использования упреждающего просмотра для решения проблем удовлетворения ограничений является алгоритм поддержания согласованности дуги (MAC) . ^[2]

Два других метода, включающих согласованность дуги, — это полный и частичный просмотр вперед. Они обеспечивают согласованность дуг, но не для каждой пары переменных. В частности, полный просмотр учитывает каждую пару неназначенных переменных. $x_{i},x_{j}$ и обеспечивает согласованность дуг между ними. Это отличается от обеспечения согласованности глобальной дуги, которая может потребовать повторного рассмотрения пары переменных. Вместо этого, как только полный просмотр вперед обеспечивает согласованность дуг между парой переменных, пара больше не учитывается. Частичный просмотр вперед аналогичен, но учитывается заданный порядок переменных, а согласованность дуг обеспечивается только один раз для каждой пары. $x_{i},x_{j}$ с $i<j$ .

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

Использование взгляда вперед

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

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

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

Ниже приведены три метода упорядочивания значений, которые предварительно присваиваются переменной:

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

Эксперименты доказали, что эти методы полезны для решения больших задач, особенно с минимальными конфликтами. ^{[ нужна ссылка ]}

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

Ссылки

^ RM Haralick и GL Elliott (1980), « Повышение эффективности поиска по дереву для задач удовлетворения ограничений ». Искусственный интеллект , 14, стр. 263–313.
^ Сабин, Дэниел и Юджин К. Фрейдер (1994), « Противоречие общепринятой мудрости в удовлетворении ограничений ». Принципы и практика программирования с ограничениями, стр. 10-20.

Дектер, Рина (2003). Обработка ограничений . Морган Кауфманн. ISBN 1-55860-890-7
Оуян, Мин (1998). «Насколько хороши правила ветвления в DPLL?» . Дискретная прикладная математика . 89 (1–3): 281–286. дои : 10.1016/S0166-218X(98)00045-6 .

[1] RM Haralick и GL Elliott (1980), « Повышение эффективности поиска по дереву для задач удовлетворения ограничений ». Искусственный интеллект , 14, стр. 263–313.

[2] Сабин, Дэниел и Юджин К. Фрейдер (1994), « Противоречие общепринятой мудрости в удовлетворении ограничений ». Принципы и практика программирования с ограничениями, стр. 10-20.

[1]

[2]