2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему
 
 задача о выборе ждать или идти пешком до следующей остановки
Сообщение24.04.2016, 03:28 


15/04/10
18/06/20
984
г.Москва
публикую эту задачу скорее из возможности варьирования ее постановок
пусть $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)  $ - еще оценки среднего ожидания
по принципу что заложишь- то и получишь
примечание: в такой постановке задача видимо теряет статус олимпиадной - интегралы вероятностей видимо сложны для школьников

 Профиль  
                  
 
 Re: задача о выборе ждать или идти пешком до следующей остановки
Сообщение24.04.2016, 10:31 


15/04/10
18/06/20
984
г.Москва
для 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$

 Профиль  
                  
 
 Re: задача о выборе ждать или идти пешком до следующей остановки
Сообщение08.05.2016, 21:50 
Аватара пользователя


08/05/16
2
Россия
Задача интересная, а вот постановку я бы поменял.

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

 Профиль  
                  
 
 Re: задача о выборе ждать или идти пешком до следующей остановки
Сообщение08.05.2016, 22:48 
Аватара пользователя


22/06/12
1442
Vitya_40kin в сообщении #1122114 писал(а):
а на автобусе $t_1 \gg t_0$

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

 Профиль  
                  
 
 Re: задача о выборе ждать или идти пешком до следующей остановки
Сообщение23.06.2016, 23:18 
Аватара пользователя


17/05/08
358
Анк-Морпорк
Если взять как отправную точку предположение о том, что нужно ждать $0.5t_0$, а потом идти?

 Профиль  
                  
 
 Re: задача о выборе ждать или идти пешком до следующей остановки
Сообщение24.06.2016, 05:54 
Аватара пользователя


07/01/16
906
Аязьма
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$ стоит под логарифмом, что, так сказать, заметно уменьшает ее величину.

 Профиль  
                  
 
 Re: задача о выборе ждать или идти пешком до следующей остановки
Сообщение09.09.2016, 01:20 


15/04/10
18/06/20
984
г.Москва
не вдаваясь в детали решения 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 или более регулярных потоков разных автобусов

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group