2.2. ОПЕРАТОРЫ

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

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

Для описаний состояний в форме строки имеется очень удобный способ представления операторных вычислений. Он основан на идее правил переписывания (называемых иногда продукциями (productions)).

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

Оно означает, что если символ А появляется в качестве первого символа некоторой строки, то он может быть заменен на символ В. Знак -произвольная подстрока (включая пустую строку). В приведенном правиле переписывания знак указывает, что часть строки (какова бы она ни была), идущая непосредственно за А, не изменяется, когда А заменяется на В.

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

(см. скан)

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

Правило переписывания часто может применяться к некоторой строке несколькими различными способами.

Рис. 2.1. (см. скан) Правила переписывания для игры в восемь.

Так, в приведенном примере правило 4 к строке вообще не может быть применено, тогда как правило 3 может применяться к ней несколькими способами. Конечно, определенному оператору отвечает некоторое конкретное применение данного правила переписывания. Поскольку одно правило переписывания может

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

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

Один из способов представления допустимых ходов в этой игре состоит в задании множества правил переписывания, определенных над массивами. Эти правила определяют пути, по которым массивы могут быть преобразованы в другие массивы того же размера. На рис. 2.1 изображено множество правил переписывания для игры в восемь. Каждое правило представляет собой в действительности два правила (как это показано двунаправленными стрелками), объединенных для экономии места в одно; в каждом случае левая запись может быть заменена правой и обратно. В каждом из правил переписывания допустимый ход определяется путем подстановки чисел на место переменных по каждую сторону от стрелки (при условии Так,

может быть преобразовано в

посредством применения правила 3.