11.2.1. Основные принципы GPS

Универсальный решатель задач объединяет в себе два основных принципа: анализ целей и средств и рекурсивное решение задач.

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

Задача об обезьяне

В клетке сидит обезьяна. В центре клетки подвешена связка бананов, причем дотянуться до нее нельзя. В углу стоит ящик. Что должна сделать обезьяна, чтобы достать бананы?

Ситуацию можно описать, определив: высоту, на которой находится обезьяна, положение ее в клетке, положение ящика, положение связки бананов и ее высоту. Это характеристики ситуации. Операторы здесь — это то, что может делать обезьяна: ходить, влезать на что-либо, протягивать руку за бананами и толкать ящик. Эти характеристики, соответствующие различия и операторы показаны в таблице операторов и различий (см. табл. 11.1). Наличие компоненты в таблице означает, что данный оператор влияет на данное различие. Фактически табл. -только одна из возможных здесь таблиц операторов и различий. Задание такой таблицы производится вне рамок GPS, поскольку она дается программе как часть определения проблемной среды.

Таблица 11.1. Таблица операторов и различий для задачи об обезьяне

Упрошенная алгебра

Алгебру „плюса и минуса" можно определить следующими правилами:

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

Таблица 11.2

необходимо уметь как находить, так и описывать различия. Например, выражения

сходны на верхнем уровне в том, что оба являются выражениями но различаются своими правыми компонентами. Чтобы обнаружить сходство такого рода, GPS представляет объекты в форме деревьев. Примером могут служить два выражения (1), представленные графами на рис. 11.1. Их изучение показывает, что первое различие из табл. 11.2, т. е. тип использованного арифметического оператора, содержится в выражении, представленном на рис. 11.1 справа.

Рис. 11.1. Деревья для

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

Анализ целей и средств использует различие между объектами для управления процессом решения задачи. Этапы анализа абстрактной задачи „перевести объект А в объект показаны на рис. 11.3. Первый шаг — найти наиболее важное различие между объектами А и В. (Если не найдено никакого различия, считается, что задача решена.) „Наибольшая важность" определяется априорным упорядочением различий, задаваемым программистом. После того как они оценены, для уменьшения различия используется последовательность применяемых операторов. Это

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

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

Необходимо объяснить еще один шаг: как решается подзадача применения к А? Эта задача преобразования аналогична исходной. Напомним, что преобразование по определению есть изменение объекта от формы С к форме С, где С и С — древовидные структуры весьма общего вида, содержащие свободные переменные, которым, следовательно, могут соответствовать многие конкретные деревья. Обратимся к рис. 11.3,6. Сначала А сравнивается с С, чтобы определить, есть ли здесь какие-либо различия в форме. Если нет (т. е. если А — частный случай общей формы С), то применяется непосредственно, образуя Допустим, однако, что найдено различие между С и А. Устанавливается подцель преобразования А к частному случаю А" формы С. Решение этой подзадачи может требовать еще одного этапа уменьшения различий и применения операторов. Если в конце концов выделен применяется для образования Для этих шагов требуется, чтобы GPS была рекурсивной программой, т. е. чтобы она могла обращаться к себе как к подпрограмме. Это соображение приводит нас к обсуждению рекурсивного решения задач и изменению контекста в решаемых подзадачах.

Рис. 11.4 показывает другой путь представления действий GPS, уделяющий большее внимание задаче изменения контекста. Необходимые шаги здесь:

(1) Принять заданную извне цель преобразования Получить различие сравнивая деревья для А и В.

(2) Цель — уменьшить для объекта А. После обращения к таблице операторов и различий в качестве подходящего оператора выбирается

(3) Цель — применить к А. Пусть — оператор с входной формой С. Находится различие между А и С.

(4) Цель G3 - уменьшить D для А. Находится соответствующий оператор

(5) Пусть С — входная форма оператора Допустим, что нет различия между А и С. Применим чтобы получить Теперь нужно выйти из процесса порождения подзадач, решив одну из них.

(6) Различие уменьшается для А путем подстановки вместо А.

(7) Поскольку различие теперь убрано, можно применить к оператор приходя к

(8) Различие уменьшается для А в результате преобразования

(9) Поставлена новая подзадача преобразования . Различие между А" а В либо не существует, либо равно

(10) Если существует, то уменьшить для Процесс продолжается до тех пор, пока не будет найдено решение.

Рис. 11.4. Операция целей и подзадач в GPS.

В некоторых случаях эта стройная схема контекстов внутри контекстов не вполне адекватна. Трудности возникают при появлении „циклов», в которых задача становится подзадачей самой себя. Здесь можно применить хорошие, хотя и довольно скучные программистские приемы. Детали их обсуждаются в работах Куинлана и Ханта (1968), Эрнста и Ньюэлла (1969).