Упорядочение переменных и значений
Приведенный выше алгоритм поиска с возвратами содержит следующую строку:
var <— Select-Unassigned-Variable(Variables[csp] , assignment, csp)
По умолчанию функция Select-Unassigned-Variable выбирает следующую переменную с неприсвоенным значением в порядке, указанном в списке Variables [csp]. Такое статическое упорядочение переменных редко приводит к наиболее эффективному поиску. Например, после присваиваний WA=red и NT= green остается только одно возможное значение для SA, поэтому имеет смысл на следующем этапе выполнить присваивание SA=blue, а не присваивать значение переменной Q. В действительности после присваивания значения переменной SA все варианты выбора значений для Q, NSW и V становятся вынужденными. Эта интуитивная идея (согласно которой в первую очередь следует выбирать переменную с наименьшим количеством "допустимых" значений) называется эвристикой с минимальным количеством оставшихся значений (Minimum Remaining Values — MRV). Эту эвристику называют также эвристикой с "переменной, на которую распространяется наибольшее количество ограниченной", или эвристикой "до первого неудачного завершения"; последнее название применяется потому, что такая эвристическая функция предусматривает выбор переменной, которая с наибольшей вероятностью вскоре приведет к неудаче, усекая тем самым дерево поиска. Если существует переменная хс нулевым количеством оставшихся допустимых значений, эвристическая функция MRV выберет X и неудача будет обнаружена немедленно; это позволяет избежать бессмысленных поисков среди других переменных, которые всегда будут оканчиваться неудачей после того, как в конечном итоге будет выбрана переменная х. Производительность поиска с использованием этой эвристической функции показана во втором столбце табл. 5.1, обозначенном как Поиск с возвратами на основе MRV. Производительность поиска повышается от 3 до 3000 раз по сравнению с простым поиском с возвратами, в зависимости от задачи. Следует отметить, что в применяемом здесь показателе производительности не учитывается дополнительная стоимость вычисления значений эвристической функции; в следующем подразделе описан метод, который позволяет удерживать это значение стоимости в приемлемых рамках.
Эта эвристическая функция MRV вообще не оказывает никакой помощи при выборе для окрашивания в Австралии первого региона, поскольку первоначально каждый регион имеет три допустимых цвета. В таком случае удобной становится степенняя эвристика. В этой эвристике предпринимается попытка уменьшить коэффициент ветвления в будущих вариантах за счет выбора переменной, которая участвует в наибольшем количестве ограничений на другие переменные с неприсвоенными значениями. На рис. 5.1 переменной с наибольшей степенью, 5, является переменная &А; другие переменные имеют степень 2 или 3, за исключением Т, которая имеет степень 0. В действительности после выбора переменной SA применение степенной эвристики позволяет решить задачу без каких-либо неудачных этапов — теперь можно выбрать любой согласованный цвет в каждой точке выбора и все равно прийти к решению без поиска с возвратами. Эвристика с минимальным количеством оставшихся значений обычно обеспечивает более мощное руководство, но степенная эвристика может оказаться полезной в качестве средства разрешения неопределенных ситуаций.
После выбора одной из переменных в этом алгоритме необходимо принять решение о том, в каком порядке должны проверяться ее значения. Для этого в некоторых случаях может оказаться эффективной эвристика с наименее ограничительным значением. В ней предпочитается значение, в котором из рассмотрения исключается наименьшее количество вариантов выбора значений для соседних переменных в графе ограничений. Например, предположим, что на рис. 5.1 сформировано частичное присваивание с WA=red и NT-green и что следующий вариант выбора предназначен для Q. Синий цвет был бы плохим вариантом, поскольку исключил бы последнее допустимое значение, оставшееся для соседней переменной относительно О, т.е. переменной SA. Поэтому эвристика с "наименее ограничительным значением" предпочитает значение red, а не blue. Вообще говоря, в этой эвристике предпринимается попытка сохранить максимальную гибкость для последующих присваиваний значений переменным. Безусловно, если бы мы стремились найти все решения некоторой задачи, а не первое из них, то такое упорядочение не имело бы значения, поскольку нам так или иначе пришлось бы рассмотреть каждое значение. Такое же замечание остается справедливым, если данная задача вообще не имеет решений.