Intel_Nils

н.нильсон ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ МЕТОДЫ ПОИСКА РЕШЕНИЙ Перевод е аиглийекого Б. Л. Стефанюка Под редакцией С. В. Фомина ИЗДАТЕЛЬСТВО сМИРз МОСКВА !973 ЩК 62 — 606.222.001.67 Книга Нильсона написана как учебник, посвященный методам поиска решенкй в пространстве состояний, — главной теме в исследованиях по искусственному интеллекту. В ией излагаются основные теоретические результаты и для их иллюстрации разбираются многочисленные примеры решения задач — игра в 15, игра тик-так-ту, задача о коммивояжере, задача о пирамидке, доказательство теорем и др.

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

Редакция лпгерагрды ло математическим наукам 0223 — 016 Перевод на русский язык, «ййнр» С' ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА Круг вопросов, объединяемых термином «искусственный интеллект», достаточно широк и довольно неопределен. В самом общем смысле — это решение «интеллектуальных» задач с помощью автоматических методов, в первую очередь с помощью вычислительных машин.

Но какую деятельность следует считать интеллектуальной, а какую нету Это не вполне ясно. Например, мы привыкли рассматривать решение сложных вычислительных задач как деятельность, несомненно, интеллектуальную. Для специалистов же по искусственному интеллекту большой интерес, пожалуй, представит исследование игры в шашки или «крестики и нолики», чем, скажем, решение систем дифференциальных уравнений. И для этого есть довольно веские оенования. Дело в том, что если для той или иной вычислительной задачи (типа решения уравнений) имеется определенный алгоритм решения, то он достаточно естественно и четко представляется последовательностью отдельных элементарных операций, которая и реализуется в виде соответствующей программы для вычислительной машины, Что же касается таких видов деятельности, как распознавание образов, различного рода игры, решение головоломок и т, д., то для ннх, напротив, это формальное разбиение процесса поиска решения на отдельные элементарные шаги часто оказывается весьма затруднительным, даже если само их рец1ение и несложно, Трудность разбиения вычислительных задач на элементарные шаги обычно бывает связана с трудностью формального описания этих задач.

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

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

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

Методы, рассматриваемые в главах 2 — 5, базируются в основном на теории графов и близком к ней комбинаторном аппарате. В главах 6 — 8 довольно широко используются методы математической логики. Хотя все содержание книги ориентировано на автоматические (т. е. реализуемые в виде программ для вычислительных машин) методы перебора, собственно вопросы составления программ в книге ие рассматриваются. Ее цель— дать логические подходы к возможно более эффективному построению таких программ. От читателя книги Нильсона требуется очень умеренная математическая подготовка; по существу достаточно владеть элементарными теоретико-множественными понятиями и основами комбинаторики.

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

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

'Моим родителям, ' ,Уолтеру и Наулине Нильсон ПРЕДИСЛОВИЕ Цель работ по искусственному интеллекту состоит в создании машин, выполняю|цих такие действия, для которых обычно требуется интеллект человека. В число основных направлений этой области входят автоматические методы решения задач, «понимания» и перевода языков, доказательства теорем и распознавание зрительных образов и речи. Хотя многие из этих задач очень трудны, уже создано несколько программ для вычислительной машины, работаю|цих на уровне, приближающемся к человеческому. Дальнейшее продвижение в этой области зависит как от развития теории, так и от накопления практических результатов.

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

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

К таким дисциплинам относятся математическая логика, структурная лингвистика, теория вычислений, теория информационных структур, теория управления, статистическая теория классификации, теория графов и теория эвристического поиска. Последняя из названных дисциплин — эвристический поиск — составляет основной предмет данной книги.

Решение задач посредством эвристически направляемого. метода проб и ошибок в пространстве возможных решений— Предисловие доминнруюшая тема в исследованиях по искусственному интеллекту. Тем не менее пока нет единого уяебника, посвященного объяснению тех теоретических идей, которые лежат в основе таких поисковых процессов. Настоящая работа представляет собой попытку удовлетворить потребность в такой книге. В ней достаточно полно рассматриваются важнейшие методы эвристического поиска, используемые при автоматическом решении задач, доказательстве теорем в игровых ситуациях. Эти методы поиска разъясняются на основе единой системы понятий; кроме того, приводятся некоторые теоретические результаты относительно свойств эвристического поиска. Хотя эффективное применение эвристических методов поиска в больших «практических» задачах только еше начинается, тем не менее во многих случаях онн были успешно использованы в задачах несравненно более сложных, чем выбранные в книге в качестве примеров.

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

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