Вычислительное мышление. Метод решения сложных задач - Питер Макоуэн

Пакуем чемоданы

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

Хорошей альтернативой будет жадный алгоритм. С его помощью не получится упаковать все максимально компактно, но порой он работает весьма хорошо. Как выбрать, что положить сначала? Исходите из жадности. Положите самый большой предмет внутрь, пусть он займет как можно больше места. Теперь положите следующий по размеру — и так далее. Если что-то не помещается, берите следующий чемодан. Обычно все получается само собой, потому что, когда у вас остаются небольшие свободные пространства, вы заполняете их небольшими предметами. Это годный эвристический алгоритм — с такими алгоритмами вы достаточно хорошо (но не безупречно) справитесь с задачей. Они не гарантируют оптимального решения.

Снова в дороге

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

Хороший, плохой, злой

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

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

Теперь, ознакомившись с основами вычислительного мышления, рассмотрим, как с его помощью создать искусственный разум для робота. Строить тело робота интересно, но без «мозга» оно ни на что не способно. Мы изучим историю роботостроения, выясним, что такое «понимать», и создадим систему искусственного интеллекта — виртуального собеседника, или чат-бота.

Недоброе имя?

Термин «робот» впервые появился в пьесе R.U.R. («Россумские универсальные роботы») чешского писателя-публициста Карела Чапека. В этой пьесе на заводе, расположенном на уединенном острове, делают человекоподобных роботов, «труд которых в пять раз дешевле человеческого». По ходу действия разворачивается знакомый сюжет, который заканчивается тем, что (подумать только!) все люди, за исключением одного, погибают во время восстания роботов. В финале последний человек совершает акт самопожертвования и заставляет двух роботов полюбить друг друга. Занавес.

Считается, что в пьесе отразилась озабоченность Чапека тоталитарным обществом, которую он выразил в виде научной фантастики. Отсюда и мрачный сюжет. Если бы автор оказался в иной политической ситуации, то появление роботов в информационном пространстве могло бы быть не таким зловещим. Это подчеркивает тот факт, что выбранное Чапеком слово «робот» происходит от чешского robota, означающего «рабский труд». Сначала Чапек хотел назвать этих существ laboři (от латинского labor — «работать»), но передумал и попросил совета у брата Йозефа. Йозеф предложил использовать слово robota. Братья Чапеки создали обоснование и название для роботов как раз тогда, когда в западном мире появились технологии, которые впоследствии привели к их созданию.

Что такое робот в вашем понимании?

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

Давайте кратко рассмотрим историю материальных роботов, а потом перейдем к самому интересному — как создать искусственный разум.

Были и выдумки

Истории о механических роботах с древних времен присутствуют во всемирной истории. В трактате «Ле-цзы» описывается человекообразный робот, созданный в Китае в III в. мастером Яньши для чжоуского царя Му. Это была полноразмерная фигура человека, сделанная из кожи, дерева и искусственных органов. В мифологии Древнего Крита есть персонаж по имени Талос — бронзовый витязь, который охранял остров, подаренный Европе, от пиратов. А в еврейских преданиях рассказывается о големах — глиняных великанах, которые оживают и выполняют указания по записке, вложенной им в рот.

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

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

Сегодня у нас дома помимо стиральных машин есть и другие роботы. Возможно, у кого-то из ваших знакомых есть робот-пылесос, который убирает дом в отсутствие хозяев, робот-газонокосильщик или автомобиль, который умеет парковаться. Современные самолеты оснащены автопилотом и умеют взлетать и приземляться самостоятельно. Если вы когда-нибудь летели в отпуск и в точке назначения был сильный туман, скорее всего, командир доверил посадку автопилоту. Почему? Потому что так безопаснее. Подобным образом беспилотные автомобили обычно безопаснее автомобилей, управляемых водителем-человеком. Так роботы начинают входить в нашу жизнь, и они достаточно «умны», чтобы научиться делать работу лучше нас, демонстрируя более мощный искусственный интеллект (ИИ).