4.9. КЛЮЧЕВЫЕ ОПЕРАТОРЫ

Во многих задачах поиска в пространстве состояний нетрудно сообразить, как выделить по крайней мере один оператор в пространстве состояний, который будет находиться где-то в решающей цепочке операторов. То есть, хотя задача нахождения всей цепочки операторов в решении достаточно трудна, задача выделения одного из них часто оказывается легкой. С возможностью выделения одного такого оператора мы сталкиваемся тогда, когда по характеру задачи применение одного из операторов рассматривается как необходимый шаг решения задачи. (На графах в пространстве состояний применение такого оператора соответствует проведению дуги, связывающей две практически отдельные части графа.) Например, в рассмотренной задаче о пирамидке оператор «переложить диск С на колышек 3» может быть выделен как оператор, совершенно необходимый при решении задачи (см. рис. 4.2). Мы будем называть операторы такого рода ключевыми операторами.

Когда удается найти ключевой оператор, его можно использовать для определения некоторого основного промежуточного состояния в нашем процессе сведения задачи. Предположим, что некоторый из — ключевой оператор для задачи, задаваемой тройкой Так как мы предполагаем, что оператор должен быть применен, то первой задачей, следующей из будет задача поиска пути к некоторому состоянию, к которому применим. Пусть представляет собой множество состояний, к которым применим Тогда мы имеем подзадачу, описываемую тройкой Как только такая подзадача решена и названо состояние мы можем сформулировать элементарную задачу где — состояние, достигающееся после применения оператора к состоянию Эта задача элементарная, так как она решается просто

путем применения ключевого оператора У нас остается теперь задача, описываемая тройкой

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

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

В большинстве задач нам не удается всегда выделить единственный ключевой оператор, про который заведомо известно, что применение его совершенно необходимо при решении задачи. Вместо этого нам удается лишь указать некоторое подмножество операторов, таких, что один из них с достаточно высокой степенью правдоподобия является таким существенным оператором. Каждый оператор из эого подмножества образует пару результирующих подзадач. Процесс перебора, опирающийся на эту идею, приводил бы к построению графа «И/ИЛИ» при поиске решения среди различных альтернатив.

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