Как я считал время прибытия методом Монте-Карло

Одной из самых захватывающих вещей в восьмидесятые было программное моделирование для решения каких-нибудь сложных аналитических проблем и одной из самых используемых техник был метод Монте-Карло. Заключается он в том, что запускает моделирование большое количество раз для получения все более и более достоверного результата.

Несмотря на то, что PHP не является научным языком и редко используется в исследовательских целях, метод Монте-Карло легко может быть реализован и на нём. И в данной статье я покажу как это сделать.

Задача из реальной жизни

Пару дней назад у меня должна быть встреча в 9 часов утра, за 100 миль от моего дома. В 6.30 утра я проснулся, оделся и пока я завтракал, я начал прикидывать в блокноте ближайшие пару часов. Я, как обычно, хотел приехать вовремя, поэтому я начал набрасывать маршрут: выезд из города, проселочная дорога, затем по штату на север, на восток, местная дорога на восток, проехать город, затем на снова на север и прибытие в город. Все это выглядело как-то так:

Моя жена заполнила бак прошлым вечером и я спокойно мог ехать по проселочной дороге. Шины, казалось, были в порядке, когда я смотрел на них, но мысль о том, делать или нет остановку на 10 минут, чтобы проверить их давление, не давала мне покоя. Ведь если я остановлюсь и проверю их, то я буду уверен в их давлении, так как сейчас в нем не был уверен, да и давление в шинах может повлиять на мое движение и скорость…

Я могу выезжать раньше, например, в 6.40, но тогда моей жене придется самой отводить дочь в школу, вместо того чтобы прямиком идти на работу. Если я подожду еще 10 минут, то я могу быть у школы как раз в тот момент, когда они только открывают свои двери, тем самым избавив мою жену от неудобств, тем более что школа по пути к выезду из города и это не сильно меня задерживало.

Я вернулся к тому, что я рисовал и добавил следующее:

Выпивая вторую чашку кофе, я встал у окна. Чистое утреннее небо, легкий утренний ветерок подтверждали хороший прогноз на моем смартфоне и я подумал, что поездка в этот раз будет быстрой. Заканчивая свое планирование, я нарисовал примерное время для каждого этапа, которые я нарисовал ранее:

Ожидаемое время поездки было 115 минут (1 час и 55 минут), если я смогу двигаться без лишних остановок. Я ожидал приехать в 8.35, если поеду сразу, или же в 8.55, если придется захватить с собой дочь, чтобы отправить ее в школу и заодно проверить шины.

Но любое планирование перестает быть идеальным после того, как столкнется с реальностью! По каким-то непонятным причинам, многие родители решают оставить своих детей в школе раньше, чем обычно, поэтому я потерял больше 5 минут, по сравнению с тем, что я планировал для своей быстрой поездки. Поняв, что я немного опаздываю, я решил не проверять давление в шинах и ехать сразу.

Я добрался до выезда из города на 5 минут раньше, чем я планировал в самом плохом раскладе дел и все шло хорошо ровно до тех пор, пока где-то между точками B и C в моем плане я не наткнулся на туман, сильно повлиявший на видимость на дороге. Туман снизил мою среднюю скорость? да еще и мешал обгонять медленные, но длинные грузовики. Городской поток в городе я преодолел намного легче, чем обычно и это не заняло больше 10 минут. Через несколько миль на южной дороге туман снизился и я мог спокойно ехать на разрешенной скорости. Но когда я приближался к моей цели, я понял, что впереди идут дорожные работы и это опять отнимет у меня запланированное время. В общем и целом я потратил еще 10 лишних минут на мое путешествие и в конце-концов я опоздал.

Моделируем путешествие

Я понимаю, что большая часть работы с PHP направлена на всякие там интернет-магазины и другие вебсайты. Но PHP может быть прекрасным инструментом для научных исследований, поскольку ему легко обучить непрофессиональных программистов, таких как инженеры и ученые, в отличии от моего любимого Python.

Напишем небольшой код, который поможет мне понять насколько раньше или позже я смогу прибыть на встречу, если пара этапов моего путешествия немного отойдут от намеченного пути. Для начала, можно описать наш путь как он есть:

