自己想到的一个算法题

[Biwood]

如下图所示，实线为可通行路线，虚线和 X 为不可通行路线。其中 CDGH 为正方形，CH 和 HG 中只有一条为实线，每隔 30 秒实线和虚线互换一次，CD 和 DG 同理，CDGH 中的实线始终保持平行状态，可以理解为十字路口的红绿灯。

小明需要从 A 点走到 E 点，现在有两种方案

1. 沿着 ABCDE 走，只过一次红绿灯
2. 沿着 AHDE 走，过两次红绿灯

遇到红绿灯的时机不确定，那么问题来了，这两种方案那个花费的时间更短？还是说两种方案时间一样？

[Biwood]

咦？没人看吗，我琢磨着可以写个程序算一下平均值什么的

[craiiz]

小明很累的....

[takato]

时间是如何度量的？
走过一条边+x 秒？还是有特殊的计量方法？

[Biwood]

@takato 时间为等红绿灯的时间+行走的时间，假如没有红绿灯，两个方案时间一样，主要区别就在等红绿灯的时间了

[SuperMild]

假设 AB 30 秒，BC 60 秒：
1. ABCDE，运气最好的时候无需等灯，30+60+30+60 = 2min，运气最差的时候等 30 秒，即 2:30
2. AHCDE, 运气最好的时候无需等灯，30+60+30+60 = 2min，运气最差的时候等 30+30 秒，即 3min

[Biwood]

@SuperMild 方案二应该不会出现 30+30 的情况，因为他走到路口的时候总会又一个是绿灯，HC 行不通的时候，HG 肯定行得通

[SuperMild]

@Biwood 即使能通行，但如果下一秒就到了虚实转换的时间，就不够时间过去了，假设 HC 的路程也要走 30 秒，如果 15 秒后就到转换时间，也过不去。

总之这题就算一个最佳情况和一个最坏情况，条件随你怎么变，比如你假设小明可以秒过，那 2.AHDE 的最好和最差就和 1 一样，不能比 1 更好。

[takato]

@Biwood 我的意思就是，走过一条边需要花多久。。。

这个题目设计本身，条件似乎没有给足，比如这个突然出现的 30s 也不知道该如何理解。。

[Biwood]

@takato 30s 是为了标识转换的间隔时间是相等的，也可以写成“固定时间”。当然，为了方便理解，可以给出具体的数字，比如红绿灯每隔 30s 变换一次，走过 AB 需要 10s，走过 BC 需要 20s，以此类推。

[qwertyegg]

几何分布问题，这两条路径的期望时间是一样的

[widewing]

小明的速度呢？走到一半变线的情况？

[ihciah]

ABCDE 相当于一半常绿的红绿灯，期望上更优

[Elethom]

数学期望问题，这跟算法有什么关系。

[binux]

我猜一个，当你过马路时间小于 (√2 - 1) 倍亮灯时间的时候，1 快，否则 2 快

[Biwood]

@widewing 就排除掉走到一半变线的情况吧，假设小明总是能在绿灯期间过去。速度是固定的，可以不用管，只需要根据时间和概率来推理即可。

[Biwood]

@ihciah 为什么我觉得方案二期望更优先呢，你想想，方案一小明运气最差时要等完 30 秒，而方案二中，小明过第一个红绿灯的时候，第二个红绿灯相当于已经等待一段时间了，他好像永远不需要等完 30 秒。

[binux]

@Biwood #16 你 #15 的「小明总是能在绿灯期间过去」和「第二个红绿灯相当于已经等待一段时间了」根本就是矛盾的。既然第二个绿灯已经等待一段时间了，那么这段时间小明过的第一个路口是红灯啊！除非小明是闪电侠。

[Biwood]

@binux 我写的是“第二个红绿灯”而不是“第二个绿灯”。举个例子，小明过第一个绿灯 HC，这时候 CD 肯定是红灯吧，又或者过第一个绿灯是 HG，那这时候 GD 肯定是红灯吧。每当过完第一个绿灯，第二个路口的红灯已经过去一段时间了，不需要等待 30 秒才变绿灯。

[binux]

@Biwood #18 我 #14 通项都给你算好了，是否节省取决于过马路的速度，即黄灯的时间比例。你所谓「方案二期望更优先」完全建立在小明走一半变红灯，别人让他的情况下。

[Biwood]

@binux 好吧，这些边界情况应该是比较重要的，我没有考虑在内，也许要加上一个黄灯时间才更具合理性。

[geelaw]

假设看起来相等的线段相等，小明在小于 30 秒内的时间可以通过红绿灯的一边，不需要考虑转弯的时间，开始时间是在红绿灯周期（ 60 秒）的均匀分布，则显然是只过一次红绿灯期望时间小。

利用耦合法：考虑两个平行世界，它们的红绿灯情况相差通过 AB 需要的时间，世界 X 走第一条路，世界 Y 走第二条路。在 Y 中可以通过 CD 或 GD 时（最后一个红绿灯路），在 X 里更早或当时也可以通过 CD。

