Глава 6
Бесконечная оптимизация: безграничный потенциал алгоритмов – от эволюции до электронной коммерции
«Через сто метров поверните направо… Поверните направо», – инструктировал бесплотный голос спутникового навигатора. Роберто Фархат, только учившийся водить машину, но уже взявший с собой в поездку жену и двух детей, так и поступил. Всего несколько минут назад он сменил за рулем свою жену – опытного водителя с 15-летним стажем. Когда он свернул с шоссе А6, двухтонный Audi, двигавшийся по встречной полосе, въехал в пассажирскую дверь машины Фархата со скоростью 45 миль в час. Уделяя пристальное внимание спутниковому навигатору, Фархат пропустил дорожные знаки, запрещавшие правый поворот. Сам он остался невредим. А вот его четырехлетней дочери Амелии не повезло. Она умерла в больнице три часа спустя.
Мы уже привыкли полагаться на гаджеты вроде спутниковых навигаторов, которые призваны облегчить нашу перегруженную стрессами и заботами жизнь. Определяя кратчайший маршрут из пункта А в пункт Б, спутниковые навигационные системы решают сложную задачу, что можно сделать единственным способом – через алгоритмический расчет по требованию. Удержать в памяти все возможные маршруты между двумя удаленными точками – слишком сложная задача для небольшого устройства. Точек, между которыми может потребоваться проложить маршрут, огромное количество, что увеличивает сложность задачи в астрономическом масштабе. Учитывая уровень сложности, впечатляет, что алгоритмы спутниковой навигации очень редко ошибаются. Но когда они делают ошибки, те порой оказываются катастрофическими.
Алгоритм – последовательность инструкций, точно описывающих порядок действий для решения конкретной задачи. Задачей может быть что угодно – от организации музыкальной коллекции до приготовления пищи. Самые ранние записанные алгоритмы, однако, носили строго математический характер. У древних египтян был простой алгоритм перемножения двух чисел, а вавилоняне имели правила вычисления квадратных корней. В III веке до нашей эры древнегреческий математик Эратосфен изобрел свое «решето» – простой алгоритм определения простых чисел в числовом ряду, а Архимед применил метод исчерпывания для вычисления последовательности цифр в числе π.
В Европе накануне эпохи Просвещения развитие навыков механической обработки позволило физически воплотить алгоритмы в таких инструментах, как часы и, позднее, зубчатые вычислители. К середине XIX века мастерство достигло такой степени, что эрудит Чарльз Бэббидж смог построить первый механический компьютер, для которого первопроходец математики Ада Лавлейс написала первые компьютерные программы. В принципе, именно Ада первой поняла, что изобретение Бэббиджа имеет прикладное значение, выходящее далеко за рамки чисто математических вычислений, для которых его вычислитель был изначально разработан: что такие объекты, как ноты или, что, возможно, еще важнее, буквы можно описывать в виде кода и манипулировать ими с помощью машины. Сначала электромеханические, а затем и чисто электрические компьютеры использовались союзниками во время Второй мировой войны для алгоритмической расшифровки немецких шифров. Хотя в принципе эти алгоритмы можно было исполнять вручную, прототипы компьютеров того времени уже делали это со скоростью и точностью, недостижимой для людей – сколько бы тех ни было.
Все более сложные алгоритмы, которыми сейчас руководствуются компьютеры, стали неотъемлемой частью нашей повседневности – от ввода запроса в поисковую систему или фотографирования на телефон до компьютерных игр или вопроса о погоде у персонального цифрового ассистента. Мы уже не довольствуемся многими прежними решениями: мы хотим, чтобы поисковая система выводила наиболее релевантные ответы на наши вопросы, а не только первый, который она находит; мы хотим знать точно, будет ли дождь в пять вечера, чтобы определиться – брать ли с собой на работу плащ; мы хотим, чтобы спутниковая навигация вела нас из точки A в точку Б по самому быстрому маршруту, а не по первому попавшемуся. Примечательно, что в большинстве определений алгоритма (списка инструкций для выполнения задачи) не упоминаются входные и выходные данные, которые обеспечивают соответствие алгоритмов задаче. Так, для рецепта входными данными будут ингредиенты, а выходными – готовое блюдо, которое вы подаете на стол. Для спутниковой навигации входные данные – это начальная и конечная точки, которые вы указываете на карте, хранящейся в памяти прибора. Выходные – маршрут, который он вам предлагает. Без этих привязок к реальному миру алгоритмы являются просто абстрактными наборами правил. Когда сбой алгоритма попадает в новостные ленты, в большинстве случаев этот сбой вызван либо погрешностью при вводе данных, либо неожиданными данными на выходе, но не ошибкой в самих правилах.
В этой главе мы познакомимся с математикой, стоящей за неумолимой оптимизацией алгоритмов в нашей повседневной жизни: от принципов выдачи ответов на поисковые запросы в Google до историй, навязываемых нам на Facebook. Мы покажем обманчиво простые алгоритмы, которые решают сложные задачи и на которые опираются современные технологические гиганты: от навигационной системы Google Maps до маршрутов доставки Amazon. Но мы не будем ограничиваться компьютеризированным миром современных технологий – мы предложим вам некоторые «подручные» алгоритмы оптимизации, с помощью которых можно занять лучшее место в поезде или выбрать самую короткую очередь в супермаркете.
Хотя некоторые алгоритмы могут выполнять задачи невообразимой сложности, порой они бывают, мягко говоря, недостаточно эффективными. К несчастию для семейства Фархат, устаревшие карты, «зашитые» в навигатор, заставляли его выбирать неверный маршрут. В самих правилах поиска маршрута ошибки не было, и будь карта актуальной, несчастный случай, скорее всего, никогда бы не произошел. Их история иллюстрирует могущество современных алгоритмов. Этих невероятных инструментов, пронизывающих и упрощающих многие аспекты нашей повседневной жизни, не стоит бояться. В то же время к ним нужно относиться с должным почтением и держать их «входы и выходы» под пристальным наблюдением. Однако человеческий контроль чреват цензурой и предвзятостью. Но даже если жестко ограничить ручной контроль в погоне за чистой объективностью, можно столкнуться со скрытыми, зашифрованными в самом алгоритме предрассудками – отпечатками пристрастий его создателя. Независимо от того, насколько полезными могут быть алгоритмы, не стоит слепо верить в их непогрешимость: некоторое понимание принципов их работы может сохранить время, деньги и даже жизнь.
