首页   注册   登录
V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
V2EX  ›  算法

自己想到的一个算法题

  •  
  •   Biwood · 61 天前 · 1297 次点击
    这是一个创建于 61 天前的主题,其中的信息可能已经有所发展或是发生改变。
    如下图所示,实线为可通行路线,虚线和 X 为不可通行路线。其中 CDGH 为正方形,CH 和 HG 中只有一条为实线,每隔 30 秒实线和虚线互换一次,CD 和 DG 同理,CDGH 中的实线始终保持平行状态,可以理解为十字路口的红绿灯。

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

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

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

    29 回复  |  直到 2019-04-17 16:47:39 +08:00
        1
    Biwood   61 天前
    咦?没人看吗,我琢磨着可以写个程序算一下平均值什么的
        2
    craiiz   61 天前 via iPhone   ♥ 1
    小明很累的....
        3
    takato   61 天前
    时间是如何度量的?
    走过一条边+x 秒?还是有特殊的计量方法?
        4
    Biwood   61 天前
    @takato 时间为等红绿灯的时间+行走的时间,假如没有红绿灯,两个方案时间一样,主要区别就在等红绿灯的时间了
        5
    SuperMild   61 天前   ♥ 1
    假设 AB 30 秒,BC 60 秒:
    1. ABCDE,运气最好的时候无需等灯,30+60+30+60 = 2min,运气最差的时候等 30 秒,即 2:30
    2. AHCDE, 运气最好的时候无需等灯,30+60+30+60 = 2min,运气最差的时候等 30+30 秒,即 3min
        6
    Biwood   61 天前
    @SuperMild 方案二应该不会出现 30+30 的情况,因为他走到路口的时候总会又一个是绿灯,HC 行不通的时候,HG 肯定行得通
        7
    SuperMild   61 天前
    @Biwood 即使能通行,但如果下一秒就到了虚实转换的时间,就不够时间过去了,假设 HC 的路程也要走 30 秒,如果 15 秒后就到转换时间,也过不去。

    总之这题就算一个最佳情况和一个最坏情况,条件随你怎么变,比如你假设小明可以秒过,那 2.AHDE 的最好和最差就和 1 一样,不能比 1 更好。
        8
    takato   61 天前
    @Biwood 我的意思就是,走过一条边需要花多久。。。

    这个题目设计本身,条件似乎没有给足,比如这个突然出现的 30s 也不知道该如何理解。。
        9
    Biwood   61 天前
    @takato 30s 是为了标识转换的间隔时间是相等的,也可以写成“固定时间”。当然,为了方便理解,可以给出具体的数字,比如红绿灯每隔 30s 变换一次,走过 AB 需要 10s,走过 BC 需要 20s,以此类推。
        10
    qwertyegg   61 天前
    几何分布问题,这两条路径的期望时间是一样的
        11
    widewing   61 天前 via Android
    小明的速度呢?走到一半变线的情况?
        12
    ihciah   60 天前 via iPhone
    ABCDE 相当于一半常绿的红绿灯,期望上更优
        13
    Elethom   60 天前 via iPhone
    数学期望问题,这跟算法有什么关系。
        14
    binux   60 天前   ♥ 1
    我猜一个,当你过马路时间小于 (√2 - 1) 倍亮灯时间的时候,1 快,否则 2 快
        15
    Biwood   60 天前 via Android
    @widewing 就排除掉走到一半变线的情况吧,假设小明总是能在绿灯期间过去。速度是固定的,可以不用管,只需要根据时间和概率来推理即可。
        16
    Biwood   60 天前 via Android
    @ihciah 为什么我觉得方案二期望更优先呢,你想想,方案一小明运气最差时要等完 30 秒,而方案二中,小明过第一个红绿灯的时候,第二个红绿灯相当于已经等待一段时间了,他好像永远不需要等完 30 秒。
        17
    binux   60 天前
    @Biwood #16 你 #15 的「小明总是能在绿灯期间过去」和「第二个红绿灯相当于已经等待一段时间了」根本就是矛盾的。既然第二个绿灯已经等待一段时间了,那么这段时间小明过的第一个路口是红灯啊!除非小明是闪电侠。
        18
    Biwood   60 天前
    @binux 我写的是“第二个红绿灯”而不是“第二个绿灯”。举个例子,小明过第一个绿灯 HC,这时候 CD 肯定是红灯吧,又或者过第一个绿灯是 HG,那这时候 GD 肯定是红灯吧。每当过完第一个绿灯,第二个路口的红灯已经过去一段时间了,不需要等待 30 秒才变绿灯。
        19
    binux   60 天前
    @Biwood #18 我 #14 通项都给你算好了,是否节省取决于过马路的速度,即黄灯的时间比例。你所谓「方案二期望更优先」完全建立在小明走一半变红灯,别人让他的情况下。
        20
    Biwood   60 天前
    @binux 好吧,这些边界情况应该是比较重要的,我没有考虑在内,也许要加上一个黄灯时间才更具合理性。
        21
    geelaw   60 天前 via iPhone   ♥ 1
    假设看起来相等的线段相等,小明在小于 30 秒内的时间可以通过红绿灯的一边,不需要考虑转弯的时间,开始时间是在红绿灯周期( 60 秒)的均匀分布,则显然是只过一次红绿灯期望时间小。

    利用耦合法:考虑两个平行世界,它们的红绿灯情况相差通过 AB 需要的时间,世界 X 走第一条路,世界 Y 走第二条路。在 Y 中可以通过 CD 或 GD 时(最后一个红绿灯路),在 X 里更早或当时也可以通过 CD。
        22
    hearfish   60 天前   ♥ 1
    就假设他通过的时间忽略不计(远小于 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,解一下不等式就完事了
        23
    hearfish   60 天前
    什么?你说红绿灯既没有倒计时也不智能?行人闯红灯好像也是全责吧🐶
        24
    w2cny   60 天前 via Android
    脑子不够用,@-@
        25
    binux   60 天前
    @hearfish #23 怎么可能有智能红绿灯嘛,按照中国这个情况,10 秒内一定还会有人开始过马路啊,那就是无限绿(红)灯啊。
        26
    autoxbc   60 天前   ♥ 1
    这个从红绿灯得到的灵感,那么应该遵守红绿灯的规则
    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
        27
    okface   59 天前
    @binux 老哥,问个 pyspider 的问题哈,project 过多的时候加载任务是有上限的吗,为什么 on_start 方法里一个 150 万行的文件就读了 30 万行进去
        28
    binux   59 天前 via Android
    @okface 有时间限制
        29
    MinakoKojima   38 天前
    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
    关于   ·   FAQ   ·   API   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   774 人在线   最高记录 5043   ·  
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.3 · 20ms · UTC 20:51 · PVG 04:51 · LAX 13:51 · JFK 16:51
    ♥ Do have faith in what you're doing.
    沪ICP备16043287号-1