Часть III. ДОКАЗАТЕЛЬСТВО ТЕОРЕМ И РЕШЕНИЕ ЗАДАЧ

Глава 9. МАШИННОЕ ПРЕДСТАВЛЕНИЕ В РЕШЕНИИ ЗАДАЧ

9.0. Использование представлений

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

Мыслители не решают непосредственно задач как они есть, а занимаются поиском представления задач. Этот факт настолько обыден, что мы не ощущаем его важность до тех пор, пока не попытаемся построить программу, предназначенную для решения задач. Конечно, такая программа работает не с реальным физическим миром, а с его символьным представлением в предположении, что существует соответствие между символами и операциями над ними в машине, с одной стороны, и состояниями и действиями во внешнем мире — с другой. Фактически всю прикладную математику можно рассматривать подобным образом.

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

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

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

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

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

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

Для получения списочного представления составим список ученых с указанием людей, с которыми каждый из них беседует:

Для определенности будем считать, что открытие сделал Джоно. Чтобы решить нашу задачу, перечислим людей, с которыми Джонс беседует: Смит и Томас. Они услышат об открытии на первой встрече.

Рис. 9.1. Граф сети общения.

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

Представление в виде графа, называемое графовым представлением, точно так же соответствует реальности, как и списочная модель, но имеет некоторые преимущества благодаря своей наглядности. Сеть общения из приведенного выше примера изображена на рис. 9.1 в виде графа, в котором узлы соответствуют ученым, а дуги соединяют человека, передающего новость, с принимающим ее. Из рисунка сразу видно, что это общество распадается на две группы, не связанные между собой: нет возможности передать сообщение от Джонса к Беннету, Мейзону и Джеймсу. Несколько более подробное исследование показывает, что дальше всех из достижимых для Джонса находится Уайт (расстояние по графу равно 3 дугам). При решении этой задачи людьми графовое представление

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

И наконец, матричное представление (предложенное Харари, Норманом и Картрайтом, 1965). Оно годится для машинного решения задач, но людям нелегко пользоваться им.

Рис. 9.2. Матрица связности, соответствующая сети, изображенной на рис. 9.1.

Определим путь как маршрут, по которому информация передается от одного к другому, и длину пути как число шагов в нем. Таким образом, последовательности Джонс, Томас, Браун и Джонс, Смит, Грин, Браун (рис. 9.1) являются путями от Джонса до Брауна с длинами 2 и 3 соответственно. Обозначим через С матрицу, элементы которой Си равны 1 тогда и только тогда, когда ученый общается с ученым и 0 в противном случае. Считаем, что На рис. 9.2 показана матрица, соответствующая графу на рис. 9.1. Заметим, что матрицу С можно интерпретировать и так: определяет число путей (не больше одного) длины 1 от ученого к ученому Этот способ выразить смысл, содержащийся в рассматриваемой матрице, кажется неуклюжим, пока не поставлен более общий вопрос. Сколько путей длины 2 ведет от к Для того чтобы ответить на этот вопрос, подсчитаем число путей длины 1, ведущих от к и число таких путей от к для всех возможных Тогда число путей длины 2, ведущих от к равно

Запишем (1) в матричной форме:

Для того чтобы найти число путей от к длины 3, определим для всех число путей длины 2, ведущих от к и длины 1, ведущих от к Число путей от к длины 3 равно

или в матричной форме

Обобщим (4) на случай путей длины

Процесс общения оканчивается в точке, в которой увеличение длины пути не увеличивает числа путей. Математически это означает, что

Пусть — наименьшее целое число, для которого справедливо (6). Ненулевое значение указывает на то, что от к ведет по крайней мере один путь длины не более Если то от к пути нет.

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

В следующем разделе излагаются типы представлений для решения задач в соответствии с работами Ньюэлла и Саймона (1972) и Нильсона (1971). Разделение на типы не строгое. Похоже, что по крайней мере между некоторыми из представленных типов можно установить формальную эквивалентность. Бенерджи (1969) исследует это несколько подробнее. Однако предположение о том, что все представления можно считать прагматически эквивалентными, кажется сомнительным. Представления можно интерпретировать как эвристические подходы к решению задач. Хорошее представление дает хороший метод решения задач. И хотя формальная эквивалентность хорошего представления плохому интересна с точки зрения математики, для практического решения задач этот факт мало полезен.