Непредсказуемость может помочь специалистам по информатике решать задачи, которые в противном случае были бы неразрешимы. Комментарий Сохранить статью Прочитать позже
Когда вариантов много, случайный выбор может оказаться на удивление плодотворным.
Введение
С самых первых дней развития информатики — области, известной своим методичным подходом к решению проблем — случайность играла важную роль. Первая программа, запущенная на первом в мире универсальном электронном компьютере, использовала случайность для моделирования ядерных процессов. Аналогичные подходы с тех пор применялись в астрофизике, климатологии и экономике. Во всех этих случаях подстановка случайных чисел на определенных этапах алгоритма помогает исследователям учитывать неопределенность в отношении множества возможных вариантов развития сложных процессов.
Однако добавление случайности в алгоритм также может помочь вычислить правильный ответ на однозначные вопросы типа «верно/неверно». «Вы просто говорите: „Хорошо, давайте я сдамся, давайте я не буду пытаться, давайте я просто выберу что-нибудь наугад“», — говорит Эрик Блейс, специалист по информатике из Университета Ватерлоо. «Для слишком многих задач это оказывается успешным подходом».
Допустим, вы хотите определить, является ли данное число простым (делится только на 1 и на себя) или составным (делится также на другие целые числа). Вы могли бы просто попытаться разделить его на все возможные делители, но для больших чисел этот «грубый метод» и другие алгоритмы разложения на множители невероятно медленны. А если число окажется составным, алгоритмы разложения на множители сообщат вам значения его делителей — больше информации, чем вы запрашивали. Если вас интересует только «простота» числа, существует ли более эффективный алгоритм?
Да, это возможно, если использовать случайность. Основная идея восходит к результату французского математика XVII века Пьера де Ферма, известному как его «малая теорема». Ферма рассмотрел два целых числа — назовем их N и x. Он доказал, что если N — простое число, то xN − x всегда кратно N, независимо от значения x. Эквивалентно, если xN − x не кратно N, то N не может быть простым числом. Но обратное утверждение не всегда верно: если xN − x кратно N, то N обычно, но не всегда, является простым числом.
Чтобы превратить небольшую теорему Ферма в проверку на простоту, просто возьмите интересующее вас число N, выберите случайным образом x и подставьте два числа в уравнение xN − x. Если результат не кратен N, то всё готово: вы точно знаете, что N — составное число. Если результат кратен N, то N, вероятно, простое число. Теперь выберите другое случайное x и попробуйте снова. В большинстве случаев, после нескольких десятков попыток, вы можете с почти полной уверенностью заключить, что N — простое число. «Вы делаете это небольшое количество раз, — сказал Блейс, — и каким-то образом теперь вероятность ошибки меньше, чем вероятность столкновения астероида с Землёй в промежутке между моментом, когда вы посмотрите на ответ».
Первые проверки на простоту чисел с использованием рандомизированных алгоритмов (основанных на уточнениях малой теоремы Ферма) положили начало новой эре. Оказалось, что решать одну задачу за другой гораздо проще с помощью случайных алгоритмов, чем с помощью неслучайных, или детерминированных, алгоритмов. Ключевым моментом стало переформулирование каждой задачи как задачи, которую можно быстро решить, имея подходящее значение для некоторого числа x, а затем доказательство того, что подойдет практически любое x. Решение работает, даже несмотря на то, что исследователи понятия не имеют, как определить, является ли тот или иной конкретный выбор хорошим. Математики шутят, что эта необычная задача сродни поиску сена в стоге сена.
Однако эти успехи заставили исследователей задуматься, почему случайность должна помогать в решении таких задач, как проверка на простоту чисел, которая заключается в поиске скрытых, неслучайных закономерностей. «В этом есть что-то парадоксальное», — сказал Рахул Сантанам, специалист по информатике из Оксфордского университета. «Чистая случайность помогает вам понять структуру, которая решает проблему».
В 1994 году учёные-программисты Ноам Нисан и Ави Вигдерсон помогли разрешить эту путаницу, продемонстрировав, что случайность, хотя и полезна, вероятно, не является необходимой. Они доказали, что должно выполняться одно из двух условий: либо все задачи, которые можно эффективно решить с помощью случайности, также имеют быстрые детерминированные алгоритмы, либо многие заведомо сложные задачи на самом деле просты. Учёные-программисты считают вторую возможность крайне маловероятной.
На самом деле, специалистам по информатике часто проще разработать детерминированный алгоритм, начав с рандомизированной версии, а затем «де-рандомизировав» её. «Как только у меня есть готовый алгоритм, я внезапно вижу очень очевидный способ сделать его детерминированным», — говорит Эли Апфал, специалист по информатике из Университета Брауна. «Но если бы я не рассматривал это с точки зрения рандомизации как вероятностный вопрос, я бы, вероятно, и не подумал об этом».
Спустя почти 30 лет после знакового доказательства Нисана и Вигдерсона рандомизированные алгоритмы остаются такими же популярными, как и прежде, потому что дерандомизация может быть сложной задачей, а детерминированные алгоритмы часто эффективны только в принципе. Лишь в 2002 году три исследователя нашли способ дерандомизировать проверку простоты чисел, и на практике их алгоритм намного медленнее, чем лучшие рандомизированные алгоритмы. Для других задач трудно даже понять, с чего начать — самый известный алгоритм имеет проблему «курицы и яйца», которую можно избежать только с помощью случайности.
Это относится и к недавнему прорыву в теории графов. В прошлом году три учёных-программиста разработали быстрый алгоритм для поиска кратчайшего пути через граф — сеть узлов, соединённых отрезками, — который работает даже тогда, когда некоторые отрезки уменьшают общую длину пути, а не увеличивают её. Их алгоритм включал преобразование графа в более простой путём удаления определённых отрезков, решение задачи для упрощённого графа, а затем учёт удалённых отрезков. Они смогли доказать, что алгоритм будет работать быстро, если ни один кратчайший путь не проходит через слишком много удалённых отрезков — в противном случае последний шаг займёт слишком много времени.
Но как вообще решить, какие сегменты удалять? Найти идеальный набор сегментов детерминированным образом не просто сложно — это невозможно. Набор зависит от того, какие пути являются кратчайшими, — именно эту проблему и пытались решить три исследователя. Но даже несмотря на то, что им не удалось найти лучший набор сегментов для удаления, они смогли доказать, что большинство случайных выборов будут довольно удачными, и этого было достаточно, чтобы разорвать самореферентный цикл. В редких случаях, когда алгоритм делает неудачный выбор и застревает на последнем шаге, они могли просто остановить его и запустить заново.
«Случайность — это, по сути, способ гарантировать истинность чего-либо относительно оптимального решения, не зная самого оптимального решения», — сказал Аарон Бернштейн, один из авторов нового алгоритма.
Случайность нашла бесчисленное множество других применений в информатике, от криптографии до теории игр и машинного обучения. Скорее всего, она останется с нами надолго.
Источник: www.quantamagazine.org
