4.10. РАЗЛИЧИЯ

Один из способов нахождения операторов, которые предположительно могут быть ключевыми, состоит в вычислении различия для данной задачи Попросту говоря, различие для тройки это есть частичный список причин, по которым элементы множества не удовлетворяют тем условиям, которым должны удовлетворять целевые состояния (множество (Если некоторый элемент множества находится в то

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

Далее, каждому возможному различию мы ставим в соответствие некоторый оператор (или множество операторов) в пространстве состояний. Это и есть операторы, которые могут быть ключевыми. Некоторый оператор ставится в соответствие различию только в том случае, когда его применение может устранить это различие. Проиллюстрируем работу этого процесса применительно к задаче об обезьяне и бананах.

Эта задача обсуждалась нами в гл. 2 в связи с использованием схем описаний состояний. Напомним, что эти схемы имели форму , где — положение обезьяны в горизонтальной плоскости (двумерный вектор); х равен 1 или 0 в зависимости от того, находится обезьяна на ящике или нет соответственно; у — положение ящика в горизонтальной плоскости (двумерный вектор); равен 1 или 0 в зависимости от того, получает обезьяна бананы или нет соответственно.

Имеются четыре оператора, действия и условия применимости которых даются следующими правилами переписывания:

где с — точка пола, расположенная прямо под бананами.

Условие выполнения поставленной цели выполняется для описаний состояний лишь в том случае, когда последний элемент в этой схеме описания состояния равен 1. Начальное состояние дается списком

Если — множество из четырех операторов, множество целевых состояний, то наша исходная задача принимает вид

Так как в этой задаче множество операторов остается неизменным, то символ можно опустить и обозначить всю задачу просто как

Теперь процедура сведения задачи к совокупности подзадач с использованием понятия ключевых операторов может быть описана следующим образом:

Прежде всего вычисляем различие для исходной задачи. Для списка мы получаем, что он не удовлетворяет поставленной цели, так как последний элемент в нем не равен 1. Ключевой оператор (ответственный за уменьшение этого различия — это оператор «схватить».

(Мы предполагаем, что связи между возможными различиями и их ключевыми операторами заданы решателю задач с самого начала.)

Используя оператор для сведения иервоначальной задачи, мы приходим к следующей паре подзадач:

где — множество описаний состояний, к которым применим оператор (описания состояний из области определения оператора — состояние в получаемое в результате решения подзадачи.

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

Сначала вычислим различие. Состояние, описываемое четверкой , не входит в по той причине, что

Если теперь этот список утверждений взять в качестве различия, то мы выделяем следующие ключевые операторы:

Далее мы по очереди применяем каждый из этих ключевых операторов, с тем чтобы построить альтернативные пары результирующих задач. Первый из ключевых операторов используется для сведения задачи к такой паре задач:

где получается в результате решения задачи 1.1.

Так как сначала необходимо решить задачу 1.1, то мы вычисляем, ее различие.

(кликните для просмотра скана)

Это различие дает нам ключевой оператор

Затем этот ключевой оператор используется для разбиения задачи на две:

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

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

На рис. 4.14 изображен граф типа «И/ИЛИ», дающий дерева решения для этой задачи. Числа около вершин гра-фа показывают порядок, в котором исследовались различные задачи в ходе описанного процесса перебора. Оказалось, что рассмотренный нами порядок привел к решению еще до того, как были подвергнуты изучению незанумерованные задачи, но в общем случае мог потребоваться дополнительный перебор. Анализируя граф решения на рис. 4.14, нетрудно построить последовательность операторов, решающую исходную задачу:

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