Intel_Nils, страница 4

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

В главах 4 и 5 мы вернемся к обсуждению методов, основанных на редукции задач. Ед Исаользоеание формальной логики при решении задач !Л. ИСПОЛЬЗОВАНИЕ ФОРМАЛЬНОЙ ЛОГИКИ ПРИ РЕШЕНИИ ЗАДАЧ Часто для решения задачи либо требуется проведение логического анализа в определенном объеме, либо поиск решения существенно облегчается после такого анализа. Иногда такой анализ показывает, что определенные проблемы неразрешимы. В игре в пятнадцать, например, можно доказать'), что целевая конфигурация не может быть получена из начальной конфигурации Необходимость делать логические заключения возникает как в подходах, основанных на использовании пространства состояний, так и в подходах, связанных с редукцией задач.

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

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

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

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

Он мог бы решать задачи из достаточно широких областей, поскольку существуют логические формализмы, достаточно универсальные для того, чтобы выразить любую информацию и записать любую задачу. Са. ДВА СОСТАВНЫХ ЭЛЕМЕНТА ПРОЦЕССА РЕШЕНИЯ ЗАДАЧ: ПРЕДСТАВЛЕНИЕ И ПОИСК (ПЕРЕБОР) В каждом из подходов к решению задач, о которых мы говорили, для построения решения необходим поиск какого-либо типа.

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

Мы увидим, что существует несколько вариантов представлений для одной н той же задачи, причем некоторые представления дают намного более узкие пространства состояний, чем другие. Так как даже самые эффективные методы поиска будут непригодны, если пространство, в котором ведется поиск, слишком велико, то важно уметь представлять задачу самым экономным из возможных способов. Вопрос о выборе представления— общий для любого способа решения задач, но, к сожалению, в исследованиях по искусственному интеллекту еще не выработано универсального автоматического метода для нахождения искусных формулировок задач. Поэтому, несмотря на то что имеется два аспекта в автоматическом решении задач, а именно представление и поиск, в настоящей книге мы вынуждены ограничиться рассмотрением главным образом вопросов поиска. 1.7. БИБЛИОГРАФИЧЕСКИЕ И ИСТОРИЧЕСКИЕ ЗАМЕЧАНИЯ я Интеллект» вычислительных машин Вопрос о том, могут лн машины «думать» (нли будут ли онн когда-либо способны на это), все еще вызывает живое обсуждение даже среди тех, кто допускает, что сам человек представляет собой некую машину.

Тьюринг (1960) устранил многие из стандартных доводов против мыслящих' машин, Для решения вопроса о том, может ли машина мыслить, им был предложен тест, который принято теперь называть тестом Тьюринга. Селфридж и Келли (!962) обсуждали вопрос об объеме практических трудностей, стоящих на пути создания разумных машин, после того, как они пришли к выводу о том, что здесь неизвестно никаких теоретических запретов.

Хьюберт Дрейфус (1966) заявил, что цифровые вычислительные машины принципиально неспособны на выполнение таких обязательных для интеллекта действий, как «осознание края» н еясное группирование». Его аргументация была последовательно опровергнута Пейпертом (1968), Гл. Ь В«еде«ее Искусственный интеллект в целом Попытки упорядочить область искусственного интеллекта никогда не были вполне успешны. В важной обзорной статье Минский (196!а) предложил следующий перечень; поиск, распознавание образов, обучение, решение задач, логические выводы.

Такая схема все еще приносит пользу, хотя ее классификационные достоинства сильно снижаются изобилием в литературе утверждений, имеющих форму: «проблема Х по существу является проблемой У», где в качестве Х и У можно взять любую пару компонент, о которых говорил Минский. Уже не так давно Минский (1968) написал еще одну содержательную статью об основаниях искусственного интеллекта, где делается вывод, что главной является проблема образования, поддержания и извлечения сведений из некоторой большой их совокупности. Различные подходы в области искусственного интеллекта При попытке построить разумные машины мы, естественно, ставим вопрос о том, в чем же состоит секрет естественного интеллекта.

Поиски ответа на этот вопрос были связаны с рядом замечательных событий, однако до сих пор никому не удалось раскрыть этой тайны. Розенблаттом (1962) были предложены модели мозга, названные персеатроиами. Это были сети из искусственных нейронов, в основе которых лежали нейронные модели Маккаллока — Питтса (1943). Изучение персептронов стимулировалось вначале исследователями по распознаванию образов и привело к некоторым изящным математическим результатам по вычислительной геометрии (Минский и Пейнерт, 1969). Однако сложные процессы, связанные с интеллектом, оказались вне пределов возможностей, заложенных в'этих простых персептронных моделях.

Другим подходом, основанным на биологических представлениях, была весьма грандиозная попытка промоделировать саму эволюцию. Поскольку эволюционному процеебу потребовалось два миллиарда или около того лет для,создания разумного человека, то почему бы нам не воспользоваться вычислительной машиной и не промоделировать такой эволюционный процесс при высокой скорости? Фогель и др. (1966) описывают эксперименты, в которых с использованием идей мутации и'избирательного выживания моделировался процесс построения многих поколений машин с конечным числом состояний, Хотя такой подход дает возможность свести несколько первых миллионов лет эволюции к нескольким дням вычислительного времени, создается впечатление, что важные средняя и поздняя стадии эволюции связаны со столь сложными структурами (хотя и не являющимися еще «разумными»), что их эволюция уже не может быть ускорена путем моделирования на вычислительной д7. Бибяиогра4ические и историчЕские еимечоиия машине.