最优停止找停车位问题的最简单解释

设

x

x

x为一个车位被占用的概率，那么显然

1

−

x

1-x

1−x则为空闲率。停车位坐标如下：

仿照万里挑一的37%原则建模。

设

k

k

k为司机开始考虑停车的位置，那么实际可以停车的位置

i

i

i肯定满足在

i

<

k

i<k

i<k，还有两个约束：

• 司机在$i$
• 若$i$

综上两点，可以求出成功停车的概率：

P

(

k

)

=

∑

i

=

1

k

a

k

−

i

×

(

1

−

a

)

×

a

i

=

∑

i

=

1

k

a

k

×

(

1

−

a

)

=

(

1

−

a

)

k

a

k

P(k)=\sum\limits_{i=1}^ka^{k-i}\times (1-a)\times a^{i}=\sum\limits_{i=1}^ka^{k}\times (1-a)=(1-a)ka^k

P(k)=i=1∑k​ak−i×(1−a)×ai=i=1∑k​ak×(1−a)=(1−a)kak

导数是：

P

′

(

k

)

=

(

1

−

a

)

a

k

+

(

1

−

a

)

k

a

k

ln

⁡

a

=

a

k

(

1

−

a

+

k

ln

⁡

a

)

P'(k)=(1-a)a^k+(1-a)ka^k\ln a=a^k(1-a+k\ln a)

P′(k)=(1−a)ak+(1−a)kaklna=ak(1−a+klna)

所以，在

k

=

a

−

1

ln

⁡

a

k=\dfrac{a-1}{\ln a}

k=lnaa−1​时，效果最好。来感受动态(用Geogebra作图)：

这说明，当已知车位占用率为

a

a

a时，离目的地

k

=

a

−

1

ln

⁡

a

k=\dfrac{a-1}{\ln a}

k=lnaa−1​开始，找到一个车位就停进去，是最好的选择。给出一个

a

a

a，就能算出一个

k

k

k。

《算法之美》第一章“最优停车位置”问题大致也是这么算的，只是它考虑了更复杂的情形，停止位并没有在目的地终止，而是延伸到无穷远处，最终它得到了下表：

浙江温州皮鞋湿，下雨进水不会胖。