Идущий по Отражениям (solmyr) wrote,
Идущий по Отражениям
solmyr

Category:

Математика для автомобилистов

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).)
Tags: math
Subscribe

  • Post a new comment

    Error

    default userpic

    Your reply will be screened

    When you submit the form an invisible reCAPTCHA check will be performed.
    You must follow the Privacy Policy and Google Terms of use.
  • 17 comments