9.1. Типы представлений

9.1.0. Перечисление

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

(i) Положить и начать с некоторого множества пробных решений .

(ii) Если содержит требуемое решение, то работа алгоритма оканчивается. В противном случае перейти к

(iii) Построить увеличить к на единицу и перейти к

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

9.1.1. Решение задач в пространстве состояний

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

что

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

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

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

В методе сведения задачи к подзадачам определяется совокупность подзадач, которые, если бы решились раздельно, привели бы к решению исходной задачи. Затем рассматривается каждая подзадача, и результаты объединяются для нахождения решения всей задачи. Этот процесс можно применять рекурсивно для порождения подзадач, подподзадач и т. д. до тех пор, пока, наконец, не получится множество тривиальных „задач“, решения которых известны. Решения этих задач можно объединить в решение более сложной задачи. В качестве интересной иллюстрации рассматриваемого метода Нильсон (1971) предлагает задачу „Ханойская башня“. Даны три колышка и три различных диска. Сначала все диски находятся на левом колышке, требуется переместить их все на правый (рис. 9.3). При этом каждый раз должен перемещаться только один диск, и

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

больший диск никогда не должен находиться над меньшим. Чтобы решить задачу, больший диск надо поместить на колышек 3. Разумеется, диск С должен быть на колышке 1, а колышек 3 должен быть пустым, т. е. имеется в виду ситуация, когда на колышке 2 находятся диски А и В в нужном порядке. Таким образом, задача разбивается на две подзадачи (рис. 9.4 и 9.5). Заметим, что последняя тривиальна и решается единственным ходом. Однако после того, как они решены, остается дополнительная задача переместить на нужное место диски А и В (рис. 9.6). Читатель может легко применить предыдущее рассуждение для выделения дальнейших подзадач и, таким образом, получить решение.

Рис. 9.7. ИЛИ-подзадачи для задачи „Ханойская башня".

Подзадачи, которые мы до сих пор обсуждали, называются И-подзадачами, так как для решения основной задачи они должны быть решены все. Часто возникают случаи ИЛИ-подзадач, т. е. таких задач, что если решена какая-нибудь одна из них, то решена и основная задача. Это происходит и в задаче „Ханойская башня“. На рис. 9.7 показаны такие две конфигурации дисков, что если достигнута любая из них, то основная задача решается тривиально.

Задачу сведения к подзадачам можно изобразить в виде специального графа, называемого деревом (рис. 9.8). Обращаем внимание читателя на дугу, связывающую подзадачи 1 и 2. Она указывает, что для решения основной задачи должны быть решены обе подзадачи, поэтому 1 и 2 являются И-подзадачами. Такой дуги на рисунке нет в случае ИЛИ-подзадач, какими являются подподзада-чи 3, 4, 5 и 6.

Поиском решения при сведении задачи к подзадачам называется процесс, в котором каждый узел помечается как решенная задача и который продолжается до тех пор, пока не будет помечен корень. Процесс решения начинается с корня, который представляет исходную задачу. Затем порождаются ее подзадачи, и соответствующие узлы соединяются с корнем как его И- или ИЛИ-преемники. После этого порождаются подзадачи подзадач до тех пор, пока не получится подзадача, которую можно непосредственно решить (т. е. для нее программа решения „знает ответ. Соответствующий узел помечается как решенный, и дерево просматривается вновь.

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

9.1.3. Переписывание цепочек

В представлении, использующем переписывание цепочек, возможные „состояния мира“, включая начальные и целевые, рассматриваются как правильно построенные выражения некоторого языка.

Рис. 9.8. Представление метода сведения задачи к подзадачам в виде дерева.

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

Доказательство таково:

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