Когда метод Монте-Карло должен использоваться?
Например, почему Joel решал использовать метод Монте-Карло для основанного на доказательстве Планирования вместо того, чтобы систематически обработать все пользовательские данные в течение прошлого года?
Предположим, вы хотите оценить некоторую интересующую вас величину. В примере Джоэла «дата отгрузки» - это то, что вы хотите оценить. В большинстве таких ситуаций на наши оценки влияют случайные факторы.
Когда у вас есть случайная величина, вы обычно хотите знать ее среднее значение и стандартное отклонение, чтобы предпринять соответствующие действия. В простых ситуациях вы можете смоделировать величину как стандартное распределение (например, нормальное распределение), для которого существуют аналитические формулы для среднего и стандартного отклонения. Однако существует множество ситуаций, когда аналитических формул не существует. В таких ситуациях вместо аналитического решения для среднего и стандартного отклонения мы прибегаем к моделированию. Идея такова:
Шаг 1: Сгенерируйте факторы, влияющие на интересующее количество, используя соответствующие распределения
Шаг 2: Вычислите интересующее количество
Повторите шаги 1 и 2 много раз и вычислите эмпирическое среднее и стандартное отклонение для что вы хотите узнать.
Вышеупомянутое, безусловно, типичное применение приложения Монте-Карло. См. Ссылку на википедию, предоставленную Джарродом, чтобы узнать о нескольких таких приложениях и некоторых примерах интересных приложений, в которых нет присущей случайности (например, оценка числа Пи).
В Википедии есть хорошая статья о методах моделирования Монте-Карло. Я использовал монте-карло несколько раз - вкратце, методы MC обычно дают точные ответы при попытке спроецировать результаты с использованием наборов выборок, которые в значительной степени случайны, и кто-то обычно использует интуицию, чтобы попытаться угадать тенденцию. К сожалению, попытаться объяснить методы MC довольно сложно, поэтому ознакомьтесь со статьей.
Поскольку оценки обычно довольно широко распределяются при планировании задач программирования, имеет смысл обрабатывать их статистически.
Если мы возьмем проект, который включает сотни задач, ошибки в оценках выровняются, и вы получите распределение, которое показывает вероятность завершения проекта в виде диапазона.
Это также позволяет обойти некоторые серьезные проблемы, такие как буферизация задач и синдром студента, что еще больше искажает результаты.
Методы Монте-Карло обычно используются когда размерность задачи слишком высока для традиционных схем. отличная вводная статья по этому вопросу - The Markov Chain Monte Carlo Revolution Перси Диакониса.