自己想到的一个算法题

[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 好吧，这些边界情况应该是比较重要的，我没有考虑在内，也许要加上一个黄灯时间才更具合理性。