Что такое наименьшая сдерживающая ценность?

В проблемах удовлетворения ограничений эвристика может использоваться для повышения производительности решателя бактрекинга. Три обычно используемых эвристики для простых решателей обратного отслеживания:

• Минимальные оставшиеся значения (сколько значений все еще допустимо для этой переменной)
• Степень эвристики (сколько других переменных зависит от этой переменной)
• Наименьшее ограничивающее значение (какое значение оставит большинство других значений для других переменных)

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

Это просто, четко определено и легко реализуемо.

Наименьшая ограничивающая ценность четко не определена, где бы я ни смотрел. Искусственный интеллект: современный подход (Russel & Norvig) просто говорит:

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

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

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

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

Может ли кто-нибудь дать более полезное описание наименьшего ограничивающего значения и объяснить, как эта версия наименьшего ограничивающего значения действительно приведет к улучшению?

см эту ссылку:

https://people.cs.pitt.edu/~wiebe/courses/CS2710/lectures/constraintSat.example.txt

Сначала он выбирает переменную «O», а затем проверяет «O» со всеми допустимыми значениями «i», чтобы увидеть число сокращений соседей «O» «N». Это добавляет все из них. и выбирает «я», которое вызывает меньше сокращений:

   sums = {0:0,1:0,2:0,3:0,4:0,5:0,6:0,7:0,8:0,9:0}
   For i from 0 to 9:  
     plug "o=i" into the constraint formulas
     For each neighbor "N" of "o" in the constraint graph:
       sums[i] += the number of values remaining for "N"

Он выбирает «я» так, чтобы:

sums[i] = MAX{sums[i] | for all "i" that is a member of "O",s valid values}

Я надеюсь, что это может помочь вам найти свой ответ!

Я думаю, что здесь главное, чтобы эти эвристики применялись в зависимости от задачи, для которой написан решатель. И если существует вероятность того, что если выбранное значение переменной не оставит ни одного значения в области другой переменной (скажем, у нас есть сильно ограниченная задача только с одним решением), то решение будет остановлено. , И случайный поиск может идти по правильному пути, ведущему к решению и неправильному. И если что-то пойдет не так, вам придется вернуться назад (см. Конфликт, направленный назад), и это займет время вычислений. Но алгоритм, использующий эвристику LCV, скорее всего пойдет по более правильному пути, и никаких возвратов не требуется. Но если проблема будет недостаточно сложной, я думаю, что это будет очень похоже на случайный поиск.