Главная arrow книги arrow Копия Глава 5. Задачи удовлетворения ограничений arrow Интеллектуальный поиск с возвратами: поиск в обратном направлении
Интеллектуальный поиск с возвратами: поиск в обратном направлении

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

Несмотря на замечания, сделанные в предыдущем абзаце, идея, лежащая в основе обратного перехода, остается перспективной, если возврат осуществляется с учетом причин неудачи. При обратном переходе неудача обнаруживается после того, как область определения некоторой переменной становится пустой, но во многих случаях какая-то ветвь поиска становится бесперспективной задолго до того, как это происходит. Еще раз рассмотрим частичное присваивание {WA=red,NSW=red} (которое согласно приведенному выше описанию является несовместимым). Предположим, что на следующем этапе предпринимается попытка присваивания T=red, а затем осуществляется присваивание значений переменным NT, Q, V, SA. Известно, что ни одно присваивание не применимо для этих последних четырех переменных, поэтому в конечном итоге не остается доступных значений, которые можно было бы попытаться присвоить переменной NT. Теперь возникает вопрос, куда выполнить возврат? Обратный переход не может применяться, поскольку в области определения переменной NT имеются значения, совместимые со значениями, ранее присвоенными переменным, — переменная NT не имеет полного конфликтного множества из переменных с ранее присвоенными значениями, которое вызвало бы неудачу при попытке присваивания ей значения. Однако известно, что неудачу вызывают четыре переменные, NT, Q, V и SА, вместе взятые, поскольку во множестве переменных с ранее присвоенными значениями должны существовать такие переменные, которые непосредственно конфликтуют с этими четырьмя. Эти рассуждения приводят к созданию более глубокого определения понятия конфликтного множества для такой переменной, как NT. конфликтным множеством называется множество переменных с ранее присвоенными значениями, которые, наряду со всеми переменными со значениями, присваиваемыми в дальнейшем, становятся причиной того, что для NT не существует совместимого решения. В таком случае конфликтное множество состоит из переменных WA и NSW, поэтому алгоритм должен выполнить возврат к NSW и пропустить переменную, соответствующую Тасмании. Алгоритм обратного перехода, в котором используются конфликтные множества, определенный таким образом, называется алгоритмом обратного перехода, управляемого конфликтами (conflict-directed backjumping).