Надеюсь что тема будет интересна людям которые знакомы с обычными алгоритмами и хотят узнать об упомянутых выше в общих чертах, что бы иметь представление о чем речь. Постараюсь избегать вычеслений и излагать на интуитивном уровне. И хотя интуиция в теории вероятностей часто подводит, давайте все же попробуем.
Рандомизированые Алгоритмы от обычных отличаются тем, что используют случайность (source of randomness) в своей работе. В первую очередь нам надо четко различать слова «случайный» (random) и «произвольный» (arbitrary). Если в первом случае, мы делаем равновероятностный выбор, то во втором — не важно какой выбор мы делаем.
Пример 1: Нам нужно выбирать число от 1 до 10.
Если выбор «случайный», то каждый раз мы выбираем число с вероятностью 1/10. т. е. Сделав выбор N раз, каждое число будет выбрано примерно N/10 раз.
Если выбор «произвольный», то выбирать только число «5», это тоже хорошо. Иными словами, «произвольный» выбор хорош там, где выбор не влияет на результат. Скажем DFS проход по дереву позволяет «произвольный» выбор потомка.
Второй момент, который следует оговорить, это то, что вероятность ошибки/скорость вычеслений не должна зависить от инпута, а только от того случайного числа, которое мы выбираем каждый раз заново на каждом запуске, в дополнение к входным данным.
Чем же они хороши, эти рандомизированые алгоритмы?
- Зачастую, они заметно проще. (см. пример 4)
- Позволяют решать задачи, не разрешимые классическими. (см. пример 2)
- Позволяют контролировать размер ошибки.
- Наверное есть что-то еще.
Монте-Карло
Наверное, самым известным алгоритмом такого рода является метод Монте-Карло. Идея метода заключается в том, что бы получить результат близкий к верному с хорошей вероятностью.
Пример 2.
Нам нужно написать профайлер, можно в каждую функцию втюхать таймер и смотреть сколько времени занимает ее вызов, а можно воспользоваться методом Монте-Карло. Время от времени останавливать процесс и смотреть на стэк вызовов (call stack). Конечно, ответ мы получим приблизительный, но если замерять будем достаточно часто и достаточно много, то отклонение от истины не будет большим.
Лас-Вегас
Другая известная парадигма – метод Лас-Вегас (наверное по аналогии с предидущим методом назвали). Суть его заключается в том, что алгоритм возвращает правильный результат, но за неопределенное время. Дальше включается теория вероятности, которая доказывает что скорее всего это время будет небольшим.
Пример 3.
У нас есть монета на которой решка выпадает с вероятностью 1/3, а орел, соответственно, с вероятностью 2/3. Нам нужна монета с вероятностями ½ на каждую сторону.
Подбросим монету два раза.
- Если выпали “орел, решка” — скажем орел.
- Если выпали “решка, орел” — скажем решка.
- Если выпали два орла или две решки, повторим опыт.
Вероятность увидить два орла или две решки 1/9+4/9 = 5/9. Значит, вероятность что наш алгоритм не остановится за (скажем) 10 ходов меньше 0.003.
Основной закон органической химии
Иногда, у нас есть алгоритм который показывает хорошие результаты на случайных данных и плохие на упорядоченых (например бинарное несбалансированое дерево). Наша задача, из существующих данных, сделать однородно распределенные данные, и тут нам поможет «основной закон органической химии». Применительно к нашему вопросу он звучит так:
Пусть А случайный бинарный вектор так что каждый бит равен 1 с вероятностью одна вторая.
Тогда если взять «произвольный» бинарный вектор B и посчитать (A xor B), то вероятность каждого бита в результате, тоже будет одна вторая. Иными словами (A xor B) «случайный» вектор.
Пример 4. Желаем хранить в обычном дереве двоичные строки длинны k. Для этого генерируем случайную строку нужной длины, и делаем с ней xor всем данным с которые кладем или ищем в дереве.
Как бороться с ошибкой (Amplification)
Для простоты, предположим что наша задача может иметь только два ответа: «да» или «нет».
По большому счету, есть 2 варианта ошибки. Одностороння и двух сторонняя.
В первом случае, алгоритм ошибается только с ответами «да» или только с «нет».
Пример: Наш алгоритм проверяет число на простоту. Если оно простое, он говорит «да».
Если число составное, он говорит «нет» с вероятностью ½.
Запустим алгоритм N раз и скажем «число составное» если, хотя бы раз, алгоритм сказал «нет».
Как вы видите, если изначально на составных числах вероятность ошибки была ½, то после N запусков она 2^(-N).
Во втором случае, наш алгоритм ошибается не зависимо от того, какой же правильный ответ.
Например он верно определяет простоту числа с вероятностью 2/3. Тогда запустим его N раз, и выбирем тот ответ, который встретился чаще. Теорема Чернова подтвердит нам, что вероятность ошибки убывает экспоненциально от N.
В заключение
Если перед вами стоит муторная задача с замысловатым алгоритмом для ее решения, то может стоит рассмотреть вариант с рандомизацией? И багов меньше, и нервы крепче.
Автор: lagranzh
