Взгляд вперед (возврат)

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

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

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

Методы прогнозирования

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

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

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

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

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

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

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

Использование функции «смотреть вперед»

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

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

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

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

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

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

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

Ссылки

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

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