<?php  class MyTrip  {      protected $departureTime;      protected $meetingTime;      protected $travelTimes;        public function __construct() {          $this->setDepartureTime('0640');          $this->setMeetingTime('0900');            // время потраченное на проезд между этапами         $this->setTravelTimes(array(              'AB' => 17,              'BC' => 17,              'CD' => 36,              'DE' => 9,              'EF' => 15,              'FG' => 15,              'GH' => 6          ));      }        // для простоты переведем время в минуты     protected static function convertToMinutes($timeStr) {          return substr($timeStr, 0, 2) * 60 +             substr($timeStr, 2, 2);      }        public function setDepartureTime($timeStr) {          $this->departureTime = self::convertToMinutes($timeStr);      }        public function setMeetingTime($timeStr) {          $this->meetingTime = self::convertToMinutes($timeStr);      }        public function setTravelTimes(array $travelTimes) {          $this->travelTimes = $travelTimes;      }        public checkPlan($stopAtSchool = true, $checkTires = true) {         // ...     } } 

План должен быть осуществимым и подходящим критерием для определения этого будет таким, что сумма всех времен плюс раннее время выезда должна быть меньше или равна времени, на которое назначена моя встреча. Собственно это и определяет метод checkPlan():

<?php public checkPlan($stopAtSchool = true, $checkTires = true) {     // посчитаем сумму проезда между всеми этапами     $travelTime = array_sum($this->travelTimes);       // добавим задержку, если мне придется отвозить дочь в школу     $schoolDelay = ($stopAtSchool) ? 10 : 0;       // задержка на проверку давления в шинах     $tiresDelay = ($checkTires) ? 10 : 0;       // находим ожидаемое время приезда     $meetingArriveTime = $this->departureTime + $travelTime +         $schoolDelay + $tiresDelay;       // доеду ли я вовремя?     $arriveOnTime = $meetingArriveTime <= $this->meetingTime;       return array($meetingArriveTime, $this->meetingTime,         $arriveOnTime); } 

Все, нам осталось только сделать экземпляр этого класса и проверить:

<?php $trip = new MyTrip(); print_r($trip->checkPlan()); 

С учетом настроек по умолчанию, вывод будет таким:

Array (     [0] => 535     [1] => 540     [2] => 1 ) 

Я должен прибыть в 535 минут, а встреча назначена на 540 минут. Если перевести на часы, то я прибуду в 8.45, раньше запланированного времени на 15 минут.

Но что на счет возможных задержек? Как их предусмотреть и просчитать?

Метод Монте-Карло или добавляем случайности

В самом простом виде мы можем определить некий безопасный зазор для каждого события и сказать что он может случиться на 10% раньше и на 25% позднее заданного времени. Эти зазоры могут быть случайно добавлены к изначальным задержкам (дочь, давление) и времени между этапами умножением каждого фактора на rand(90,125)/100.
Также можно присвоить 50% вероятность к двум решениям — отвезти дочь в школу и проверить шины. Тут снова поможет rand():

$this->checkTires = rand(1, 100) > 50; 

Объединив все это вместе можно определить метод checkPlanRisk() для вычисления решения приеду ли я вовремя или нет, с учетом разных ситуация во время пути:

<?php public function checkPlanRisk() {     // скорректируем время проезда     $travelTime = 0;     foreach ($this->travelTimes as $t) {         $travelTime += $t * rand(90, 125) / 100;     }       // Решение прихватить с собой дочь     $schoolDelay = 0;     if (rand(1, 100) > 50) {         $schoolDelay = 10 * rand(90, 125) / 100;     }           // и для шин     $tiresDelay = 0;     if (rand(1, 100) > 50) {         $tiresDelay = 10 * rand(90, 125) / 100;     }       // вычисление времени прибытия     $meetingArriveTime = $this->departureTime + $travelTime +         $schoolDelay + $tiresDelay;       // вовремя или же нет?     $arriveOnTime = $meetingArriveTime <= $this->meetingTime;       return array($schoolDelay, $tiresDelay, $meetingArriveTime,         $this->meetingTime, $arriveOnTime); } 

Сейчас встает вопрос прибуду ли я вовремя, принимая во внимание все возможные задержи? Метод Монте-Карло позволяет решить этот вопрос запуском большого количества раз данной задачи и вычисляя «уровень доверия» как отношение времени прибытия вовремя к общему количеству запусков задачи.

Если запустить данный достаточное количество раз и записать как часто я прибуду вовремя, то я смогу определить некоторую вероятность того, что я прибуду как планировал.

<?php public function runCheckPlanRisk($numTrials) {     $arriveOnTime = 0;     for ($i = 1; $i <= $numTrials; $i++) {         $result = $this->checkPlanRisk();         if ($result[4]) {             $arriveOnTime++;         }           echo "Попыток: " . $i;         echo " Школа: " . $result[0];         echo " Шины: " . $result[1];         echo " Время в пути: " . $result[2];           if ($result[4]) {             echo " -- Вовремя";         }         else {             echo " -- Опоздание";         }           $confidence = $arriveOnTime / $i;         echo "Уровень доверия: $confidencen";     } } 

Создадим новый экземпляр и сделаем 1000 вычислений друг за другом:

<?php $trip = new MyTrip(); $trip->runCheckPlanRisk(1000); 

После завершения получим прогноз:

Попыток: 1000 Школа: 0 Шины: 11.3 Время в пути: 530.44 -- Вовремя Уровень доверия: 0.716 

При текущих параметрах, как видно, у меня есть шанс в 72% прибыть на встречу вовремя. Конечно, это просто среднее значение, но и оно имеет право на жизнь.

От себя: скорее всего статья не несет абсолютно ничего нового, заголовок немного желтоват, но мне эта статья показалась забавной. Прочитал давно, а вспомнил с появлением статьи на хабре про Монте-Карло. Может кому-нибудь и пригодится. Всех с праздником 🙂