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

Составные элементы представления в пространстве состояний

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

Основные элементы языка теории графов (дуги, вершины, пути и т. п.) часто используются при описании процессов решения задач. Классическими книгами по теории графов являются книги Бержа (1958) и Оре (1962). Оре (1963) написал также популярную элементарную книжку, содержащую применения теории графов к различным комбинаторным задачам.

Недетерминированные программы

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

Основная литература по примерам задач

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

специализированных методов на обычный язык представления в пространстве состояний.

Задача о коммивояжере занимает важное место в теории исследования операций. Обзор результатов по ней можно найти у Беллмора и Немхозера (1968).

Задачи синтаксического анализа обычны при исследовании языков. Фельдман и Грис (1968) дают всесторонний обзор методов синтаксического анализа, используемых трансляционными системами для формальных вычислительных языков. Амарель (1965) обсуждает синтаксический анализ с позиции автоматического решения задач и предлагает процедуру, основанную на сведении задачи к подзадачам. Доступное изложение вопроса об использовании строк и символов и их продукционных систем как вычислительных моделей имеется в заключительных главах книги Минского (1967) по вычислениям.

Множество задач, таких, как распределение, потоки и очереди, может быть решено методом, связанным с пространством состояний. Они рассмотрены в книге Форда и Фалкерсона (1962).

Теория управления — это большая специальная область с разнообразными приемами решения возникающих здесь задач. Книга Де Руссо, Роя и Клоуза (1965) может служить хорошим введением в современную теорию управления.

Проблема поиска хорошего представления

Вопросы поиска хорошего представления рассматривали лишь немногие исследователи и, в частности, Амарель. Амарелем (1968) написана классическая работа на эту тему. В ней он последовательно показывает читателю ряд постепенно улучшающихся представлений для задачи о миссионерах и людоедах. Интересная головоломка, подчеркивающая важность выбора хорошего представления, была отмечена Маккарти (1964). Задача об обезьяне и бананах — стандартный пример задачи о построении рассуждений на основе здравого смысла. Она детально рассмотрена Амарелем (1966).

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

Задачи

(см. скан)

(см. скан)

(см. скан)