Нет, я никогда не был в Монте-Карло! Но «метод Монте-Карло» - это романтическое название метода случайных испытаний, которое мне очень нравится. Данный метод позволяет, как бы шутя получать решения сложных задач.
А дело было так. В 1998 году мне довелось вести практикум по нелинейному программированию.
Я взял методичку. Там были приведены задачи на нахождение экстремумов функций четырех переменных. Предлагалось запрограммировать(написать коды) для решения задач градиентным методом, методом покоординатного спуска и проч. Студенты тут же выудили из инета подходящие проги, и задачи практикума «как бы» уже были решены. Но требовалось провести еще многочасовые аудиторные занятия! Сверхбыстрое освобождение студентов, и себя, любимого, от нагрузки «старшие товарищи» явно бы не поняли!
Возникла задача: чем же занять студенческие ручоночки шаловливые? И я предложил провести вычислительный эксперимент. А именно попробовать порешать все задачки методом случайных испытаний. Причем, не вдаваясь в тонкости, а прямо в лоб. Так же тупо, как муха пытается вылететь из комнаты, не понимая, где застекленное окно, а где настежь открытая дверь.
Сказано – сделано. Текст проги на турбопаскале занял около полстраницы двенадцатым кеглем.
И студенты стали эту прогу гонять на всех задачах. И что бы выдумали? Все задачи были решены с требуемой в методичке точностью! Но, разумеется, машинное время потребовалось много большее, чем даже у покоординатного спуска. Эксперимент проводился на откровенно устаревших в ту пору персоналках IBM AT286. (Уже Пентиум 2 был не редкостью.)
В тех случаях, когда метод покоординатного спуска решал задачу за доли секунды, «метод Монте-Карло» мог потребовать и пары минут.
Но выигрыш в затратах времени на программирование и отладку программы был неоспорим.
Войдя в раж, мы методом случайного поиска пробовали решать и задачи линейного программирования. Получалось! Однако проигрыш во времени по сравнению с симплекс-методом был колоссальный. Но тут время практикума закончилось, и я к этой теме с другими студентами не возвращался. Кстати, упомянутые студенты были отнюдь не математики, а строители.
Нет слов, результат им очень понравился. Одной прогой на пол-листа «рубить вообще все»!
Позднее я узнал про еще один интересный метод с интригующим названием «кенгуру с мышью в сумке». Суть его очень проста. Большие шаги делает метод случайного поиска. Когда он находит окрестность экстремума, в дело включается «мышь» – регулярный метод, допустим, градиентный, который находит точное значение экстремума. Метод особенно хорош для мультимодальных функций.
Однако колоссальное преимущество перед регулярными методами «Монте_Карло» имеет для задач высокой размерности, когда все регулярные, как один, тормозят очень сильно. Почему так?
Но об этом уже в другой статье.
