Intel_Nils, страница 5

Поэтому такая «искусственная эволюция» не привела к созданию действительно сложных машин, Другой способ понять, что такое естественный интеллект животных, состоит в том, чтобы изучать их поведение н в особенности поведение человека при решении задач. Трейвис «1963, 1967) обсуждает роль самонаблюдения при создании решателя задач. Ньюэлл, Шоу и Саймон (1959) описали «универсальный решатель задач», который обращается с задачей в значительной степени так же, как это делает человек. Богатым источником идей о том, как человек подходит к решению задач, является книга Пойа (1957).

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

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

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

На построение настоящей книги оказала сильное влияние серия трудных, но очень ценных статей Амареля (1965, !967, !969). Формализация некоторых идей поиска решений, которыми мы занимаемся в нашей книге, дана в статье Сэндуолла (1969), Весьма формальное исследование вопросов решения задач и разыгрывания игр содержится в книге Бенерджн (1969), Подход к решению задач с использованием пространства состояний получил такое название по аналогии с ситуацией в теории управления, где также для подобных целей используются пространства состояний.

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

Это различие носит тот же характер, что и отмеченное Амарелем (1967) различие между методами «продукционного типа»'и «редукционного типа». Слейджл (1963а) при описании своей программы, предназначенной для символического интегрирования, также счел полезным использовать понятие сведения задачи к подзадачам. По нашему убеждению, работу универсального решателя задач (Оепега! Ргой)еш Ьо1- чег) Ньюэлла и его сотрудников (Эрнст и Ньюэлл, 1969) гораздо легче себе уяснить, если его описывать как решатель задач, опирающийся на сведение задачи к подзадачам. Использование формальных методов для построения логических выводов при решении задач может быть обнаружено в заметках Маккарти (!958, !963) о системе, «воспринимающей советы». Эта система должна была выводить решения для задач из большого количества аксиом, представляющих те знания, которые имеются у решателя Такой системе очень легко давать «советы», просто добавляя новые аксиомы.

Работа Блэка (!964) была одной из первых работ, основанных на этой идее. О. некоторых из последних работ в этой области будет идти речь в гл. 7. Ряд блестящих идей о решении больших комбинаторных задач высказал Лив Шен (1965, 1970), Он привел несколько эффективных стратегий разбиения задачи на подзадачи. Х7. Библиографические и исторические эамечакиа Приложения программ решения задач Стоит задаться вопросом о том, был ли хоть один из мего. дов, так хорошо работающих на головоломках и играх, когда.

либо с пользой применен для «реальных» задач, Методы, исполь. зующие пространство состояний, нашли применение для реше. ния задач исследования операций, таких, как известная задача о коммивояжере. Примером может служить метод, предложен. ный в диссертации Шапиро (1966) и рассмотренныи затем Белл- мором и Немхозером (!968). Хотя задача о коммивояжере может показаться легкомысленной, как головоломки и игры, она служит моделью важных с экономической точки зрения проблем, возникающих при составлении расписаний и планировании производства. Другие приложения метода, использующего пространство состояний, даны в работе Уитни (1969) о дистанционном управлении манипуляторами, в работе йелинека (1969) о последовательном декодировании и в работе Монтанари (!970) о подборе хромосом.

Методы, основанные на редукции задачи, были использованы в одной системе, осуществляющей интегрирование в символической записи (Слейджл, 1963а), и в системе, анализирующей данные с масспектрографа (Фейгенбауи, Букхэнан и Ледерберг, 197!), Важнейшая литература по искусственному интеллекту По вопросам искусственного интеллекта имеется много обзоров и существует обширная литература. Один из первых аннотированных списков литературы принадлежит Минскому (1961б). Более поздние обзоры Фейгенбаума (1963) и Соломонова (1966) содержат много дополнительных работ. Еще больше литературных ссылок, сопровождающихся рассуждениями о будущем этой области исследований, содержится в недавнем обзоре Фейгенбаума (1969). Часто делаются ссылки на книгу «Вычислительные машины и мышление» под редакцией Фейгенбаума и Фельдмана, поскольку в ней нашло отображение много более ранних статей в этой области.

Под редакцией Мичи и др. выходит серия книг, носящая название «Машинный разум». Здесь публикуются доклады, сделанные на конференциях по машинному разуму, проводимых ежегодно в Эдинбурге. Следующая важная книга — это «Обработка семантической информации» под редакцией Минского; в ней содержатся полные тексты несколькихдиссертаций, связанных с обработкой языков и вопросами «понимания». Журнал Аг(11!с!а! 1п1е11!депсе, целиком предназначенный для работ по искусственному интеллекту, начал издаваться в 1970г.

Статьи по этой тематике время от времени пубчикуются также в )опгпа! о1 111е Аззос)а1!оп (ог Сотри()пй Масп!негу. 24 Гл. й Введемие В США координацию деятельности в области искусственного интеллекта осуществляет специальная исследовательская Группа по искусственному интеллекту (51ОАКТ) Ассоциации вычислительных устройств (АСМ). Она издает информационный бюллетень, в котором время от времени появляются реферативные материалы, нигде больше не публикуемые. В Европе издается информационный бюллетень Группой искусственного интеллекта и моделирования поведения (А!ЬВ) Британского общества вычислительных машин. Программы решений задач были отшлифованы на ряде головоломок и игр. Хорошими книгами по головоломкам являются книги Мартина Гарднера (!959, 1961), который редактирует раздел головоломок в журнале Т)!е Ьс!еп1!(!с Агпег!сап.

Интересны также книги по головоломкам Дьюденея (!958, 1967), известного английского составителя головоломок. В книге головоломок Шуха (1968) особо выделяются стратегии поиска. методом проб и ошибок и редукции задач. У игры в пятнадцать имеется длительная история, которая обсуждается Мартинбм Гарднером (1964, 1965а, б, в) и Боллом (1931). Для полноты изложения мы иногда будем ссылаться в этой книге на неопубликованные работы и отчеты. Авторы этих материалов в отдельных случаях могут выслать их копии, если обратиться к ним с такой просьбой.

Задачи !Л. Прочтите статью Ньюзлла (!969) и сопоставьте применяемую им классификацию методов решений задач с.описанной в настоящей главе. Ка. кие из методов Ньюзлла можно рассматривать как методы поиска в пространстве состояний! Что является для них состояниями и операторамиг !.2.

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

Приведите несколько примеров из повседневной челоаечесной деятель. ности, характеризующихся гем или иным поигком по методу проб и ошибок. (Примеры могут касаться вопроса о том, что одеть, что приготовить к обеду н т, л.) П4. Прочтите работу Ньюэлла, Шоу и Саймона (!997) о логической теории машин и опишите ее содержание как с точки зрения подхода, основанного из~пространстве состояний, таи и с точки зрения редукции задач.