9.2. Комбинирование представлений

Метод сведения задачи к подзадачам приводит к хорошим результатам потому, что часто решение задач имеет иерархическую структуру. Однако в самом сведении задачи к подзадачам скрывается важный момент. Не обязательно основная задача и все ее подзадачи решаются с помощью одинаковых представлений. Если на этом уровне допустимы какие-то обобщения, то можно сказать, что метод сведения задачи к подзадачам полезен для представления глобальных аспектов задачи, а при решении более специфических задач предпочтительнее методы, использующие пространство состояний, переписывание цепочек и перечисление. Лучше всего это можно понять, если рассмотреть проблемы, относящиеся к широкой области, пока еще не затронутой вычислительными машинами. Например, „проблема», упомянутая Джоном Кеннеди в его речи на торжестве по случаю избрания его на пост президента. Как восстановить международный престиж США? Он считал, что эта проблема состоит из ряда подпроблем, таких, как более активная программа гражданских свобод, повышение эффективности вооруженных сил, обширная программа исследования космоса. Последняя содержала в качестве подпрограммы посылку человека на Луну. Пока еще мы находимся в рамках сведения задачи к подзадачам. Далее исследование Луны требовало конструирования специальных космических кораблей. Наилучший способ представления и решения этоп задачи — построить соответствующий граф и найти на нем оптимальный путь. Конструирование космического корабля в свою очередь потребовало решения ряда инженерных и математических задач, для которых понадобилось либо перечисление, либо переписывание цепочек.

Смешанные представления встречаются не только при решении задач, с которыми сталкиваются политические деятели национального или международного масштаба. В настоящее время наиболее известный проект в области искусственного интеллекта — это „робот Шейки», представляющий собой управляемый от ЭВМ

перемещающийся объект, построенный в Станфордском исследовательском институте (США). Шейки наделен способностью определить путь, по которому он достигает цели, и свои действия, необходимые для того, чтобы определенным образом изменить окружающий его мир. Программная система Шейки использует смешанное представление (Мансон, 1971). Когда Шейки получает задание изменить окружающий мир, основная задача разбивается на подзадачи. Последовательность просмотра подзадач определяется с помощью графового представления (или представления в пространстве состояний). К отдельным шагам этой последовательности применяют методы доказательства теорем, чтобы показать, что определенная операция даст желаемый результат. Этими методами служат методы перечисления, аналогичные излагаемым в гл. 12. Они фактически предназначены для нахождения эквивалентных алгебраических выражений. Вместе с тем серьезно обсуждалась возможность представления данной задачи в форме переписывания цепочек. Таким образом, этот проект служит хорошим примером того, как смешиваются представления, когда решается совсем сложная проблема (и также иллюстрирует тот факт, что сложное по машинным стандартам может оказаться очень простым для людей). Несмотря на сенсационные сообщения в прессе, наиболее ревностные почитатели Шейки легко соглашались, что сами действия робота не выглядят впечатляющими. Во время многочисленных публичных демонстраций (например, организованная Нильсоном и Фельдманом на одном из совещаний АВТ, 1972) указывалось, что основная причина увлечения роботами в 70-х годах состоит в желании узнать, как строить сложные системы решения задач, используя различные представления, а не как строить устройства, которые будут полезными сами по себе.

Когда для решения очень сложных задач применяются вычислительные методы, „типичная" ошибка, которую совершает программа, заключается в том, что она порождает так много пробных решений, что, несмотря на значительное быстродействие ЭВМ, не хватает времени проверить каждое из них. Поэтому правильное решение можно и не найти, поскольку задача обработки данных становится слишком громоздкой. С другой стороны, для людей, очевидно, типична неспособность построить правильное решение вообще. Это предполагает наличие у людей некоторого способа, позволяющего ограничить (возможно, чересчур сильно) свое пространство поиска пространством допустимых решений. В частности, Пойа (1954, 1957) предположил, что этот способ состоит в использовании планов и аналогий. Чтобы перенести обсуждение из психологии в вычислительные науки, определим план как решение более

ограниченной задачи, содержащей лишь некоторые основные характеристики исходной. При решении задачи в представлении на основе планов вырабатывается совокупность подзадач, которые, как ожидается, можно будет легко решить одну за другой. Можно было бы продемонстрировать эту идею на примере из вычислительной области, однако этот принцип так же хорошо, но проще иллюстрируется задачей о „путешествующем профессоре». Предположим, что профессор из Сиэтла, штат Вашингтон, желает посетить коллегу из Калифорнийского университета в Санта-Барбара, Южная Калифорния. В конечном счете эту задачу можно решить последовательностью действий, включающих поездки на такси, лимузине, воздушные перелеты и даже немного ходьбу. Такое путешествие сначала будет планироваться на уровне аэропортов, в предположении, что локальные транспортные проблемы будут как-то решаться по мере возникновения.

В то время, как планирование естественно соответствует машинно-ориентированному понятию об иерархических отношениях между задачами и подзадачами, формальное описание аналогий кажется намного труднее. В аналогиях легче всего разобраться, если обратиться к представлению, основанному на сведении задачи к подзадачам. Предположим, что на некотором этапе выделено множество ИЛИ-подзадач. Идеально решатель задач должен выбрать самую легкую и попробовать ее решить. Если какая-то задача из этого множества неразрешима, то ясно, что и не стоит ее решать, — это пустая трата времени. Но откуда решатель задач знает, пока не попробует решить, что задачу легко, трудно или невозможно решить? Чтобы выйти из этого логического круга, предположим, что решателю задач известен (возможно, не очень точный) способ представления подзадач, с которыми легко работать. Будем называть полученное представление аналогией представлению, в котором нужно решить рассматриваемую задачу. В рамках такой аналогии решатель задач может решить все подзадачи или по крайней мере выделить те из них, которые можно решить, и воспользоваться этой информацией, чтобы попытаться решить их в первоначальном представлении. Отметим различие между иерархическими смешанными представлениями и представлениями, основанными на аналогии. В первом случае каждая подзадача имеет свое собственное представление, а во втором — подзадача имеет два представления.

Пожалуй, одно из самых ясных и утонченных применений представлений, основанных на аналогии, появилось весьма давно в исследованиях по искусственному интеллекту в программе „Искусственный геометр" созданной Гелернтером (1963) для решения задач из планиметрии. Формально планиметрия представляет собой аксиоматическую систему, в которой определены правильно построенные выражения, выводимые из посылок с помощью точно сформулированных правил, в основном опирающихся на свойства

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

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

Обсуждаемый метод можно проиллюстрировать задачей:

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

Приведем формальную постановку (рис. 9.9).

Для простоты ограничимся доказательством только одного утверждения: Поскольку правила вывода в геометрии

Рис. 9.9. Задача о параллелограмме.

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

Рис. 9.10. Неточный рисунок для задачи о тупом угле.

Возможные конгруэнтности получаются в результате чисто символьного рассмотрения:

Анализируя рисунок, видим, что только (126) и (12в) „графически равны». Таким образом, только эти подзадачи помещаются в список подзадач, которые программа будет пытаться решить.

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