智游城

标题: 追车问题 [打印本页]

作者: 老陈 时间: 2020-4-11 17:26
标题: 追车问题
在一条单线无线长的公路上，有100辆汽车以不同的速度同一方向行驶，初始汽车的前后距离15米，每辆汽车的速度都不变，如果发生追尾后面的车退出，前面的车继续。问达到稳定状态时剩余汽车的期望值多少？

作者: ahthwl 时间: 2020-4-12 14:09
假设N辆车的速度是从1~N的随机排序数组。比如4辆车的速度分别为[1，2，3，4]，某一个随机数组为[3,1,2,4]
那么针对单个随机数组求最终车辆的数量等价于：求以数组最后一位为终点的严格单调递增子序列的长度。
例如[3,1,2,4]以4为终点的单调递增子序列：从4往前第一个小于4的是2，子序列为[4,2],再往前小于2的是1，子序列为[4,2,1]，最终是三辆车。
[2,3,1,4]以4为终点的单调递增子序列为[4,1]，最终有两辆车剩下来。
针对速度列表的所有随机数组都进行单调递增子序列的计算，总和除以全排列中数组的数量，就是最终的期望值。
我没有去求全排列然后计算期望值，简单随机排序了10000次，最终期望值是5.1左右。

作者: ahthwl 时间: 2020-4-12 14:24
又想到了用动态规划的方式去精确求解，思路就不赘述了。代码如下：
dp=[0 for i in range(100)]
dp[0]=1
dp[1]=2
for i in range(2,100):
dp[i]=sum(dp[:i])/i+1
print(sum(dp)/100)

最终期望值是5.187377517639617

作者: 老陈 时间: 2020-5-9 18:37
结果：Σ(1/k){k=1,100}

欢迎光临智游城 (http://zhiyoucheng.co/)