4.13. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ

Методы сведёния задачи к подзадачам и «И/ИЛИ» графы

В некоторых из самых первых работ по искусственному интеллекту для решения задач использовались методы сведёния задачи к совокупности подзадач (называемые также «рассуждением в обратном направлении»). Ньюэлл, Шоу и Саймон (1957) написали программу для логико-теоретической машины (ЛТ), которая доказывала теоремы исчисления предикатов, строя свою работу на рассуждении в обратном направлении от доказываемой теоремы. В этой программе было использовано дерево подзадач, для того чтобы можно было просмотреть альтернативные цепочки рассуждений.

Другой из первых программ, в которой были применены методы сведёния задачи и деревья подзадач, была программа для символьного интегрирования (SAINT) Слейджла (1963а). Слейджл первым назвал эти деревья деревьями типа «И/ИЛИ». В более поздней работе Слейджла и Бурского (1968) был использован термин «пропозициональное дерево». Ригни и Таун (1969) предложили применить граф типа графов «И/ИЛИ» для анализа структуры последовательностей операций в промышленности. Некоторые примеры представлений неявно заданных деревьев типа «И/ИЛИ» с помощью недетерминированных программ были даны Манна (1970).

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

Наш пример символического интегрирования основан на программе Слейджла (1963а). Подробно эта программа описана в диссертации Слейджла (1961). Много более развитая система интегрирования (названная SIN) была впоследствии запрограммирован Мозесом (1967). Она содержала так много специальных критериев применимости различных операторов, что интегрирование по большей части производилось либо вовсе без перебора, либо после очень незначительного перебора. Риш (1969) разработал алгоритмические процедуры для интегрирования выражений различных типов (см. задачу 4.5).

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

Понятия ключевых операторов и различий и их применение при решении задач связаны главным образом с именем Ньюэлла и его сотрудников по универсальному решателю задач GPS (см. Эрнст и Ньюэлл, 1969). Можно было бы здесь упомянуть, что наше объяснение этих идей несколько отличается от того, что можно найти у Ньюэлла и др. Ньюэлл употреблял фразу «анализ цели-средства», когда говорил о процессе поиска различий и устранения этих различий с помощью подходящих операторов. Он различал также три типа целей в программе GPS: преобразование объекта, уменьшение различия и применение оператора. Из нашего описания не видна полезность такой классификации. Нас интересует программа GPS постольку, поскольку она может быть использована в системе автоматического решения задач, а многих работавших над GPS она интересовала также и как психологическая модель мыслительного процесса. Это различие в точках зрения, без сомнения, отразилось в какой-то мере и на способах описания программы.

Особо интересуясь возможностями программы GPS для решения задач, Эрнст (1969) исследовал те условия, при которых GPS гарантирует нахождение решения. Анализ Эрнста привел к формализации понятий различия и упорядочения различий.

Игры и подход, связанный с разбиением задачи на подзадачи

Слейджл и его сотрудники подчеркнули существенную аналогию между «И/ИЛИ» деревьями и игровыми деревьями

(Слейджл, 1970, Слейджл и Бурский, 1968). Эта аналогия в какой-то мере очевидна в простых играх, которые могут быть рассмотрены до конца, или в окончаниях более сложных игр, таких, как шахматы. Действительно, мы часто думаем о шахматных эндшпилях как о задачах на доказательство, а не как об играх. Наш пример игры Гранди взят из статьи О’Бирна (1961).

Задачи

(см. скан)

(см. скан)