ПРЕДИСЛОВИЕ РЕДАКТОРА ПЕРЕВОДА

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

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

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

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

Именно этим вопросам и посвящена книга Нильсона — одного из ведущих сотрудников Группы искусственного интеллекта Станфордского исследовательского института.

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

От читателя книги Нильсона требуется очень умеренная математическая подготовка; по существу достаточно владеть элементарными теоретико-множественными понятиями и основами комбинаторики. Знакомство с математической логикой желательно, но не обязательно, поскольку необходимые сведения из этой области, равно как и используемые автором элементы теории графов, достаточно подробно изложены в самой книге.

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

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

С. В. Фомин

ПРЕДИСЛОВИЕ

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

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

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

Решение задач посредством эвристически направляемого, метода проб и ошибок в пространстве возможных решений —

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

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

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

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

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

В каждой главе имеются также «Библиографические и исторические замечания», в которых перечисляются и вкратце

обсуждаются наиболее важные работы по материалу соответствующей главы. Все эти работы объединены в алфавитном порядке в список литературы в конце книги.

При создании этой книги ряд организаций и отдельных лиц оказали мне неоценимую помощь. Я хотел бы особо отметить первоначальную поддержку Отдела информационных систем Управления военно-морских исследований. Дополнительная помощь исходила от Группы техники обработки информации Агентства перспективных исследовательских проектов, которое поддерживает работы по проектам искусственного интеллекта Станфордского исследовательского института и Станфордского университета (где я провел часть академического года в 196&- 1969 гг.). Группа искусственного интеллекта из Станфордского исследовательского института, членом которой я состою, создала все необходимые условия для выполнения этой работы.

Доктор Петер Харт из Станфордского исследовательского института затратил немало усилий на чтение и критический разбор нескольких вариантов рукописи. С его помощью изложение материала удалось сделать значительно более ясным. Беседы с профессорами вычислительного факультета Станфордского университета Эдвардом Фейгенбаумом и Артуром Сэмюэлем помогли мне в выборе структуры книги. Я также хочу поблагодарить профессора Дэвида Лакхэма из Станфорда за его попытку научить меня математической (формальной) логике. Многие из аспирантов вычислительного факультета Станфордского университета, в частности Дж. Кеннет Сиберз, внесли предложения, позволившие улучшить эту книгу.

Нильс Нильсон

К РУССКОМУ ИЗДАНИЮ

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

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

Другая, и более важная причина состоит в том, что, как показывает опыт, обобщенные процессы поиска, взятые сами по себе, как правило, недостаточны для решения по-настоящему

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

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

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

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

Март, 1973 Нильс Нильсон

Падо-Дльтр