Математика для автомобилистов
chva придумал задачку (точнее, суровые жизненные условия ему ее предложили :)).
Вы едете на машине в точку X и ищете место для парковки. Припарковаться можно только около тротуара. После точки X парковаться уже нельзя, поэтому вы теряете уйму времени (вариант: вынуждены сделать длинный круг и снова искать место). Вы видите только, свободно ли место непосредственно рядом с вами, дальше все загораживают другие машины. Ждать, пока место освободится, нельзя (за вами поток машин). Какой должна быть правильная стратегия в такой ситуации? Все нужные параметры считать известными.
Решение, которое я придумал, такое:
Пусть мы едем из точки a в точку 0, скорость машины V, скорость пешехода v, вероятность того, что в точке x можно припарковаться, равна p(x), потеря времени в случае облома равна T. Кажется понятным, что стратегия должна выглядеть следующим образом: до некоторой точки x0 едем, не паркуясь, а за ней паркуемся на первом встреченном свободном месте. Тогда имеем:
- с вероятностью \int_0^x0 (1-p(x))dx мы не встретим свободного места и потеряем время T.
- с вероятностью (\int_x^x0 (1-p(y))dy)p(x) мы встретим первое свободное место в окрестности точки x и потратим время x/v + (a-x)/V.
Итого стратегия для точки x0 дает нам среднее время
t(x0) = T * \int_0^x0 (1-p(x))dx + \int_0^x0 (\int_x0^x (1-p(y))dy) (x/v + (a-x)/V) p(x)dx
Продифференцировав по x0 и приравняв к нулю, находим:
T = (x0/v + (a-x0)/V) * (P(x0)-P(0)),
где P - первообразная p.
Очевидно, что, поскольку v < V, а P возрастает, уравнение имеет ровно одно решение, которое и соответствует оптимальной стратегии.
Аналогичное дискретное уравнение, соответственно
T = (x0/v + (a-x0)/V) * \sum_0^x0 p(x_k),
где p(x_k) вероятность того, что k-e, считая от цели движения, место свободно. Оптимальной стратегии соответствует одно из двух целых x_0, между которыми достигается равенство.
Задачка выглядит симпатичной, во-первых, потому что из жизни, а во-вторых, потому, что получается такой простой ответ. Кстати, раз уж он таким простым выходит, то наверняка должно быть решение без высшей математики.
(Специально для maksa: ответ простой в том смысле, что уравнение вышло не дифференциальным и даже почти линейным относительно P(x0).)
Вы едете на машине в точку X и ищете место для парковки. Припарковаться можно только около тротуара. После точки X парковаться уже нельзя, поэтому вы теряете уйму времени (вариант: вынуждены сделать длинный круг и снова искать место). Вы видите только, свободно ли место непосредственно рядом с вами, дальше все загораживают другие машины. Ждать, пока место освободится, нельзя (за вами поток машин). Какой должна быть правильная стратегия в такой ситуации? Все нужные параметры считать известными.
Решение, которое я придумал, такое:
Пусть мы едем из точки a в точку 0, скорость машины V, скорость пешехода v, вероятность того, что в точке x можно припарковаться, равна p(x), потеря времени в случае облома равна T. Кажется понятным, что стратегия должна выглядеть следующим образом: до некоторой точки x0 едем, не паркуясь, а за ней паркуемся на первом встреченном свободном месте. Тогда имеем:
- с вероятностью \int_0^x0 (1-p(x))dx мы не встретим свободного места и потеряем время T.
- с вероятностью (\int_x^x0 (1-p(y))dy)p(x) мы встретим первое свободное место в окрестности точки x и потратим время x/v + (a-x)/V.
Итого стратегия для точки x0 дает нам среднее время
t(x0) = T * \int_0^x0 (1-p(x))dx + \int_0^x0 (\int_x0^x (1-p(y))dy) (x/v + (a-x)/V) p(x)dx
Продифференцировав по x0 и приравняв к нулю, находим:
T = (x0/v + (a-x0)/V) * (P(x0)-P(0)),
где P - первообразная p.
Очевидно, что, поскольку v < V, а P возрастает, уравнение имеет ровно одно решение, которое и соответствует оптимальной стратегии.
Аналогичное дискретное уравнение, соответственно
T = (x0/v + (a-x0)/V) * \sum_0^x0 p(x_k),
где p(x_k) вероятность того, что k-e, считая от цели движения, место свободно. Оптимальной стратегии соответствует одно из двух целых x_0, между которыми достигается равенство.
Задачка выглядит симпатичной, во-первых, потому что из жизни, а во-вторых, потому, что получается такой простой ответ. Кстати, раз уж он таким простым выходит, то наверняка должно быть решение без высшей математики.
(Специально для maksa: ответ простой в том смысле, что уравнение вышло не дифференциальным и даже почти линейным относительно P(x0).)