задача о выборе ждать или идти пешком до следующей остановки

[eugrita]

публикую эту задачу скорее из возможности варьирования ее постановок
пусть $T_i$ интервал движения (детерминированный)
классическая постановка и решение вроде такое
человек приходит на остановку ждет время $t_0$ и потом уходит.
Найти вероятность дождаться (или уйти пешком)

решение: строим квадрат с стороной $T_i$
и параллельно диагонали проводи 2 прямые $y=x \pm t_0$
вероятность уехать - доля площади квадрата между прямыми, а остаться - доля оставшейся площади.

Чуть модифицировав задачу и введя времена
$t_1$ время дойти пешком до следующей остановки
и $t_2$ время движения транспорта до остановки
видимо можно найти мат. ожидание затраченного времени и ответить на вопрос
выгоднее ждать или не ждать
---------------------------------------------------------
2)модификация этой задачи известна под именем задача "Трамвай"
(возможность идти пешком или вернуться на остановку)
---------------------------------------------------------
3)но есть и другая формализация (поток случайных событий)
Оценить среднее время ожидания $T$ считая инт-лы времени ожидания –независимыми одинаково распредел с в с Средним временем ожидания $T_i =m $ и станд. откл. $s$ и зная $f(t)$-плотность вер-ти для инт-лов последовательного прибытия
------------------------------------------------------------------------------------
решение: $T=\frac{1}{2m}\int{t^2 \cdot f(t)dt}=\frac{m^2+s^2}{2m}$
для показательного распределения $f(t)=\lambda \exp(\lambda t)$
можно получить $T=m=T_i $
Если считать инт-лы между прибытиями имеют равномерное распределение
$f(t)=\frac {1}{T_i}$ при $0<t<T_i$ можно получить
$T=\frac{T_i}{3}$
если предположить еще какой-то закон для $f(t) $ - еще оценки среднего ожидания
по принципу что заложишь- то и получишь
примечание: в такой постановке задача видимо теряет статус олимпиадной - интегралы вероятностей видимо сложны для школьников

[eugrita]

для 1 постановки задачи у меня получено следующее
вероятность уехать $Py=2k-k^2$ где $k=\frac{t_0}{T_i}$
при $t_2<0.5 \cdot T_i $ минимум матожидания затрат времени достигается при $k=1$ и равен $0.5 \cdot t_0+t_a$
В противном случае ($t_2> 0.5 \cdot T_i $) минимум матожидания затрат времени достигается при $k=0$ (не ждать ни секунды) и равен $0.5 \cdot t_0+T_i$

примеч. для постановки 3) видимо не корректно принимать равномерное распределение шириной $Ti$ т к это противоречит смыслу понятия "интервал движения"
видимо более правильно принять ширину равномерного распределения $2Ti$
тогда имеем $T=\frac{2}{3} T_i$

[Vitya_40kin]

Задача интересная, а вот постановку я бы поменял.

Пусть человек, находясь на автобусной остановке (точка А), хочет как можно быстрее оказаться в точке В. Пешком он потратит $t_0$ времени, а на автобусе $t_1 \gg t_0$. Проблема в том, что расписания он не знает, а спросить не у кого. Задача: какой алгоритм поведения ему выбрать чтобы наверняка оказаться в точке B и за как можно меньшее время?

[StaticZero]

Vitya_40kin в сообщении #1122114 писал(а):

а на автобусе $t_1 \gg t_0$

Наверное, всё-таки $t_1 \ll t_0$.

[General]

Если взять как отправную точку предположение о том, что нужно ждать $0.5t_0$, а потом идти?

[waxtep]

Vitya_40kin в сообщении #1122114 писал(а):

Задача интересная, а вот постановку я бы поменял.

General в сообщении #1133627 писал(а):

Если взять как отправную точку предположение о том, что нужно ждать $0.5t_0$, а потом идти?

Можно попробовать что-то прикинуть. Пусть время в пути до следующей остановки пешком $t_0$, а, на автобусе, $t_1, t_0\gg t_1, \Delta t=t_0-t_1$. Предположим, время до прихода автобуса есть некая случайная величина с функцией распределения $F(T)=\int\limits_0^T\rho(t)dt$. Мы выбирам стратегию "подождать некоторое время $t_2$, и, если автобус не пришел, пойти пешком" и ищем оптимальное значение $t_2$ в том смысле, чтобы среднее суммарное время ожидания и время в пути было минимальным. Оно равно:

$$\tau=\int\limits_0^{t_2}\rho(t)(t+t_1)dt+(1-F(t_2))(t_2+t_0)$$

