Интеллектуальный поиск с возвратами: поиск в обратном направлении
В алгоритме Backtracking-Search, приведенном в листинге 5.1, применялось очень простое правило, касающееся того, что делать, если какая-то ветвь поиска оканчивается неудачей: вернуться к предыдущей переменной и попытаться использовать для нее другое значение. Такой метод называется хронологическим поиском с возвратами, поскольку повторно посещается пункт, в котором было принято последнее по времени решение. В данном подразделе будет показано, что существуют намного лучшие способы поиска с возвратами.
Рассмотрим, что произойдет в случае применения простого поиска с возвратами в задаче, показанной на рис. 5.1, с постоянным упорядочением переменных Q, NSW, V, Т, SA, WA, NT. Предположим, что сформировано частичное присваивание {Q= red,NSW= green, V=blue, T=red}. А после попытки присвоить значение следующей переменной, SA, будет обнаружено, что любое значение нарушает какое-то ограничение. Алгоритм возвращается к узлу т и пытается назначить новый цвет для Тасмании! Очевидно, что это — бессмысленное действие, поскольку смена цвета Тасмании не позволяет решить проблему с Южной Австралией.
Более интеллектуальный подход к поиску с возвратами состоит в том, чтобы вернуться к одному из множеств переменных, которые стали причиной неудачи. Это множество называется конфликтным множеством; в данном случае конфликтным множеством для SA является {Q,NSW, V}. Вообще говоря, конфликтное множество для переменной х представляет собой множество переменных с ранее присвоенными значениями, которые связаны с X ограничениями. Метод обратного перехода выполняет обратный переход к переменной с последним по времени присвоенным значением из конфликтного множества; в данном случае в обратном переходе следует перескочить через узел Тасмании и попытаться применить новое значение для V. Такая операция может быть легко реализована путем модификации алгоритма Backtracking-Search таким образом, чтобы он накапливал данные о конфликтном множестве, одновременно проверяя одно из значений, допустимых для присваивания. Если не будет найдено ни одного допустимого значения, алгоритм должен возвратиться к последнему по времени элементу конфликтного множества и наряду с этим установить индикатор неудачи.
Внимательный читатель уже должен был заметить, что предварительная проверка позволяет определить конфликтное множество без дополнительной работы, поскольку каждый раз, когда процедура предварительной проверки, основанная на присваивании значения переменной X, удаляет некоторое значение из области определения Y, она должна добавить X к конфликтному множеству Y. Кроме того, каждый раз, когда это последнее значение удаляется из области определения у, переменные из конфликтного множества Y добавляются к конфликтному множеству X. В этом случае после перехода к Y можно сразу же установить, куда должен быть выполнен обратный переход в случае необходимости.
А проницательный читатель уже должен был заметить нечто странное: обратный переход происходит, когда каждое значение в некоторой области определения конфликтует с текущим присваиванием, но предварительная проверка обнаруживает этот случай и вообще исключает возможность достижения такого узла! В действительности можно показать, что каждая ветвь, отсекаемая с помощью обратного перехода, отсекается также с помощью предварительной проверки. Поэтому простой поиск с обратным переходом в сочетании с поиском с предварительной проверкой становится избыточным, а фактически обратный переход избыточен в любом поиске, в котором используется более строгая проверка совместимости, такая как MAC.
Несмотря на замечания, сделанные в предыдущем абзаце, идея, лежащая в основе обратного перехода, остается перспективной, если возврат осуществляется с учетом причин неудачи. При обратном переходе неудача обнаруживается после того, как область определения некоторой переменной становится пустой, но во многих случаях какая-то ветвь поиска становится бесперспективной задолго до того, как это происходит. Еще раз рассмотрим частичное присваивание {WA=red, NSW=red} (которое согласно приведенному выше описанию является несовместимым). Предположим, что на следующем этапе предпринимается попытка присваивания T=red, а затем осуществляется присваивание значений переменным NT, Q, V, SA. Известно, что ни одно присваивание не применимо для этих последних четырех переменных, поэтому в конечном итоге не остается доступных значений, которые можно было бы попытаться присвоить переменной NT. Теперь возникает вопрос, куда выполнить возврат? Обратный переход не может применяться, поскольку в области определения переменной NT имеются значения, совместимые со значениями, ранее присвоенными переменным, — переменная NT не имеет полного конфликтного множества из переменных с ранее присвоенными значениями, которое вызвало бы неудачу при попытке присваивания ей значения. Однако известно, что неудачу вызывают четыре переменные, NT, Q, Vn SA, вместе взятые, поскольку во множестве переменных с ранее присвоенными значениями должны существовать такие переменные, которые непосредственно конфликтуют с этими четырьмя. Эти рассуждения приводят к созданию более глубокого определения понятия конфликтного множества для такой переменной, как NT. конфликтным множеством называется множество переменных с ранее присвоенными значениями, которые, наряду со всеми переменными со значениями, присваиваемыми в дальнейшем, становятся причиной того, что для NT не существует совместимого решения. В таком случае конфликтное множество состоит из переменных ш и NSW, поэтому алгоритм должен выполнить возврат к NSW и пропустить переменную, соответствующую Тасмании. Алгоритм обратного перехода, в котором используются конфликтные множества, определенный таким образом, называется алгоритмом обратного перехода, управляемого конфликтами (conflict-directed backjumping).
Теперь необходимо объяснить, как вычисляются эти новые конфликтные множества. Применяемый для этого метод фактически очень прост. "Окончательная" неудача в какой-то ветви поиска всегда возникает из-за того, что область определения некоторой переменной становится пустой; эта переменная имеет типичноеконфликтное множество. В данном примере неудача возникает при присваивании значения переменной SA, а ее конфликтным множеством является (скажем) {WA, NT, Q). Выполняется обратный переход к переменной Q, и эта переменная поглощает конфликтное множество, полученное от SA (безусловно, после исключения из него самой переменной Q), объединяя его со своим собственным прямым конфликтным множеством, представляющим собой {NT,NSW}', новым конфликтным множеством становится {WA,NT,NSW}. Это означает, что, продолжая поиск от Q, нельзя найти решение при наличии ранее выполненного присваивания переменным {WA, NT, NSW). Поэтому обратный переход выполняется к переменной NT, присваивание значения которой выполнено последним по времени по сравнению с другими этими переменными. Переменная NT поглощает множество {WA,NT,NSW}-{NT}, объединяя его со своим собственным прямым конфликтным множеством {WA), что приводит к получению {WA, NSW} (как было указано в предыдущем абзаце). Теперь алгоритм осуществляет обратный переход к NSW, как и предполагалось. Подведем итог: допустим, что xd — текущая переменная, a confix) — ее конфликтное множество. Если все попытки присваивания каждого возможного значения переменной Xj оканчиваются неудачей, то необходимо выполнить возврат к переменной xL с последним по времени присвоенным значением во множестве confix) и установить:
conf{Xi) <- conf(Xi) U conf(Xj) - {Xi)
Обратный переход, управляемый конфликтами, позволяет вернуться в правильную точку дерева поиска, но не предотвращает возможности возникновения таких же ошибок в другой ветви того же дерева. Метод определения ограничений с помощью обучения (constraint learning) по сути представляет собой метод модификации задачи CSP путем добавления нового ограничения, выдвинутого на основе логического анализа этих конфликтов.