Н. Нильсон
ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ
МЕТОДЫ ПОИСКА РЕШЕНИЙ
*** 1973 ***
|
Круг вопросов, объединяемых термином «искусственный интеллект», достаточно широк и довольно неопределен. В самом общем смысле — это решение «интеллектуальных» задач с помощью автоматических методов, в первую очередь с помощью вычислительных машин. Но какую деятельность следует считать интеллектуальной, а какую нет? Это не вполне ясно. Например, мы привыкли рассматривать решение сложных вычислительных задач как деятельность, несомненно, интеллектуальную. Для специалистов же по искусственному интеллекту большой интерес, пожалуй, представит исследование игры в шашки или «крестики и нолики», чем, скажем, решение систем дифференциальных уравнений. И для этого есть довольно веские оено-вания. Дело в том, что если для той или иной вычислительной задачи (типа решения уравнений) имеется определенный алгоритм решения, то он достаточно естественно и четко представляется последовательностью отдельных элементарных операций, которая и реализуется в виде соответствующей программы для вычислительной машины. Что же касается таких видов деятельности, как распознавание образов, различного рода игры, решение головоломок и т. д., то для них, напротив, это формальное разбиение процесса поиска решения на отдельные элементарные шаги часто оказывается весьма затруднительным, даже если само их решение и несложно.
Трудность разбиения вычислительных задач на элементарные шаги обычно бывает связана с трудностью формального описания этих задач. Например, человек может отличать кошку от собаки, совершенно не будучи в состоянии дать формальное описание соответствующей процедуры распознавания. Многие из задач, с которыми нам прихЬдится встречаться в науке, играх, практической Деятельности, в принципе могут быть решены путем перебора некоторого, заведомо конечного числа вариантов и выбора из них варианта, в том или ином смысле наилучшего. Однако в достаточно интересных н содержательных ситуациях такой «полный перебор» неосуществим, поскольку обилие вариантов превосходит возможности любой самой совершенной вычислительной машины. Например, число различных позиций в шахматах, равно как и число возможных шахматных партий, состоящих из некоторого ограниченного числа ходов (скажем, не более 40), хотя и конечно, но столь велико, что никакой перебор здесь невозможен. Поэтому в подобных ситуациях возникает вопрос о нахождении возможно более экономных и эффективных способов сокращенного перебора, первоочередного рассмотрения наиболее перспективных путей решения задачи и т. д. Итак, для проблем искусственного интеллекта существенную роль играет вопрос о формальном описании тех или иных неформально поставленных задач, методах их расчленения на отдельные элементарные шаги, а также об организации раз-' личных оптимальных в том или ином смысле процедур перебора вариантов. Именно этим вопросам и посвящена книга Нильсона — одного из ведущих сотрудников Группы искусственного интеллекта Станфордского исследовательского института. Эта книга задумана автором как учебное руководство по проблемам эвристического поиска. В первой, вводной, главе дается общее представление о рассматриваемом круге вопросов, который сам автор характеризует как эвристические методы поиска решений задач. Далее следует изложение этих методов. Методы, рассматриваемые в главах 2—5, базируются в основном на теории графов и близком к ней комбинаторном аппарате. В главах 6—8 довольно широко используются методы математической логики. Хотя все содержание книги ориентировано на автоматические (т. е. реализуемые в виде программ для вычислительных машин) методы перебора, собственно вопросы составления программ в книге не рассматриваются. Ее цель — дать логические подходы к возможно более эффективному построению таких программ. От читателя книги Нильсона требуется очень умеренная математическая подготовка; по существу достаточно владеть элементарными теоретико-множественными понятиями и основами комбинаторики. Знакомство с математической логикой желательно, но не обязательно, поскольку необходимые сведения из этой области, равно как и используемые автором элементы теории графов, достаточно подробно изложены в самой книге. Приводимые в книге результаты и методы автор'иллюстрирует, как правило,’ весьма элементарными модельными примерами— игрой в пятнадцать, задачей о пирамидке и т. д., однако сами эти методы применимы и ко многим проблемам, имеющим серьезный научный и практический интерес. Доступность изложения, сравнительная элементарность аппарата, наглядность приводимых примеров позволяют читателю, желающему лишь составить себе общее представление о рассматриваемом круге вопросов, достигнуть этого с неболь-шрй Затратой времени и сил. Вместе с тем, ие пожалев труда на тщательное изучение книги и, в частности, на разбор задач, помещенных в конце каждой главы, читатель может достигнуть и значительно большего — активного владения понятиями и методами современной теории поиска решений. Такого внимательного изучения книга Ннльсрна несомненно заслуживает. С. В. Фомин ПРЕДИСЛОВИЕ Цель работ по искусственному интеллекту состоит в создании машин, выполняющих такие действия, для которых обычно требуется интеллект человека. В число основных направлений этой области входят автоматические методы решения задач, «понимания» и перевода языков, доказательства теорем и распознавание зрительных образов и речи. Хотя многие из этих задач очень трудны, уже создано несколько программ для вычислительной машины, работающих на уровне, приближающемся к человеческому. Дальнейшее продвижение в этой области зависит как от развития теории, так и от накопления практических результатов. По мере того как практики будут на основании своего опыта понимать пути построения все более сложных систем обработки информации, будет расширяться запас технических приемов работы. Мы можем ожидать, что развитие технологии цифровых вычислительных машин и совершенствование языков для этих машин (в особенности списковых языков) будет и дальше служить основой для получения необходимых новых практических сведений. Что же касается теоретических знаний, то здесь имеются сторонники единой теории искусственного интеллекта. Моя точка зрения состоит в том, что искусственный интеллект представляет собой (или скоро будет представлять собой) инженерную дисциплину, поскольку его первоначальной целью является создание конструкций. Поэтому в поисках теории искусственного интеллекта смысла не больше, чем в поисках, скажем, теории гражданского строительства. Вместо единой общей теории имеется ряд теоретических дисциплин, которые сюда относятся и которые должны изучаться теми, кто выбирает искусственный интеллект своей специальностью. К таким дисциплинам относятся математическая логика, структурная лингвистика, теория вычислений, теория информационных структур, теория управления, статистическая теория классификации, теория графов и теория эвристического поиска. Последняя из названных дисциплин— эвристический поиск — составляет основной предмет данной книги. Решение задач посредством эвристически направляемого, метода проб и ошибок в пространстве возможных решений — доминирующая тема в исследованиях по искусственному интеллекту. Тем не менее пока нет единого учебника, посвященного объяснению тех теоретических идей, которые лежат в основе таких поисковых процессов. Настоящая работа представляет собой попытку удовлетворить потребность в такой книге. В ней достаточно полно рассматриваются важнейшие методы эвристического поиска, используемые при автоматическом решении задач, доказательстве теоре^ в игровых ситуациях. Эти методы поиска разъясняются на основе единой системы понятий; кроме того, приводятся некоторые теоретические результаты относительно свойств эвристического поиска. Хотя эффективное применение эвристических методов поиска в больших «практических» задачах только еще начинается, тем не менее во многих случаях они были успешно использованы в задачах несравненно более сложных, чем выбранные в книге в качестве примеров. Я упомянул некоторые из таких приложений, но я думаю, что существует еще много других. В книгу включены три главы, связанные с доказательством теорем в исчислении предикатов, основанном на принципе построения резольвент, и его применением для решения задач. И хотя этот подход еще не нашел практического приложения, но, я думаю, что в конце концов такие приложения возникнут. Поскольку большая часть литературы по этому вопросу весьма трудна для чтения, мне казалось полезным попытаться-дать достаточно простое изложение, снабдив его большим числом примеров. Первоначально я намеревался включить в книгу главу, где бы рассматривались- методы принятия решений с использованием обучающихся машин. Однако я пришел к выводу, что этот предмет еще не разработан до такой степени, чтобы его можно было включать в учебник. Уровень, на котором представлен материал в настоящей книге, позволяет использовать ее в качестве учебного пособия для студентов старших курсов и аспирантов. Предварительный курс лекций по математической логике был бы полезен, но совершенно необязателен для ее чтения. Читатель, знакомый с основными понятиями теории множеств и комбинаторной математики, не должен встретить трудностей при разборе приводимых в книге доказательств. В конце каждой главы даны задачи, которые можно разбить на три группы. Одни из них просто предназначаются для проверки понимания читателем материала книги, другие содержат важные идеи, которые не нашли исчерпывающего объяснения в тексте, третьи же могли бы служить темами соответствующих курсовых работ. Последняя группа задач отмечена звездочкой. В каждой главе имеются также «Библиографические и исторические замечания», в которых перечисляются и вкратце обсуждаются наиболее важные работы по материалу соответствующей главы. Все эти работы объединены в алфавитном порядке в список литературы в конце книги. При создании этой книги ряд организаций и отдельных лиц оказали мне неоценимую помощь. Я хотел бы особо отметить первоначальную поддержку Отдела информационных систем Управления военно-морских исследований. Дополнительная помощь исходила от Группы техники обработки информации Агентства перспективных исследовательских проектов, которое поддерживает работы по проектам искусственного интеллекта Станфордского исследовательского института и Станфордского университета (где я провел часть академического года в 196&— 1969 гг.). Группа искусственного интеллекта из Станфордского исследовательского института, членом которой я состою, создала все необходимые условия для выполнения этой работы. Доктор Петер Харт из Станфордского исследовательского института затратил немало усилий на чтение и критический разбор нескольких вариантов рукописи. С его помощью изложение материала удалось сделать значительно более ясным. Беседы с профессорами вычислительного факультета Станфордского университета Эдвардом Фейгенбаумом и Артуром Сэмюэлем помогли мне в выборе структуры книги. Я также хочу поблагодарить профессора Дэвида Лакхэма из Станфорда за его попытку научить меня математической (формальной) логике. Многие из аспирантов вычислительного факультета Станфордского университета, в частности Дж. Кеннет Сиберз, внесли предложения, позволившие улучшить эту книгу. Нильс Нильсон К РУССКОМУ ИЗДАНИЮ Это предисловие, написанное специально для русского издания, дает мне возможность высказать ряд новых соображений по поводу искусственного интеллекта вообще и этой книги в частности. Прежде всего я хотел бы остановиться на моей позиции в вопросе важности процессов поиска и различных стратегий решения задач, изучаемых в настоящей книге. В последнее время исследования в области искусственного интеллекта в США в какой-то степени отошли от эвристического поиска. Первая причина этого состоит, по-видимому, в том, что методика эвристического поиска уже доведена до такого уровня развития, при котором дальнейшее изучение приемов поиска едва ли может коренным образом повысить их эффективность. Другая, и более важная причина состоит в том, что, как показывает опыт, обобщенные процессы поиска, взятые сами по себе, как правило, недостаточны для решения по-настоящему сложных задач. Если предстоит написать программы для вычислительной машины, позволяющие переводить с одного языка на другой, мастерски играть в шахматы, эффективно и разумно управлять деятельностью механического, робота, то в такие программы нужно вложить, помимо конкретных сведений (о языке, о шахматах и т. д.), еще и представления «здравого смысла» об окружающем мире. Поэтому исследования в области искусственного интеллекта в нескольких главных центрах США в настоящее время концентрируются на том, как представить эти знания в системах программ для вычислительной машины и как ими пользоваться. Отметив это смещение акцентов, наш потенциальный читатель может подумать, что, пожалуй, ему следует читать вместо нее какие-то другие книги, скажем «Как вкладывать знания в программы для ЭВМ» или лучше «Как компьютеры могут усваивать знания». Мы можем только пожелать, чтобы такие книги существовали. К сожалению, их пока нет. (Возможно, кто-либо из читателей этого предисловия будет участвовать в их написании.) Во всяком случае, цель этой книги состоит не в объяснении наиболее модных в настоящее время вопросов из области искусственного интеллекта, а скорее в том, чтобы ввести читателя в круг идей, которые являются и существенными и достаточно установившимися. Как отмечено в предисловии к американскому изданию, я считаю, что искусственный интеллект — это по существу инженерная дисциплина. Мы хотим строить разумные системы. Как и для всякой инженерной дисциплины, имеется несколько связанных с ней теоретических предметов, знание которых обязательно для специалиста. Я по-прежнему считаю, что эвристический поиск, обсуждаемый в этой книге, представляет главную компоненту техники искусственного интеллекта. Было бы очень трудно понять современный путь развития искусственного интеллекта, не имея основ соответствующих знаний о предметах, обсуждаемых в книге. Эти предметы не стали вдруг ненужными. Наоборот: в настоящее время принято считать, что специалист уже хорошо с ними знаком. Совершенно ясно, что в области искусственного интеллекта существуют также и другие фундаментальные вопросы. К сказанному по этому поводу в предисловии к американскому изданию я бы добавил здесь, что будущему специалисту можно посоветовать приобрести знания в таких областях, как автоматические системы управления и информационные системы. При таких основах мыслящий исследователь будет располагать всеми возможностями для разработки новых важных идей в области искусственного интеллекта. Глава 1 ВВЕДЕНИЕ 1.1. РЕШЕНИЕ ЗАДАЧ И ИСКУССТВЕННЫЙ ИНТЕЛЛЕКТ Многие виды деятельности человека, такие, как решение головоломок, участие в играх, занятия математикой и даже вождение автомобиля, требуют, как это принято считать, участия «интеллекта». Если бы вычислительные машины могли справляться с деятельностью такого типа, то они (вместе с их программами), вероятно, обладали бы в какой-то степени искусственным интеллектом. Многие специалисты полагают, что в конечном итоге искусственный интеллект вычислительных машин превзойдет интеллект человека, хотя теперь все больше и больше осознается тот факт, что процессы, требуемые для выполнения даже самых обычных для человека задач, неизбежно будут чрезвычайно сложными. В настоящей книге мы подробно исследуем некоторые процессы, связанные с решением задач, в которых участвует интеллект. Решение задач может показаться весьма неясным предметом, "и тем не менее на нем концентрируется большая доля исследований по искусственному интеллекту. В самом широком смысле этих слов нахождение решений включает в себя всю вычислительную науку, поскольку всякая вычислительная задача может рассматриваться как задача, решение которой надо найти. Однако для наших целей нужно более узкое определение, которое исключает такие стандартные вычислительные методы, как методы, используемые, скажем, при обращении матрицы 50-го порядка или при решении системы линейных дифференциальных уравнений. Если мы внимательно рассмотрим методы нахождения решений, изучаемые в исследованиях по искусственному интеллекту, то обнаружим, что в большинстве из них используется понятие поиска путем проб и ошибок. Это значит, что в этих методах задачи решаются посредством поиска решения в пространстве возможных решений. Наша цель состоит в разъяснении наиболее важных методов решения задач с использованием процедур поиска. Имеются, конечно, и другие важные направления в изучении искусственного интеллекта. Типичные представители тех из них, которым было уделено особое внимание (кроме нахождения решений), следующие: Обработка сенсорных данных (особенно зрительных образов и речи). Сложные системы хранения и извлечения информации. Обработка естественных языков. К сожалению, никто еще не мог сказать ничего достаточно полезного относительно того, как названные элементы могли бы быть объединены вместе в' одном общем «интеллекте» (каком бы то ни было). В действительности при внимательном анализе становится ясно, что любая из предполагаемых «фундаментальных» компонент интеллектуального поведения содержит, по-видимому, в себе черты других фундаментальных компонент. Так, для сенсорного, восприятия могут потребоваться весьма изощренные способы выбора решения, для которых в свою очередь возникает необходимость в достаточно эффективной системе извлечения информации, опирающейся, возможно, на дополнительный выбор решений и т. д. Наш опыт работы с этими сложными процессами все еще недостаточен для создания единой теории организации интеллекта. На самом деле в настоящее время нет никаких оснований полагать, что такая теория вообще могла бы существовать. Некоторые исследователи считают, что интеллектуальное поведение может быть получено на вычислительных машинах только посредством комбинирования специализированных программ, каждая из которых содержит множество подходящих к данному случаю решений (или, как их часто называют, «программистских находок»), с возможностью обращения к магазину энциклопедических сведений, содержащему хорошо систематизированные факты. Однако сейчас нам не хотелось бы занимать определенную позицию по этому вопросу. Вместо этого мы опишем те приемы решения задач, которые, по-видимому, имеют достаточно широкую область применения. 1.2. ГОЛОВОЛОМКИ И ИГРЫ КАК ПРИМЕРЫ ЗАДАЧ Мы еще не давали точного определения, что значит решить некоторую задачу с применением методов поиска. Точно так же мы не определили, что мы понимаем под задачей. По всей видимости, еще никем не было дано такого простого определения слова «задача», которое полностью бы соответствовало тому интуитивному значению, которое мы намереваемся здесь использовать. Поэтому вместо того, чтобы пытаться дать формальное определение, мы.начнем наше обеуждение с рассмотрения типичного примера задачи. Головоломки и игры представляют собой неисчерпаемый источник примеров, полезных для иллюстрации и испытания мето- дов решения задач. Для вычислительных машин были написаны программы решения многих видов головоломок, достаточно трудных для человека. Были написаны также другие программы, которые побеждали опытных игроков в настольные игры, такие, как шахматы и шашки. Как говорит Минский (1968, стр. 12): «Игры и математические задачи берутся не потому, что они просты и ясны, а потому, что они при минимальных начальных структурах дают нам наибольшую сложность, так что мы можем заняться некоторыми действительно трудными ситуациями, относительно мало отвлекаясь на вопросы программирования». В игровых задачах и решениях головоломок возникли и отшлифовались многие идеи, которые оказались по-настоящему полезными для менее легкомысленных задач. Для иллюстрации понятий, возникающих при решении задач, мы часто будем пользоваться головоломкой, известной как игра в пятнадцать. В ней используется пятнадцать пронумерованных подвижных фишек, расположенных на площадке размером 4X4 клетки. Одна клетка этой площадки остается всегда пустой, так что всегда одну из соседних с ней фишек можно передвинуть на место этой пустой клетки, «передвинув», таким образом, и эту пустую клетку. Игра в пятнадцать иллюстрируется на рис. 1.1, на котором изображены две конфигурации фишек. Рассмотрим задачу перевода начальной конфигурации в заданную целевую конфигурацию. Решением этой задачи служит подходящая последовательность ходов, такая, например, как «передвинуть фишку 12 влево, фишку 15 вниз и т. д.». Игра в пятнадцать — замечательный пример одного класса задач, для которого лучше всего приспособлены методы”, излагаемые в данной книге. В этой задаче имеется точно определенная начальная ситуация и точно определенная цель. Имеется также некоторое множество операций, или ходов, переводящих одну ситуацию в другую. Мы начнем с введения некоторых фундаментальных понятий, связанных с нахождением решений, которые могут быть использованы для нахождения решения игры в пятнадцать. 1.3. СОСТОЯНИЯ и ОПЕРАТОРЫ По-видимому, самый прямолинейный подход при поиске решения для игры в пятнадцать состоит в попытке перепробовать различные ходы, пока не удастся получить целевую конфигурацию. Такого рода попытка по существу связана с поиском при помощи проб и ошибок. (Мы, разумеется, предполагаем, что такой поиск может быть выполнен в принципе, скажем, на некоторой вычислительной машине, а не с привлечением реальной игры в пятнадцать). Отправляясь от начальной конфигурации, мы могли бы построить все конфигурации, возникающие в результате выполнения каждого из возможных ходов, затем построить следующее множество конфигураций после применения следующего хода и т. д., пока не будет достигнута целевая конфигурация. Для обсуждения такого сорта методов поиска решения оказывается полезным введение понятий состояний и операторов для данной задачи. Для игры в пятнадцать состояние задачи — это просто некоторое конкретное расположение фишек. Начальная и целевая конфигурации представляют собой соответственно начальное и целевое состояния. Пространство состояний, достижимых из начального состояния,' состоит из всех тех конфигураций фишек, которые могут быть образованы в результате допустимых правилами перемещений фишек. Многие из задач, с которыми мы будем сталкиваться, имеют чрезвычайно большие (если не бесконечные) пространства состояний1). Оператор преобразует одно состояние в другое. Игру в пятнадцать естественнее всего интерпретировать как игру, имеющую четыре оператора, соответствующие следующим ходам: передвинуть пустую клетку (пробел) влево, вверх, вправо и вниз. В некоторых случаях оператор может оказаться неприложимым к какому-то состоянию: так, оператор «передвинуть пробел вправо» не может быть применен к целевому состоянию на рис. 1.1. На нашем языке состояний и операторов решение некоторой проблемы есть последовательность операторов, которая преобразует начальное состояние в целевое. Пространство состояний, достижимых из данного начального состояния, полезно представлять себе в виде графа, вершины которого соответствуют этим состояниям. Вершины такого графа связаны между собой дугами, отвечающими операторам. На рис. 1.2 показана небольшая часть графа для игры в пятнадцать. На этом графе в каждой вершине помещена та конфигурация фишек, которую она представляет. 1) В игре в пятнадцать имеется 16 различных конфигураций из фишек и пустой клетки. Пологина из них (или примерно 10,5-1012) достижима из данной начальной конфигурации. KOHEЦ ФPAГMEHTA КНИГИ |
