2.14 Функция eval

Функция EVAL вызывает интерпретатор языка Лисп.

((SETQ U '(A B C))(CONS (CAR U)(CADR U))

Здесь 7 раз неявно обращаются к функции EVAL (1-SETQ, 2-QUOTE,3-CONS,4-CAR,5-CADR, 6,7-const U в CAR и CADR).

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

‘(1 2 3) (1 2 3)

(Eval ‘(car ‘(1 2 3))) 1

Если выражение Х имеет значение, то это значение совпадает со значением выражения (EVAL (QUOTE X)).

3 Представление задач и поиск решений

Рассмотрим общие стратегии поиска решений , применимые к любым задачам. Обычно при решении любой задачи легко выделить два этапа: выбор способа представления задачи; собственно решение.

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

Будем рассматривать такие представления задач, которые удобны с точки зрения решателя задач (ЭВМ). С этой точки зрения выделяют следующие виды представления задач:

- представление задач в пространстве состояний;

- сведение задачи к подзадачам;

- представление задач в виде доказательства теорем.

3.1 Представление задач в пространстве состояний

Подход, использующий пространство состояний, предполагает, что в процессе решения задача переходит из своего начального состояния S_o в конечное решенное S_g через некоторые промежуточные состояния S_i с помощью операторов, входящих в множество О.

Процесс решения задачи сводится к выбору подходящего оператора из множества О и применению его к текущему состоянию задачи до тех пор, пока не будет достигнуто конечное состояние .

S_g=(O_i...(O₂(O₁(S_o))...)

Существует аналогия между таким представлением задачи и графами. Т.е. задачи, представленные в виде пространства состояний, можно отобразить в виде графа, у которого узлы - состояния, а дуги -операторы, переводящие задачу из состояния S_i в состояние S_j. В этом случае процесс поиска решения сводится к нахождению пути на графе от S_o к S_g. Если мы найдем этот путь, то мы найдем, соответственно, все операторы и решения. Этап поиска пути называется планированием решения задачи.

3.2 Сведение задачи к подзадачам

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

Этот метод также можно представить в виде графа. Граф имеет некоторые особенности:

• при представлении задач в виде пространства состояний все дуги связаны отношением "или";

• при сведении задач к подзадачам есть дуги как "и", так и "или". Соответственно, отличается и поиск.

3.3Представление задач в виде доказательства теорем

Сначала формулируются некоторые априорно-истинные утверждения- аксиомы. Затем формулируется целевое утверждение, которое необходимо доказать. Комбинируя попарно аксиомы и целевое утверждение, проводят доказательство. Такой алгоритм придуман в 1965 году и называется принципом резолюций.