WikiDer > Прогнозирование (возврат)

Look-ahead (backtracking)

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

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

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

Смотрите вперед техники

В этом примере Икс1= 2 и предварительное присвоение Икс2= 1 считается.
Прямая проверка только проверяет, каждая ли из неназначенных переменных Икс3 и Икс4 является последовательный с частичным присвоением, удалив значение 2 из своих доменов.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

  1. ^ Р.М. Харалик и Г.Л. Эллиот (1980) "Повышение эффективности поиска по дереву для задач удовлетворения ограничений". Искусственный интеллект, 14, С. 263–313.
  2. ^ Сабин, Дэниел и Юджин К. Фрейдер (1994), «Противоречие общепринятому мнению в удовлетворении ограничений.” Принципы и практика программирования с ограничениями, С. 10-20.
  • Дехтер, Рина (2003). Обработка ограничений. Морган Кауфманн. ISBN 1-55860-890-7
  • Оуян, Мин (1998). «Насколько хороши правила ветвления в DPLL?». Дискретная прикладная математика. 89 (1–3): 281–286. Дои:10.1016 / S0166-218X (98) 00045-6.