9. Случайность
Когда стоит положиться на волю случая
После стольких лет работы в этой сфере я вынужден признать, что роль случайности в решении многих алгоритмических задач поистине загадочна.
Это работает, это эффективно; но как и почему – загадка.
Майкл Рабин
Случайность представляется нам противоположностью осознанности – своего рода уходом от проблемы. Но это не так. Удивительная и весьма важная роль случайности в компьютерных науках демонстрирует нам, что порой положиться на волю случая – это взвешенный и эффективный шаг в решении ряда сложнейших задач. На самом деле бывают ситуации, когда ничего, кроме этого, не поможет.
В отличие от стандартных детерминированных алгоритмов, которые мы обычно представляем себе как работу компьютера, где каждый последующий шаг одним и тем же образом проистекает из предыдущего, рандомизированный алгоритм использует для решения задачи метод случайного выбора чисел. Последние исследования в области информатики показали, что в некоторых случаях рандомизированные алгоритмы помогают найти ответ на вопрос быстрее, чем всеми признанные детерминированные. И хотя они не всегда гарантируют оптимальные решения, рандомизированные алгоритмы порой удивительно к ним приближаются путем стратегического подбрасывания нескольких монет, в то время как их детерминированные «собратья» лезут из кожи вон.
Примечательно, что в решении некоторых задач рандомизированный подход превосходит даже лучший из детерминированных. Иногда лучшее решение проблемы – положиться на судьбу, а не пытаться заранее продумать ответ.
Но одного лишь знания о том, что случайность может оказаться полезной, недостаточно. Нужно четко понимать, когда можно положиться на случайность, каким образом и в какой степени. Новейшая история развития информатики предлагает ответы на эти вопросы – хотя начиналось все парой столетий раньше.
