Во всяком случае, это должно нас немного утешить. Если мы сталкиваемся лицом к лицу с задачей, которая кажется нескладной, тернистой, нерешаемой, то мы, вероятно, правы. И наличие компьютера далеко не всегда может помочь.
По крайней мере до тех пор, пока мы не научимся релаксировать.
Существует много способов ослабить проблему, и мы рассмотрели три наиболее важных. Первый из них – вынужденная релаксация – просто убирает некоторые ограничения в целом и достигает прогресса за счет уменьшения строгости задачи, прежде чем возвращается к реальности. Второй – непрерывная релаксация – превращает дискретный или бинарный выбор в бесконечное множество: прежде чем выбрать между холодным чаем и лимонадом, представьте себе напиток Арнольда Палмера
[28], в котором поровну того и другого, и мысленно увеличивайте или уменьшайте эти доли. Третий – Лагранжева релаксация – превращает невозможности в обычные штрафы, обучая нас искусству обходить правила (или вовсе нарушать их и отвечать за последствия). Рок-группа, решающая, какие песни должны войти в альбом, сталкивается с тем, что ученые называют задачей о рюкзаке – головоломкой, в которой требуется решить, какие из множества предметов различной величины и важности можно разместить в заданном объеме. В своей строгой постановке задача о рюкзаке практически неразрешима, но это не должно разочаровывать наших расслабленных рок-звезд. Как показал ряд известных примеров, иногда лучше просто поиграть чуть дольше городского комендантского часа и заплатить связанный с этим штраф, чем подгонять концерт под разрешенный временной интервал. На самом деле, даже если вы не совершили правонарушение, а просто представили себе нарушение, это может оказаться поучительным.
Консервативный британский журналист Кристофер Букер говорит: «Когда мы предпринимаем действия, которые бессознательно обусловлены принятием желаемого за действительное, на какое-то время может показаться, что все идет хорошо», но только потому, что «эта фантазия никогда не может быть соотнесена с реальностью». Это неизбежно приведет к тому, что он называет многоступенчатой аварией: мечта, разочарование, кошмар, взрыв. Информатика рисует слишком радужную картину. С другой стороны, в качестве метода оптимизации релаксация предлагает нам сознательно принять желаемое за действительное. Возможно, в этом вся разница.
Релаксации дают нам ряд преимуществ. С одной стороны, они предлагают нормы качества правильного решения. Если мы заполняем ежедневник планами, представляя себе, что можем каким-то магическим образом за мгновение перенестись через весь город, то немедленно становится ясно, что восемь часовых встреч – это максимум, который мы можем втиснуть в свое расписание на день. Подобное ограничение может оказаться полезным, чтобы скорректировать наши ожидания, прежде чем мы столкнемся с проблемой в полный рост. Во-вторых, релаксации устроены таким образом, что они действительно могут быть соотнесены с реальностью. И это дает нам возможность прийти к решению, двигаясь с другой стороны. Когда метод непрерывной релаксации предлагает нам частичную вакцинацию, мы можем просто вакцинировать каждого, кому досталась половина вакцины или больше, и в конечном итоге прийти к легко вычисляемому решению, которое в худшем случае потребует в два раза больше вакцин, чем в идеале. Вероятно, мы можем жить с этим.
Если только мы не готовы тратить миллиарды лет на борьбу за совершенство каждый раз, как зайдем в тупик, то, встретив сложную задачу, вместо пробуксовки на месте мы должны найти ее более легкую версию и решить сначала ее. При правильном применении метода это будет вовсе не выдавание желаемого за действительное, не фантазии и не ленивые сны наяву. Это один из лучших способов добиться успеха.
9. Случайность
Когда стоит положиться на волю случая
После стольких лет работы в этой сфере я вынужден признать, что роль случайности в решении многих алгоритмических задач поистине загадочна.
Это работает, это эффективно; но как и почему – загадка.
Майкл Рабин
Случайность представляется нам противоположностью осознанности – своего рода уходом от проблемы. Но это не так. Удивительная и весьма важная роль случайности в компьютерных науках демонстрирует нам, что порой положиться на волю случая – это взвешенный и эффективный шаг в решении ряда сложнейших задач. На самом деле бывают ситуации, когда ничего, кроме этого, не поможет.
В отличие от стандартных детерминированных алгоритмов, которые мы обычно представляем себе как работу компьютера, где каждый последующий шаг одним и тем же образом проистекает из предыдущего, рандомизированный алгоритм использует для решения задачи метод случайного выбора чисел. Последние исследования в области информатики показали, что в некоторых случаях рандомизированные алгоритмы помогают найти ответ на вопрос быстрее, чем всеми признанные детерминированные. И хотя они не всегда гарантируют оптимальные решения, рандомизированные алгоритмы порой удивительно к ним приближаются путем стратегического подбрасывания нескольких монет, в то время как их детерминированные «собратья» лезут из кожи вон.
Примечательно, что в решении некоторых задач рандомизированный подход превосходит даже лучший из детерминированных. Иногда лучшее решение проблемы – положиться на судьбу, а не пытаться заранее продумать ответ.
Но одного лишь знания о том, что случайность может оказаться полезной, недостаточно. Нужно четко понимать, когда можно положиться на случайность, каким образом и в какой степени. Новейшая история развития информатики предлагает ответы на эти вопросы – хотя начиналось все парой столетий раньше.
Метод выборки
В 1777 году Жорж-Луи Леклерк, граф де Бюффон, представил общественности результаты интересного вероятностного анализа. Если мы бросим иголку на разлинованный лист бумаги, спрашивал он, какова вероятность, что она пересечет одну из линий? В своей работе Бюффон доказал, что если длина иголки короче, чем расстояние между линиями, то ответ будет
умноженное на длину иглы, разделенную на длину расстояния. Бюффону было достаточно просто вывести эту формулу. Но в 1812 году Пьер-Симон Лаплас, один из героев главы 6, выяснил, что есть и другой подход: вычислить число π можно, просто бросая иглы на бумагу.
Подход Лапласа имеет глубокую подоплеку: когда мы хотим знать что-то о комплексной величине, мы можем оценить ее значение путем выборки из нее. Это именно тот метод расчетов, который демонстрируется в его работе над правилом Байеса. В самом деле, несколько человек в точности воспроизвели предложенный Лапласом эксперимент, подтвердив, что этим способом рассчитать значение числа π возможно – хотя и не слишком эффективно
[29].