Условие экстремума запишется как

$$\frac{\partial \tau}{\partial t_2}=0=1-F(t_2)-\rho(t_2)\Delta t$$

Допустим, $F(t)=1-e^{-\lambda t}, \rho (t)=\lambda e^{-\lambda t}, \lambda >0$; легко видеть, что в этом случае экстремума нет вообще, т.к. $\frac{\partial \tau}{\partial t_2}=e^{-\lambda t_2}(1-\lambda \Delta t)$ знакопостоянна. То есть, если интервалы между автобусами долгие, $\lambda \Delta t<1$, надо сразу идти, в противном случае, ждать прихода автобуса до упора. Это скучный ответ, попробуем еще продвинуться: пусть, например, автобусные маршруты бывают всего двух видов: очень частые, с $\lambda_g\Delta t\gg 1$ и очень редкие, с $\lambda_b\Delta t\ll 1$; мы не знаем, на какой маршрут попали, скажем, он очень частый с вероятностью $p$ и очень редкий с вероятностью $(1-p)$. Тогда условие экстремума запишется как

$$pe^{-\lambda_g t_2}(1-\lambda_g \Delta t)+(1-p)e^{-\lambda_b t_2}(1-\lambda_b \Delta t)=0$$

что в наших предположениях можно огрубить до

$$-p \lambda_g \Delta te^{-\lambda_g t_2}+(1-p)e^{-\lambda_b t_2}=0$$

Наконец, предполагая, что мы с равной вероятностью могли попасть как на очень частый, так и на очень редкий маршрут, $p=\frac 1 2$, получим оптимальное время ожидания

$$t_2=\frac 1{\lambda_g-\lambda_b} \ln \lambda_g \Delta t$$

Если очень частые автобусы ходят раз в минуту, а очень редкие раз в час, путь на автобусе между остановками так же минута, а, пешком, десять минут, то, в данных предположениях, имеет смысл ждать примерно $\ln 9\approx 2.2$ минуты. При другом варианте доопределения задачи, конечно, получится что-то другое. Практически же, если надо проехать всего одну остановку, и она недалеко (и погода хорошая), лучше двигаться сразу подобный вывод ("если идти недалеко, нет смысла долго ждать") можно попробовать сделать и из данного частного примера, поскольку большая величина $\lambda_g \Delta t$ стоит под логарифмом, что, так сказать, заметно уменьшает ее величину.

[eugrita]

не вдаваясь в детали решения waxter лишь замечу что фактически имеем дело с 2 типами задач
1)принятия решения в условиях полной (или частичной) определенности
т.е. известны все интервалы $t_0,t_1,T$
где $T $ интервал движения единственного транспорта но не известно время прибытия на остановку
2)принятия решения в условиях неопределенности
известны $t_0,t_1$ но неизвестен интервал $T $ (видимо он не совсем неизвестен а известен его диапазон $T_m<T<T_b$ и можно принять гипотезу о законе его распределения, например,равномерном)
в обоих случаях 1),2) возможен выбор как варианта оптимального (минимального)( по матожиданию , так и по критерию минимума наихудшего (пессимистический прогноз)
кроме того, стратегия ожидания может быть как задана (фиксировано $t_2$), так и выбираться ЛПР
так например в случае варьируемого времени ожидания наихудшее (максимальное время) добраться до следующей остановки - $T_{max}(1)=\min (T+t_1,t_0)$
(если $T+t_1<t_0$ то ждать автобуса до победы иначе сразу идти пешком)
Для n остановок предполагая их равноудаленными и не учитывая время стоянки на остановках
$T_{max}(n)=\min (T+n \cdot t_1,n \cdot t_0)$
рано или поздно с ростом $n$ время на автобусе даже с мах ожиданием будет меньше времени идти все пешком. Правда и здесь возможны финты типа прошел пешком 1 остановку -автобус не обогнал -> на следующей ждать до упора т.е. дерево решений будет не из 2 веток а посложнее
----------------------------------------------------------------------------------------------------
в случае 2 кроме аналитического можно подогнать к схеме ТПР в усл неопределенности или риска задав несколько "состояний природы" в виде интервалов движения - равномерной сетки из $T_m,T_b$ как с известными вероятностями так и без них (неизвестны)
а также набор стратегий ЛПР в виде значений времен ожиданий $t_2$
-----------------------------------------------------------------------------------------------------
ну и конечно как у waxter возможны усложнения типа не одного а 2 или более регулярных потоков разных автобусов