Главная arrow книги arrow Копия Глава 5. Задачи удовлетворения ограничений arrow Распространение информации с помощью ограничений
Распространение информации с помощью ограничений

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

Предварительная проверка

Один из способов лучшего использования ограничений во время поиска получил название предварительной проверки (forward checking). При каждом присваивании значения переменной х в процессе предварительной проверки просматривается каждая переменная y c неприсвоенным значением, которая соединена с х с помощью некоторого ограничения, и из области определения переменной Y удаляется любое значение, которое является несовместимым со значением, выбранным для х. На рис. 5.4 показан ход поиска решения задачи раскрашивания карты с помощью предварительной проверки. На основании данного примера можно сделать два важных вывода. Прежде всего следует отметить, что после присваивания WA=redn Q= green области определения переменных NT и SA сокращаются до единственного значения; таким образом, ветвление, связанное с поиском значений для этих переменных, было полностью устранено путем распространения информации, касающейся переменных WA и Q. Применение эвристики MRV, которая, безусловно, хорошо сочетается с предварительной проверкой, позволяет на следующем этапе автоматически выбрать значение для переменных SA и NT. (Разумеется, что предварительная проверка может рассматриваться как эффективный способ инкре-ментного вычисления той информации, которая требуется эвристике MRV для выполнения своей работы.) Второй вывод, заслуживающий внимания, состоит в том, что после присваивания V=blue область определения SA становится пустой. Поэтому предварительная проверка позволила обнаружить, что частичное присваивание {WA=red, Q=green, V=blue} является несовместимым с ограничениями этой задачи, значит, алгоритм немедленно выполняет возврат.