Алгоритмы для жизни: Простые способы принимать верные решения (Гриффитс, Кристиан) - страница 158

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

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

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

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

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

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