|
Труднорешаемые задачи
Принцип IBM В среде математиков известна такая притча. В давние времена,
когда никто и понятия не имел о компьютерах и их возможностях, один индийский
мудрец оказал большую услугу своему правителю. Правитель решил отблагодарить его
и предложил ему самому выбрать награду. На что мудрец ответил, что пожелал бы
видеть шахматную доску, на каждой клетке которой были бы разложены зернышки
пшена в следующем порядке: на первой – 2, на второй – 2х2=4, на третьей –
2х2х2=8, на четвертой 2 Сначала
правитель обрадовался легкости расплаты. Но вот выполнить обещание не смог, так
как он и его слуги вряд ли когда-нибудь смогли бы отсчитать 2 Задача, сформулированная в этой притче, относится к разряду тех, при
решении которых самый современный компьютер бессилен так же, как в древности
слуги правителя. Зная производительность современных ЭВМ, не представляет труда
убедиться в том, что пользователю не хватит всей его жизни для отсчета зерен, но
в данном случае это даже не самое главное. Суть проблемы в том, что достаточно
изменить входные данные, чтобы перейти от решаемой задачи к
нерешаемой. Каждый человек в зависимости от своих счетных способностей может
определить, начиная с какой клетки (пятнадцатой или допустим, восемнадцатой)
продолжать отсчитывать зерна для него не имеет смысла. То же самое можно
определить и для ЭВМ, для которой подобные характеристики написаны в технической
документации. В случаях, когда незначительное увеличение входных данных задачи
ведет к возрастанию количества повторяющихся действий в степенной зависимости,
то специалисты по алгоритмизации могут сказать, что мы имеем дело с
неполиномиальным алгоритмом, т.е. количество операций возрастает в зависимости
от числа входов по закону, близкому к экспоненте е Подобные алгоритмы решения
имеет чрезвычайно большой круг задач, особенно комбинаторных проблем, связанных
с нахожденим сочетаний, перестановок, размещений каких-либо объектов. Всегда
есть соблазн многие задачи решать исчерпыванием, т.е. проверкой всех возможных
комбинаций. Например, так решается задача безошибочной игры в шахматы. Эта
задача относится к классическим нерешаемым! Ни одна современная ЭВМ не сможет
сгенерировать все простые перестановки более чем 12 разных предметов (более 479
млн.), не говоря уже о всех возможных раскладках колоды из 36 игральных
карт. Поэтому труднорешаемой (нерешаемой) задачей можно называть такую задачу,
для которой не существует эффективного алгоритма решения. Экспоненциальные
алгоритмы решений, в том числе и исчерпывающие, абсолютно неэффективны для
случаев, когда входные данные меняются в достаточно широком диапазоне значений,
следовательно, в общем случае считать их эффективными нельзя. Эффективный
алгоритм имеет не настолько резко возрастающую зависимость количества вычислений
от входных данных, например ограниченно полиномиальную, т.е х находится в
основании, а не в показателе степени. Такие алгоритмы называются
полиномиальными, и, как правило, если задача имеет полиномиальный алгоритм
решения, то она может быть решена на ЭВМ с большой эффективностью. К ним можно
отнести задачи сортировки данных, многие задачи математического программирования
и т.п. Чего же не может и, скорее всего, никогда не сможет компьютер в его
современном (цифровая вычислительная машина) понимании? Ответ очевиден:
выполнить решение полностью аналитически. Постановка задачи заключается в замене
аналитического решения численным алгоритмом, который итеративно (т.е. циклически
повторяя операции) или рекурсивно (вызывая процедуру расчета из самой себя)
выполняет операции, шаг за шагом приближаясь к решению. Если число этих операций
возрастает, время выполнения, а возможно, и расход других ресурсов (например,
ограниченной машинной памяти), также возрастает, стремясь к бесконечности.
Задачи, своими алгоритмами решения создающие предпосылки для резкого
возрастания использования ресурсов, в общем виде не могут быть решены на
цифровых вычислительных машинах, т.к. ресурсы всегда
ограничены Другое возможное решение
описанной проблемы – в написании численных алгоритмов, моделирующих
технологические особенности творческой деятельности и сам подход к
аналитическому решению. Методы, используемые в поисках открытия нового,
основанные на опыте решения родственных задач в условиях выбора вариантов,
называются эвристическими. На основе таких методов и выполняется машинная игра в
шахматы. В эвристике шахматы рассматриваются как лабиринт, где каждая позиция
представляет собой площадку лабиринта. Почему же именно такая модель? В
психологии мышления существует т.н. лабиринтная гипотеза, теоретически
представляющая решение творческой задачи как поиск пути в лабиринте, ведущего от
начальной площадки к конечной. Конечно, можно проверить все возможные пути, но
располагает ли временем попавший в лабиринт? Совершенно нереально исчерпывание
шахматного лабиринта из 2х10 площадок! Занимаясь поиском ответа,
человек пользуется другими способами, чтобы сократить путь к решению. Возможно
сокращение числа вариантов перебора и для машины, достаточно "сообщить" ей
правила, которые для человека – опыт, здравый смысл. Такие правила приостановят
заведомо бесполезные действия. Исторически попытки моделирования процессов мышления для
достижения аналитических решений делались достаточно давно (с 50-х гг ХХ в.), и
соответствующая отрасль информатики была названа искусственным интеллектом.
Исследования в этой области, первоначально сосредоточенные в нескольких
университетских центрах США - Массачусетском технологическом институте,
Технологическом институте Карнеги в Питтсбурге, Станфордском университете, -
ныне ведутся во многих других университетах и корпорациях США и других стран. В
общем исследователей искусственного интеллекта, работающих над созданием
мыслящих машин, можно разделить на две группы. Одних интересует чистая наука и
для них компьютер- лишь инструмент, обеспечивающий возможность экспериментальной
проверки теорий процессов мышления. Интересы другой группы лежат в области
техники: они стремятся расширить сферу применения компьютеров и облегчить
пользование ими. Многие представители второй группы мало заботятся о выяснении
механизма мышления - они полагают, что для их работы это едва ли более полезно,
чем изучение полета птиц в самолетостроении. В настоящее время, однако,
обнаружилось, что как научные, так и технические поиски столкнулись с
несоизмеримо более серьезными трудностями, чем представлялось первым
энтузиастам. На первых порах многие пионеры искусственного интеллекта верили,
что через какой-нибудь десяток лет машины обретут высочайшие человеческие
таланты. Предполагалось, что преодолев период "электронного детства" и
обучившись в библиотеках всего мира, хитроумные компьютеры, благодаря
быстродействию, точности и безотказной памяти постепенно превзойдут своих
создателей-людей. Сейчас, в соответствии с тем, что было сказано выше, мало кто
говорит об этом, а если и говорит, то отнюдь не считает, что подобные чудеса не
за горами. На протяжении всей своей короткой истории исследователи в области
искусственного интеллекта всегда находились на переднем крае информатики. Многие
ныне обычные разработки, в том числе усовершенствованные системы
программирования, текстовые редакторы и программы распознавания образов, в
значительной мере рассматриваются на работах по искусственному интеллекту.
Короче говоря, теории, новые идеи, и разработки искусственного интеллекта
неизменно привлекают внимание тех, ктостремится расширить области применения и
возможности компьютеров, сделать их более "дружелюбными" то есть более похожими
на разумных помощников и активных советчиков, чем те педантичные и туповатые
электронные рабы, какими они всегда были. Несмотря на многообещающие
перспективы, ни одну из разработанных до сих пор программ искусственного
интеллекта нельзя назвать "разумной" в обычном понимании этого слова. Это
объясняется тем, что все они узко специализированы; самые сложные экспертные
системы по своим возможностям скорее напоминают дрессированных или механических
кукол, нежели человека с его гибким умом и широким кругозором. Даже среди
исследователей искусственного интеллекта теперь многие сомневаются, что
большинство подобных изделий принесет существенную пользу. Немало критиков
искусственного интеллекта считают, что такого рода ограничения вообще
непреодолимы. К числу таких скептиков относится и Хьюберт Дрейфус, профессор
философии Калифорнийского университета в Беркли. С его точки зрения, истинный
разум невозможно отделить от его человеческой основы, заключенной в человеческом
организме. "Цифровой компьютер - не человек, - говорит Дрейфус. - У компьютера
нет ни тела, ни эмоций, ни потребностей. Он лишен социальной ориентации, которая
приобретается жизнью в обществе, а именно она делает поведение разумным. Я не
хочу сказать, что компьютеры не могут быть разумными. Но цифровые компьютеры,
запрограммированные фактами и правилами из нашей, человеческой, жизни,
действительно не могут стать разумными. Поэтому искусственный интеллект в том
виде, как мы его представляем, невозможен". В это же время ученые стали понимать, что создателям
вычислительных машин есть чему поучиться у биологии. Среди них был нейрофизиолог
и поэт-любитель Уоррен Маккалох, обладавший философским складом ума и широким
кругом интересов. В 1942 г. Маккалох, участвуя в научной конференции в Нью-
Йорке, услышал доклад одного из сотрудников Винера о механизмах обратной связи в
биологии. Высказанные в докладе идеи перекликались с собственными идеями
Маккалоха относительно работы головного мозга. В течении следующего года
Маккалох в соавторстве со своим 18-летним протеже, блестящим математиком
Уолтером Питтсом, разработал теорию деятельности головного мозга. Эта теория и
являлась той основой, на которой сформировалось широко распространенное мнение,
что функции компьютера и мозга в значительной мере сходны. Исходя отчасти из
предшествующих исследований нейронов (основных активных клеток, составляющих
нервную систему животных), проведенных Маккаллохом, они с Питтсом выдвинули
гипотезу, что нейроны можно упрощенно рассматривать как устройства, оперирующие
двоичными числами. В 30-е годы XX в. пионеры информатики, в особенности
американский ученый Клод Шеннон, поняли, что двоичные единица и нуль вполне
соответствуют двум состояниям электрической цепи (включено-выключено), поэтому
двоичная система идеально подходит для электронно-вычислительных устройств.
Маккалох и Питтс предложили конструкцию сети из электронных "нейронов" и
показали, что подобная сеть может выполнять практически любые вообразимые
числовые или логические операции. Далее они предположили, что такая сеть в
состоянии также обучаться, распознавать образы, обобщать, т.е. она обладает
всеми чертами интеллекта. Теории Маккаллоха-Питтса в сочетании с книгами
Винера вызвали огромный интерес к разумным машинам. В 40-60-е годы все больше
кибернетиков из университетов и частных фирм запирались в лабораториях и
мастерских, напряженно работая над теорией функционирования мозга и методично
припаивая электронные компоненты моделей нейронов. Из этого кибернетического,
или нейромодельного, подхода к машинному разуму скоро сформировался так
называемый "восходящий метод" - движение от простых аналогов нервной системы
примитивных существ, обладающих малым числом нейронов, к сложнейшей нервной
системе человека и даже выше. Конечная цель виделась в создании "адаптивной
сети", "самоорганизующейся системы" или "обучающейся машины" - все эти названия
разные исследователи использовали для обозначения устройств, способных следить
за окружающей обстановкой и с помощью обратной связи изменять свое поведение,
т.е. вести себя так же как живые организмы. Естественно, отнюдь не во всех
случаях возможна аналогия с живыми организмами. Как однажды заметили Уоррен
Маккаллох и его сотрудник Майкл Арбиб, "если по весне вам захотелось обзавестись
возлюбленной, не стоит брать амебу и ждать пока она эволюционирует". Но дело
здесь не только во времени. Основной трудностью, с которой столкнулся
"восходящий метод" на заре своего существования, была высокая стоимость
электронных элементов. Слишком дорогой оказывалась даже модель нервной системы
муравья, состоящая из 20 тыс. нейронов, не говоря уже о нервной системе
человека, включающей около 100 млрд. нейронов. Даже самые совершенные
кибернетические модели содержали лишь неколько сотен нейронов. Столь
ограниченные возможности обескуражили многих исследователей того
периода. В настоящее время наличие сверхпроизводительных
микропропроцессоров и дешевизна электронных компонентов позволяют делать
значительные успехи в алгоритмическом моделировании искусственного интеллекта.
Такой подход дает определенные результаты на цифровых ЭВМ общего назначения и
заключается в моделировании процессов жизнедеятельности и мышления с
использованием численных алгоритмов, реализующих искусственный интеллект. Здесь
можно привести много примеров, начиная от простой программы игрушки "тамагочи" и
заканчивая моделями колонии живых организмов и шахматными программами,
способными обыграть известных гроссмейстеров. Сегодня этот подход поддерживается
практически всеми крупнейшими разработчиками аппаратного и программного
обеспечения, поскольку достижения при создании эвристических алгоритмов
используются и в узкоспециальных, прикладных областях при решении сложных задач,
принося значительную прибыль разработчикам. Другие подходы сводятся к созданию
аппаратуры, специально ориентированной на те или иные задачи, как правило, эти
устройства не общего назначения (аналоговые вычислительные цепи и машины,
самоорганизующиеся системы, перцептроны и т.п.). С учетом дальнейшего развития
вычислительной техники этот подход может оказаться более перспективным, чем
предполагалось в 50-80гг.
| |
