数学研发论坛

 找回密码
 欢迎注册
查看: 130|回复: 1

[原创] 步行过红绿灯的最佳策略

[复制链接]
发表于 7 天前 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
我要去的终点需要过$n$条打横的马路和$m$条打竖的马路,如下图所示:

lanes.png

下图是$n=1$、$m=1$的简单例子:

lanes.png

由于马路中间有围栏无法穿过,所以我只能在十字路口走斑马线过马路。

每个十字路口的信号灯都是交替地  允许/禁止  东西方向/南北方向  通行(不允许走对角线),

并且信号灯上有倒计时,明确指示还有多少时间改变通行方向。

为了将问题简化,我们假设:

1. 所有的十字路口的东西方向和南北方向的通行时长是相等的,

2. 两个方向的通行可以无缝切换,也就是两边都不允许通行的时长忽略不计,

3. 马路不宽,而且我过马路很快,所需时长忽略不计。

每在十字路口过完一条马路,我可以根据另一条马路的倒计时,决定等待这个倒计时然后通过,还是直接前行到下一个十字路口。

假设我是无法提前预测下一个十字路口的信号灯状态的,只能走到下一个十字路口,才能看清楚两边的信号灯状态和倒计时。

也就是信号灯的状态处于一个周期里的任一时刻的概率是均匀分布的,并且每个十字路口的信号灯状态相互独立。

我希望采取最佳策略过马路,使得停下来等待的总时长的期望值最小,并且过马路的次数必须为$(n+m)$。

问:

当$n$和$m$都很大的时候(例如:$n=m=5*10^7$),最佳策略下停下来等待的总时长的期望值是多少?

#####

我目前只知道贪心的策略,也就是哪条斑马线可以通行,就过那条斑马线,

于是$(10^8-10^4)$条马路都无需等待,直接通过了,

但是最后的$10^4$条马路就只剩一个方向可以走了,于是就只能干等信号灯了,

所以等待时间的期望值是$10^4/2$次变灯的时间。

不知道最佳策略下,这个期望值能优化到什么级别。

希望坛友们能和我一起来解决这个有趣的问题。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 6 天前 | 显示全部楼层
为简化模型起见,假设每个路口每经过单位时间会均匀变换一下,而每个路口余下的时间显示为单位时间的百分比,如果到达一个路口,总是一个方向是绿灯,另外一个方向显示余下时间为(0,1)中均匀分布的的一个数字。
需要横穿m个路口,竖穿n个路口的等待平均等待时间为E(m,n). 于是显然E(0,n)=n/2,E(m,0)=m/2.
而对于m>n>0,那么如果横向是绿灯,纵向是红灯,显示时间为p,那么他横穿期望时间为E(m-1,n), 纵穿期望时间为E(m,n-1)+p,
于是我们可以得知,在p>E(m,n-1)-E(m-1,n)时,需要选择横穿,不然选择纵穿。同样如果纵向是绿灯,横向是红灯,有类似结论。
由此可以得出:
如果$1+E(m-1,n)>E(m,n-1)>E(m-1,n)$
那么$E(m,n)=1/2 E(m-1,n)+1/2((1-(E(m,n-1)-E(m-1,n)))E(m-1,n)+\int_0^{E(m,n-1)-E(m-1,n)} (p+E(m,n-1))dp )=(2-E(m,n-1)+E(m-1,n))/2 E(m-1,n)+(E(m,n-1)-E(m-1,n))^2/2+(E(m,n-1)-E(m-1,n)) E(m,n-1)$
交换两者关系有类似结论,而余下部分选择时间短的方向,同样可以计算出结果。
于是后面就是一个递归计算的过程了。

评分

参与人数 1威望 +3 金币 +3 贡献 +3 经验 +3 鲜花 +3 收起 理由
KeyTo9_Fans + 3 + 3 + 3 + 3 + 3 看起来这个就是正解了,我有空实现一下

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2021-7-29 18:02 , Processed in 0.055447 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表