假设你要开车从A到B，横竖两个方向都要穿过多个路口，怎么走最快？
- 直来直去，走个大折线，简单；
- 碎步溜，走小折线，永远向着目标；
- 见机行事，见绿灯往前冲，见红灯右转。
直觉上，你是不是会选3？
模型
为了便于分析，我们要建立一个简化的模型。
- 从A到B，是一个8x8的棋盘道路；
- 每个路口的红灯、绿灯都是1分钟；
- 不同路口的红绿灯没有关联，你会随机地碰到红灯或绿灯；
- 每个路口都可以左转/直行/右转（忽略变道选择的细节）；
- 不纠结起步、刹车，转弯、直行的各种时间差异。
问题，按怎样的路线开车总时间最短？
01.png
数学分析
首先，走大折线肯定慢。比如走绿线要过14个路口，概率上会碰到7个红灯；而走蓝线也是14个路口，加1个左转弯，概率上是7.5个红灯。还有比这更慢的吗？——显然没有。
其实这个问题可以用递归的方法解决。如图，
02.png
对于一阶最优解S1就是路线R1，等待时间是0个红灯。
S1 = R1 = 0
对于二阶：
- R2A有一个左转，平均0.5个红灯；
- R2B表示如果碰到绿灯先直行，其结果也是0.5个红灯，并不会比R2A更快；
- R2C显然不行，1.5个红灯。所以，
S2 = R2A = 0.5
对于三阶（及更高阶）：
- R3 = 0.5 + R2A；
- 或：R2B + 0.5 （如果先碰到绿灯）；
- 或：R2C + 0.5 （出发时就先右转）太慢了，直接忽略。
递归的方式，实际上是可以穷举的。每一次递归只有3种变化。所以：
- S(1) = 0
- S(n) = 0.5 + S(n-1) = (n-1)*0.5
8阶就是3.5个红灯。每个红灯平均等待30秒，所以最优策略的期望等待时间105秒。
新问题
按照小折线（黄色的路线），最多等7个红灯，最少0个红灯，所以平均算3.5个红灯。没错吧？
每个红灯最多等60秒，最少等0秒（理论上是0.00...01秒才算红灯），所以平均算30秒。没错吧？
这样算下来，总体上平均等待时间30 * 3.5 = 105 秒，这个也没错吧？
但换个角度，总体上最少等0秒，最多等7*60=420秒，中间值是210秒，这个也没错吧？
但平均值是105秒。
这说明，等待的时间不是对称的分布？
感觉有点怪。。
模拟实验
萝卜头实验室不能空谈，一切以实验为准。
本来应该写段程序模拟的。但Excel很强大了，就用Excel吧。
每一行代表一次实验。
一次实验包括：
- 7个路口分别是碰到红灯还是绿灯，以及每个红灯的等待时间。
- 每个路口是否会碰到红灯，公式：=INT(RAND()*2)，0表示绿灯，1表示红灯；
- 每个路口等待的时间：=RAND()*60
- 总共等待的红灯数：=SUM(A2:G2)
- 总共等待的时间：=SUMPRODUCT(A2:G2, H2:N2)
03.png
因为都是随机数，这个表格每次打开都不一样，复制单元格到看的数值也是不一样的。
用条件格式把这个表格弄得更易读（花哨）一点。如前所述，数据不会和前一张图相同。
04.png
最后两列是总计：红色深浅代表红灯多少；蓝色条代表等待时间。
这两列的直方图反映了分布状况。下图代表5000次实验的结果。
05.png
下图代表1048575次实验的结果。
06.png
可以看出，
- 平均碰到的红灯确实是3.5个；
- 等待时间确实不是对称分布。其峰值和均值都是105秒。但0附近和55~60之间的峰值有点奇怪（试了几次都是这样）。
顺便说一句，1048576（=1024*1024）是Excel表格的最大行数。操作这么大的表格对电脑是个考验。
结语
对于纵横两个方向路口数相同的（NxN棋盘格）目的地，交替左转和右转的小折线是最快的，等红灯的总时间只有大折线的一半。
如果纵横两个方向路口数不相同呢？——可以转化成直线段+NxN棋盘格的模式。
最后，实际开车的因素比这复杂得多。这只是个简化模型加Excel的小把戏。仅供参考。
安全第一。
网友评论