Казино и математика
Сегодня сложная тема, но мы объясним её просто и понятно. Разговор пойдёт про алгоритмы и немного про математику.
Методы Монте-Карло — это набор методов в математике для изучения случайных процессов. Случайных — это когда что-то в них происходит непредсказуемым образом, например:
- подбрасываем монетку;
- кидаем кубик;
- опускаем жетоны в ячейки со столбиками;
- ловим элементарные частицы;
- считаем столкновения молекул;
- и что угодно ещё, что происходит полностью случайно и что нельзя предсказать заранее.
Смысл методов Монте-Карло в том, чтобы использовать данные случайных событий, чтобы на их основе получить более-менее точные результаты каких-то других вычислений. Они не будут идеально и математически точными, но их уже будет достаточно, чтобы с ними полноценно работать. Иногда это проще и быстрее, чем считать всё по точным формулам.
Пример такого вычисления — построение маршрута в навигаторе. В исходном виде это задача коммивояжёра, которая требует колоссальных вычислительных ресурсов. Но благодаря приближённым методам с ней справится даже не самый мощный телефон. Один из таких методов — метод Монте-Карло.
Своё название метод получил в честь Монте-Карло — района Монако, где находится много казино с рулеткой, самым доступным источником случайных чисел в начале 20-го века.
В чём идея метода
Если совсем примитивно, то работает так:
Вместо того чтобы строить сложную математическую модель, мы берём простую формулу и пуляем в неё случайные числа. Считаем результат по каждому числу и получаем результат с нужной нам точностью. Чем больше случайных чисел — тем точнее результат.
Вот то же самое немного подробнее:
- Выбираем, что мы хотим найти или посчитать — значение формулы, площадь, объём, распределение материала или что-то ещё.
- Смотрим, как это считается в математике, и находим нужные формулы.
- На основе формул составляем критерий проверки — если случайное значение попало в этот критерий, мы его учитываем как совпавшее число, а если не попало — как не совпавшее.
- Запускаем алгоритм, который выдаёт случайные числа, и проверяем каждое по этому критерию.
- Как наберётся достаточное количество случайных чисел — считаем результат. Обычно это соотношение чисел, которые попали в критерий и которые не попали.
Чем больше будет случайных чисел — тем точнее результат.
Плюс этого метода в том, что нам не нужно запрягать весь математический аппарат для решения задачи — достаточно подставлять числа в формулу и смотреть, получилось верное значение или нет.
Как найти число пи методом Монте-Карло
Для примера покажем классическое использование метода Монте-Карло — найдём число пи. Для этого нам понадобится круг, вписанный в квадрат, причём у круга радиус будет равен 1. Это значит, что сторона квадрата равна 2 — это диаметр (или два радиуса) круга:
В этот квадрат мы будем случайным образом кидать песчинки и смотреть, попадут они в круг или нет (но останутся в границах квадрата). Исходя из этого набора данных мы можем посчитать отношение всех песчинок, которые попали в круг, ко всем песчинкам.
Теперь смотрим на формулы:
- площадь квадрата со стороной 2 равна четырём;
- площадь круга радиусом 1 равна πR² → π×1² = π.
Если мы разделим площадь круга на площадь квадрата, то получим π / 4. Но мы ещё не можем по условию посчитать площадь круга, потому что мы не знаем число π. Вместо этого мы можем разделить количество одних песчинок на другие — в этом и суть метода Монте-Карло.
Это соотношение даст нам результат — π / 4. Получается, что если мы умножим этот результат на 4, то получим число π, причём чем больше песчинок мы кинем, тем точнее будет результат.
Кидать песчинки будем так: в качестве координат попадания X и Y будем брать случайные числа от 0 до 1. Это значит, что все числа попадут только в один квадрант — правый верхний:
Но так как в этом квадранте ровно четверть круга и ровно четверть квадрата, то соотношение промахов и попаданий будет таким же, как если бы мы бросали песчинки в целый круг и целый квадрат.
Чтобы проверить, попадает ли песчинка в круг, используем формулу длины гипотенузы: x² + Y² = 1 (так как гипотенуза — это радиус окружности):
Если длина гипотенузы меньше единицы — точка попадает в круг. В итоге мы посчитаем и общее количество точек, и точек, которые попали в круг. Потом мы разделим одно на другое, умножим результат на 4 и получим приближённое значение числа π.
Программируем поиск числа пи по методу Монте-Карло
Алгоритм на языке Python, читайте комментарии, чтобы лучше разобраться в происходящем:
Где ещё используется метод Монте-Карло
На методах Монте-Карло основано много полезного:
- моделирование облучения твёрдых тел ионами в физике;
- моделирование поведения разреженных газов
- исследования поведения разных тел при столкновении
- алгоритмы оптимизации и нахождения кратчайшего пути решения
- решение сложных интегралов (или когда их очень много)
- предсказание астрономических наблюдений
- поиск в дереве в различных алгоритмах
- алгоритмы работы некоторых функций квантового компьютера
- моделирование состояния приближённой физической среды
Без них изучать современный мир и совершать новые открытия было бы сложнее.
Что дальше
В следующей части поговорим про отжиг — интересное применение метода Монте-Карло, который имитирует физические процессы. Благодаря отжигу мы можем обучать нейросети и решать сложные комбинаторные задачи.