[hearfish]

就假设他通过的时间忽略不计（远小于 30 秒）
方案一：最多等 30 秒，最少等 0 秒，平均等待 0.5 * 0 + 0.5 * 15 = 7.5 秒
方案二：无论哪边是绿灯，他都瞬间通过，下一个一定是红灯，平均：15 秒


考虑他通过的时间，假设他需要 10 秒过马路，红绿灯上有倒计时，且他只在绿灯倒计时超过 10 秒时过马路
方案一：最多等 40 秒（小于 10 秒的绿灯 + 30 秒红灯），最少等 0 秒，平均 0 * 1/3 + 20 * 2/3 = 13.3 秒
方案二：到路口时有两种情况
1. 绿灯不到 10 秒：等另一个红灯变绿，通过后继续等 20 秒红灯，平均：5 + 20 = 25 秒
2. 绿灯大于 10 秒：通过后下一个一定是红灯（最多 20 秒），平均 10 秒
总平均：25 * 1/3 + 10 * 2/3 = 15 秒


同样假设他要 10 秒过马路，如果没有倒计时，他过马路的时候红绿灯智能维持绿灯状态，直到他过完马路（即绿灯状态最长可达 40 秒）
方案一：平均等待 0.5 * 0 + 0.5 * 15 = 7.5 秒
方案二
1. 绿灯不到 10 秒：直接通过，下一个一定还是绿灯，平均 0 秒
2. 绿灯大于 10 秒：通过后下一个一定是红灯（最多 20 秒），平均等待 10 秒
总的平均等待时间：0 * 1/3 + 10 * 2/3 = 6.7 秒

至于通项，把 10 秒换成 X，解一下不等式就完事了

[hearfish]

什么？你说红绿灯既没有倒计时也不智能？行人闯红灯好像也是全责吧🐶

[w2cny]

脑子不够用，@-@

[binux]

@hearfish #23 怎么可能有智能红绿灯嘛，按照中国这个情况，10 秒内一定还会有人开始过马路啊，那就是无限绿（红）灯啊。

[autoxbc]

这个从红绿灯得到的灵感，那么应该遵守红绿灯的规则
1. 红绿灯周期为 2t (变绿 => 变红 => 变绿)
2. 绿灯可过，中间变灯可继续通过
3. 行人通过时间为 x，按照常识 x < t

单个红绿灯
绿灯半周期 t，等待时间为 0
红灯半周期，等待时间从 0 ~ t
整个周期的等待时间期望为 4/t

两个连续的随机红绿灯等待时间期望
( 4/t ) * 2 = t/2

正方形的十字路口
因为总有一边为绿灯，第一个灯的等待总是 0，则总等待就是第二个灯的等待
进入路口为绿灯开头：等待时间 t - x
进入路口为绿灯中间某点，过第一灯刚好切信号，等待时间 0
进入路口为绿灯末尾：等待时间 0

这是个线性下降曲线，期望为曲线围出的三角形在 t 上的均值
( t - x )^2/(2t)

这是个抛物线，在 y 轴有 t/2 截距，顶点在 x 轴 ( t , 0 )，开口朝上，左半边取值有效 (因为 x < t )

由此可知，当行人通过时间等于半周期时 ( x = t )，等待期望为 0，由于等待不能为负值，所以等待必为 0

因为截距为 t/2，故斜穿十字路口(4 个信号正交的信号灯)，永远比通过两个连续的随机信号灯要快，即行人因为多了一组路径，人为选择后必然节省时间

注意到单个灯的期望为 t/4，则回到题目，方案 1 & 2 的期望需要由 x 和 t 的关系算得

令 ( t - x )^2/(2t) = t/4，解出临界点为 x = ( 1 - 1/√2)t ≈ 0.2929t

当行人速度很快，x < 0.2929t 时，方案 1 更优
当行人速度较慢，x > 0.2929t 时，方案 2 更优
作为特例，当 x 接近 t 时，等待时间为 0

[okface]

@binux 老哥，问个 pyspider 的问题哈，project 过多的时候加载任务是有上限的吗，为什么 on_start 方法里一个 150 万行的文件就读了 30 万行进去

[binux]

@okface 有时间限制

[MinakoKojima]

14 年多校第二场有一道一模一样的题目，ZCC Love traffic lights。

題意：給一個 20*20 的帶權網格圖，每個結點處有紅綠燈，顏色爲紅 - 綠 - 紅， 綠燈時可以隨便走，紅燈只能右轉，或者闖一次紅燈扣光 12 分，給出綠燈亮起的時間，求 S 到 T 的最短路(到達時間 - 出發時間最短)
解法大概是简化状态 + 最短路。
题目： http://acm.hdu.edu.cn/showproblem.php?pid=4881
题解： http://blog.sina.com.cn/s/blog_6bddecdc0102uyex.html