1) Идеальное расписание поездов по линии АВ -- следущее:
Departure from "A" -- 00:00 (midnight), arrival to "B": 03:00;
Departure from "B" -- 06:00, arrival to "A": 09:00;
Departure from "A" -- 12:00 (noon), arrival to "B": 15:00;
Departure from "B" -- 18:00, arrival to "A": 21:00.
Дальше цикл повторяется.
2) Идеальное расписание поездов по линии CD -- следущее:
Departure from "C" -- 00:45, arrival to "B": 03:45;
Departure from "D" -- 06:45, arrival to "A": 09:45;
Departure from "C" -- 12:45, arrival to "B": 15:45;
Departure from "D" -- 18:45, arrival to "A": 21:45.
Дальше цикл повторяется.
Точка "0" -- не станция, просто перекресток. Без семафора!
Проектировщики полагали, что поезда никогда не столкнуться, поскольку их время отправления по разным линиям специально максимально разнесено (на 1/2 времени в пути), т.е., зазор прохождения точки "О" -- 45 минут!
К сожалению, идеального ничего не бывает.
Поэтому поезда уходят чуть раньше или чуть позже времени по расписанию.
А именно, каждое время время оптправления по каждой станции подчиняется закону нормального распределения. При этом среднее значение (μ) = время по расписанию, а сигма (σ) = 6 минут (1/10 часа)
Скорость в пути считать неизменной и постоянной, причем именно такой, что время в пути всегда ровно 3 часа (без разброса).
Для определенности пусть будет AB=CD=300 км, а скорость -- 100 км в час.
Поезда -- не материальные точки. (Материальные точки не могут столкнуться). Точками мы их считаем только для удобства расчетов.
Поэтому столкновением считается событие, когда разница во времени между прохождением точки О двух точечных поездов меньше или равна 36 секунд (1/100 часа)
Из-за случайностей времени отправления, поезда рано или поздно столкнуться обязательно. (Ну, это примерно как монета может 100 раз подряд упасть орлом, хотя ждать этого события придется в среднем очень долго).
ЗАДАЧА:
1) Выяснить, как скоро математическое ожидание вероятности столкновения поездов достигнет 50%.
Бонусный вопрос:
Нарисуйте вообще график вероятности столкновения поездов в зависимости от времени (они ходят ежедневно неограничено долго). График будет примерно такой:
Здравствуйте, Lepsik, Вы писали:
L>Имеется "сеть" железных дорог из двух линий:
L>Image: train_problem.png
L>1) Идеальное расписание поездов по линии АВ -- следущее:
L>Departure from "A" -- 00:00 (midnight), arrival to "B": 03:00; L>Departure from "B" -- 06:00, arrival to "A": 09:00; L>Departure from "A" -- 12:00 (noon), arrival to "B": 15:00; L>Departure from "B" -- 18:00, arrival to "A": 21:00.
L>Дальше цикл повторяется.
L>2) Идеальное расписание поездов по линии CD -- следущее:
L>Departure from "C" -- 00:45, arrival to "B": 03:45; L>Departure from "D" -- 06:45, arrival to "A": 09:45; L>Departure from "C" -- 12:45, arrival to "B": 15:45; L>Departure from "D" -- 18:45, arrival to "A": 21:45.
L>Дальше цикл повторяется.
L>Точка "0" -- не станция, просто перекресток. Без семафора!
L>Проектировщики полагали, что поезда никогда не столкнуться, поскольку их время отправления по разным линиям специально максимально разнесено (на 1/2 времени в пути), т.е., зазор прохождения точки "О" -- 45 минут!
Где-то в цифрах ошибка.
Учитывая что поезда движутся по 3 часа, и по 3 часа стоят на станциях, можно добиться 3-х часового зазора между прохождениями.
L>К сожалению, идеального ничего не бывает.
L>Поэтому поезда уходят чуть раньше или чуть позже времени по расписанию.
L>А именно, каждое время время оптправления по каждой станции подчиняется закону нормального распределения. При этом среднее значение (μ) = время по расписанию, а сигма (σ) = 6 минут (1/10 часа)
L>Скорость в пути считать неизменной и постоянной, причем именно такой, что время в пути всегда ровно 3 часа (без разброса).
L>Для определенности пусть будет AB=CD=300 км, а скорость -- 100 км в час.
L>Поезда -- не материальные точки. (Материальные точки не могут столкнуться). Точками мы их считаем только для удобства расчетов.
L>Поэтому столкновением считается событие, когда разница во времени между прохождением точки О двух точечных поездов меньше или равна 36 секунд (1/100 часа)
L>Из-за случайностей времени отправления, поезда рано или поздно столкнуться обязательно. (Ну, это примерно как монета может 100 раз подряд упасть орлом, хотя ждать этого события придется в среднем очень долго).
L>ЗАДАЧА:
L>1) Выяснить, как скоро математическое ожидание вероятности столкновения поездов достигнет 50%.
L>Бонусный вопрос:
L>Нарисуйте вообще график вероятности столкновения поездов в зависимости от времени (они ходят ежедневно неограничено долго). График будет примерно такой:
L>Image: train_cumulative_collision_probability.png
Как-то слишком просто для собеседования...
Возможно, хотели поговорить о неточностях формулировки, лил получить качественный ответ "сходу".
Здравствуйте, Lepsik, Вы писали:
L>А именно, каждое время время оптправления по каждой станции подчиняется закону нормального распределения. При этом среднее значение (μ) = время по расписанию, а сигма (σ) = 6 минут (1/10 часа)
L>Скорость в пути считать неизменной и постоянной, причем именно такой, что время в пути всегда ровно 3 часа (без разброса).
L>ЗАДАЧА:
L>1) Выяснить, как скоро математическое ожидание вероятности столкновения поездов достигнет 50%.
L>Бонусный вопрос:
L>Нарисуйте вообще график вероятности столкновения поездов в зависимости от времени (они ходят ежедневно неограничено долго). График будет примерно такой:
Я что-то не понял. Если у нас есть нормальное распределение, и μ = время по расписанию, то почему у нас вероятность столкновения будет зависить от времени?
Итак, четыре раза в день, вертикальный поезд проезжает перекрёсток в момент "условный ноль" ±разброс, а "горизонтальный" — в момент "условный ноль" + 45 минут ±разброс.
Ситуацией, когда любой поезд опоздал на целый период, наверно, можно пренебречь. А опередить на целый период в принципе невозможно.
Поэтому надо искать для каждого такого периода отдельно.
Вероятность отклонения от расписания — p(t) и q(t) = p(45'+t) — горбушки нормального распределения.
Если вертикальный поезд отклонился на T, то он столкнётся с вероятностью, равной r(T) = INT [t=-6"..+6"] q(T+t)
С учётом вероятности отклонения вертикального поезда, получаем, что столкновение в момент t имеет вероятность s(t) = p(t)r(t).
Ну и нужно посчитать интеграл P = INT [t=-3h..+3h] s(t). Это вероятность столкновения в одном периоде.
Извини, кучу экспонент расписывать влом.
Как из вероятности события P найти, через сколько повторений оно состоится с вероятностью Q — это уже совсем просто.
К>Ну и нужно посчитать интеграл P = INT [t=-3h..+3h] s(t). Это вероятность столкновения в одном периоде.
К>Извини, кучу экспонент расписывать влом.
К>Как из вероятности события P найти, через сколько повторений оно состоится с вероятностью Q — это уже совсем просто.
1) Снача сведем задачу о двух поеЗдах к одному. Исходная задача
эквивалентна тому, что время отправления одного "эффективного" поезда
сместилось за Н отправлений от 0 до 45 минут. У этого "эффективного" поезда
сигма = 6 минут * корень из 2х, как дисперсия двух независимым величин
(двух — потому что мы свели два поезда в один). Пусть, для простоты,
6 минут * корень из 2х = 8.5 минут = с1.
2) Вероятность этого поезда отправиться на 45 минут раньше/позже (в интервале
36 секунд) прямо в первый же раз = Г((45-0)/с1)*(36 секунд), где Г — это гауссово распределение.
Обозначим (36 секунд) за (дт). Итак, вероятность столкнуться в 1ый же раз =
Г((45-0)/с1)*(дт).
3) Вероятность стокнуться при втором отправлении равна Г((45-т1)/с1)*(дт), где т1 =
время сдвига при первом отправлении. Итого, вероятность стоклнуться или в первый или
во 2ой раз, если сдвиг после 1ого — т1 — это Г((45-0)/с1)*(дт) + Г((45-т1)/с1)*(дт)*Г((т1-0)/с1).
Последний множитель равен вероятности иметь сдвиг т1 при 1ом отправлении.
Уточнение: Строго говоря, вероятности этих событий не должны складываться, т.к.
они не взаимоисключаюсчие. Однако, эти вероятности малы __в силу малости (дт) __.
Поэтому с очень хорошей точностью складывать их можно (и значит, нужно).
Далее, мы не знаем т1 — оно может быть любым. Поэтому, чтобы найти вероятность при любом т1,
надо второй член в предыдущей формуле проинтегрировать по т1. Имеем:
полная вероятность за 1ые 2 столкновения =
Г((45-0)/с1)*(дт) + Инт[ Г((45-т1)/с1)*(дт)*Г((т1-0)/с1) * д(т1)] =
(дт) * { Г((45-0)/с1) + Инт[ Г((45-т1)/с1)*Г((т1-0)/с1) * д(т1)] }.
4) Аналогично считается вероятность при 3х отправлениях:
(дт) * { как выше + Инт[ Г((45-т2)/с1) * Г((т2-т1)/с1) * Г((т1-0)/с1) * д(т1) *д(т2)] }.
Последний интеграл уже двойной, по т1 и т2.
Ну и аналогично для любого числа отправлений.
5) Как найти аналитическую формулу, я точно не знаю. Дело в том, что один или два
раза интеграл взять можно, но потом формулы станут необозримыми. Делать интегрирование
численно — тоже не вариант. Отправлений должно быть довольно много, чтобы получить
заметную вероятность столкновения, а сделать численно уже, скажем, 20тикратный интеграл
не представляется возможным ни на каком компе, насколько я знаю.
НО: Каждый интеграл — это многомерная свертка. Если Фурье преобразование от многомерной
свертки подчиняется тому же простому правилу, что Фурье от простой свертки (я не знаю, так
ли это), то тогда каждый след. член можно легко найти из предыдусчего в Фурье-пространстве, а
дальше взять обратное Фурье, чтобы получить ответ.
Как-то таг.
Дис-клейзмер: Наверное, есть и поэлегантнее решение. Но, наскоько я знаю, большинство
элегантных решений в мире опираются на некий нетривиальный шаг, допереть до которого
может быть так же долго, как взять 20ти-кратный интеграл... Поэтому надо брать то, что
просто работает, пусть и не оптимально, зато понятно
Здравствуйте, Lepsik, Вы писали:
К>>Ну и нужно посчитать интеграл P = INT [t=-3h..+3h] s(t). Это вероятность столкновения в одном периоде.
К>>Извини, кучу экспонент расписывать влом.
К>>Как из вероятности события P найти, через сколько повторений оно состоится с вероятностью Q — это уже совсем просто.
L>1) Снача сведем задачу о двух поеЗдах к одному. Исходная задача L>эквивалентна тому, что время отправления одного "эффективного" поезда L>сместилось за Н отправлений от 0 до 45 минут. У этого "эффективного" поезда L>сигма = 6 минут * корень из 2х, как дисперсия двух независимым величин L>(двух — потому что мы свели два поезда в один). Пусть, для простоты, L>6 минут * корень из 2х = 8.5 минут = с1.
L>2) Вероятность этого поезда отправиться на 45 минут раньше/позже (в интервале L>36 секунд) прямо в первый же раз = Г((45-0)/с1)*(36 секунд), где Г — это гауссово распределение. L>Обозначим (36 секунд) за (дт). Итак, вероятность столкнуться в 1ый же раз = L>Г((45-0)/с1)*(дт).
L>3) Вероятность стокнуться при втором отправлении равна Г((45-т1)/с1)*(дт), где т1 = L>время сдвига при первом отправлении. Итого, вероятность стоклнуться или в первый или L>во 2ой раз, если сдвиг после 1ого — т1 — это Г((45-0)/с1)*(дт) + Г((45-т1)/с1)*(дт)*Г((т1-0)/с1). L>Последний множитель равен вероятности иметь сдвиг т1 при 1ом отправлении. L>Уточнение: Строго говоря, вероятности этих событий не должны складываться, т.к. L>они не взаимоисключаюсчие. Однако, эти вероятности малы __в силу малости (дт) __. L>Поэтому с очень хорошей точностью складывать их можно (и значит, нужно).
Начиная отсюда "все неправильно".
1) Откуда вообще взялся множитель *Г((т1-0)/с1) ?
2) Попробую сравнить (численно) Г((45-0)/с1) и Г((45-т1)/с1).
В общем, вероятность столкновения с поездом, отставшим на период — вообще не надо учитывать.
Ты уже пренебрег значительно более весомыми "эффектами", например, заменив интеграл по отрезку
дт на произведение Г((45-т1)/с1)*(дт).
Мы знаем: т1=6 часов (см. расписание).
> ... L>5) Как найти аналитическую формулу, я точно не знаю. Дело в том, что один или два L>раза интеграл взять можно, но потом формулы станут необозримыми. Делать интегрирование L>численно — тоже не вариант. Отправлений должно быть довольно много, чтобы получить L>заметную вероятность столкновения, а сделать численно уже, скажем, 20тикратный интеграл L>не представляется возможным ни на каком компе, насколько я знаю. L>НО: Каждый интеграл — это многомерная свертка. Если Фурье преобразование от многомерной L>свертки подчиняется тому же простому правилу, что Фурье от простой свертки (я не знаю, так L>ли это), то тогда каждый след. член можно легко найти из предыдущего в Фурье-пространстве, а L>дальше взять обратное Фурье, чтобы получить ответ.
L>Как-то таг.
L>Дис-клейзмер: Наверное, есть и поэлегантнее решение. Но, наскоько я знаю, большинство L>элегантных решений в мире опираются на некий нетривиальный шаг, допереть до которого L>может быть так же долго, как взять 20ти-кратный интеграл... Поэтому надо брать то, что L>просто работает, пусть и не оптимально, зато понятно
На самом деле, нужно считать только вероятности столкновений поездов, выходящих с 45-минутным зазором (относительно друг-друга).
Все остальные вероятности, которые ты не знаешь как учесть — пренебрежимо малы. Этого достаточно.
Если вероятность столкновения, одной "пары" поездов P(1)=Г((45-0)/с1,
то вероятность разойтись без столкновения: 1-P(1)
А вероятность обойтись без столкновения на n периодов расписания (в сутках 4 периода расписания): (1-P(1))^n
Соответственно вероятность столкновения в течение n периодов: P(n)=1-(1-P(1))^n
(график этой функции нужно построить в бонусном вопросе).
N- число периодов, через которое вероятность достигнет 0.5
Здравствуйте, Lepsik, Вы писали:
L>5) Как найти аналитическую формулу, я точно не знаю. Дело в том, что один или два L>раза интеграл взять можно, но потом формулы станут необозримыми. Делать интегрирование L>численно — тоже не вариант. Отправлений должно быть довольно много, чтобы получить L>заметную вероятность столкновения, а сделать численно уже, скажем, 20тикратный интеграл L>не представляется возможным ни на каком компе, насколько я знаю. L>НО: Каждый интеграл — это многомерная свертка. Если Фурье преобразование от многомерной L>свертки подчиняется тому же простому правилу, что Фурье от простой свертки (я не знаю, так L>ли это), то тогда каждый след. член можно легко найти из предыдусчего в Фурье-пространстве, а L>дальше взять обратное Фурье, чтобы получить ответ.
А оно надо вообще?
Вероятности столкновений вне своего периода (когда один или оба поезда опоздают на 3 часа и более) очень маленькие в силу того, что сама вероятность таких мега-опозданий очень маленькая.
Можно посчитать величину погрешности — грубо говоря, "вероятность столкновения в первом периоде = P, во всех последующих < P*0.001005%, откуда время равно... плюс-минус..."
P — вероятность столкновения в одном периоде
Pn = 1-(1-P)^n — вероятность столкновения в рамках n периодов — установленное значение 50%
n = ceil( ln(1-Pn)/ln(1-P) ) — количество периодов, обеспечивающих эту вероятность
Если P с погрешностью, то... ну получим мы, в самом худшем случае, погрешность в ±1 период.
К тому же, распределение вероятности отклонения от расписания — это не совсем гауссов колокол, он слева ограничен тремя часами от предыдущего отклонения.
И ещё непонятно:
— вот допустим, поезд опоздал на 2 часа — это значит, что он отправится в интервале [-1;+oo), т.е. может или убежать, или протупить
— а если на 3 часа — [0;+oo), т.е. ему нужно отправиться немедленно, но он может протупить
— на 4 — [+1;+oo), т.е. немедленно, но совсем чуть-чуть протупить, или [-2;+oo) — т.е. один рейс вообще отменили и начали всё по-новой?
И что там с нормализацией этих огрызков колоколов?
Слишком много плохих вопросов, из которых следует вывод: не забивать себе голову! Считать, что каждый период полностью самостоятельный, а отклонение более чем на половину периода будем считать инсинуацией. Советские поезда так не нарушают расписание.
Перекуём баги на фичи!
