Алгоритмы для жизни: Простые способы принимать верные решения - [84]

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

Консервативный британский журналист Кристофер Букер говорит: «Когда мы предпринимаем действия, которые бессознательно обусловлены принятием желаемого за действительное, на какое-то время может показаться, что все идет хорошо», но только потому, что «эта фантазия никогда не может быть соотнесена с реальностью». Это неизбежно приведет к тому, что он называет многоступенчатой аварией: мечта, разочарование, кошмар, взрыв. Информатика рисует слишком радужную картину. С другой стороны, в качестве метода оптимизации релаксация предлагает нам сознательно принять желаемое за действительное. Возможно, в этом вся разница.

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

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

9. Случайность Когда стоит положиться на волю случая

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

Это работает, это эффективно; но как и почему – загадка.

Майкл Рабин

Случайность представляется нам противоположностью осознанности – своего рода уходом от проблемы. Но это не так. Удивительная и весьма важная роль случайности в компьютерных науках демонстрирует нам, что порой положиться на волю случая – это взвешенный и эффективный шаг в решении ряда сложнейших задач. На самом деле бывают ситуации, когда ничего, кроме этого, не поможет.

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

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

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

Метод выборки

В 1777 году Жорж-Луи Леклерк, граф де Бюффон, представил общественности результаты интересного вероятностного анализа. Если мы бросим иголку на разлинованный лист бумаги, спрашивал он, какова вероятность, что она пересечет одну из линий? В своей работе Бюффон доказал, что если длина иголки короче, чем расстояние между линиями, то ответ будет