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

请教一个算法问题,给学生分配校车乘车路线

  •  
  •   ivae · 165 天前 · 1119 次点击
    这是一个创建于 165 天前的主题,其中的信息可能已经有所发展或是发生改变。

    需要给学生分配校车乘车路线

    if __name__ == '__main__':
        #每路车剩下的空位
        line_left_Num = {
            '5 路':6,
            '6 路':11,
            '9 路': 4,
            '10 路': 9,
            '11 路': 18,
            '12 路': 21,
            '17 路': 36,
            '18 路': 41,
            '21 路': 6,
            '60 路': 20
        }
        # 每个站点还需要分配的学生人数
        site_stu_num = {
            '江山里澜湾小区':21,
            '赞贤路小学、中航云府(赣康路)':30,
            '登峰大道中(城市家园)':7,
            '中海滨江壹号':13,
            '中海国际东郡 B 区(南康路)':30,
            '登峰大道南(中航公元)':64
        }
        # 会经过该站点的线路
        site_line = {
            '江山里澜湾小区': ['11 路','17 路'],
            '赞贤路小学、中航云府(赣康路)': ['5 路','9 路','12 路'],
            '登峰大道中(城市家园)': ['10 路','18 路'],
            '中海滨江壹号': ['6 路','21 路'],
            '中海国际东郡 B 区(南康路)': ['17 路','60 路'],
            '登峰大道南(中航公元)': ['11 路','17 路','18 路']
        }
    

    怎么设计一个算法给在不超载的情况下尽可能把学生都安排上,得到每个站点的每条线路分配人数,比如江山里澜湾小区,11 路分配 6 人,17 路分配 15 人,

    6 条回复    2024-06-16 08:19:50 +08:00
    ivae
        1
    ivae  
    OP
       165 天前
    尝试用贪心算法和动态规划去算,没有太多的思路
    Sawyerhou
        2
    Sawyerhou  
       165 天前 via Android
    给每个学生编个号,然后随便初始化一下,尝试让每个已经上车学生换车,看能不能让其他没上车的学生上车,如果能,继续遍历,如果不能,直接输出?
    sillydaddy
        3
    sillydaddy  
       165 天前
    这个是线性规划。假设所有的站点分别为 s0, s1, s2, s3...sn ,共有 m 路车分别为 b0, b1, b2...bm 。然后 N_s0_b0 来表示 b0 路车在站点 s0 分配的人数。
    那么可以针对所有的 N_si_bi ,列出一组线性不等式。
    首先是在 s0 这个站点,m 路车一共分配的人数要大于该站点等待上车的人数,即 N_s0_b0 + N_s1_b0 + N_s2_b0 + ... + N_s0_bm >= s0 站等待人数
    然后是对于 b0 路车,所有 n 个站点上这辆车的人数小于该路车的空位,即
    N_s0_b0 + N_s1_b0 + ... + N_sn_b0 <= b0 路车空位

    把上面的不等式同样应用到所有的 n 个站点和 m 路车,就可以得到 n + m 个线性不等式。
    线性规划就是解决这种问题的。可以搜一下现有的线性规划库。英文叫 Linear Programming 。

    举几个我考察的例子:
    https://github.com/jvail/glpk.js
    GPL ,似乎适合大规模的求解,比如上万的变量和约束?
    https://www.npmjs.com/package/lpsolver
    MIT ,最简洁,但只有标准形式
    https://www.npmjs.com/package/lp_solve
    LGPL ,比较受欢迎,包大小比较大 2MB ,性能好,规范
    https://www.npmjs.com/package/yalps
    MIT ,看起来很合适,性能也不错,上千的变量和约束只需要几十毫秒
    https://www.npmjs.com/package/simple-simplex
    MIT ,看起来也不错,使用友好
    https://github.com/IainNZ/SimplexJS
    js ,拿来就能用,但不规范
    https://www.npmjs.com/package/@bygdle/javascript-lp-solver
    似乎的新增加的,
    来自 https://github.com/JWally/jsLPSolver ,300 多个 star ,性能也不错。
    sillydaddy
        4
    sillydaddy  
       165 天前
    上面的有一个不等式列错了:
    首先是在 s0 这个站点,m 路车一共分配的人数要大于该站点等待上车的人数,即 N_s0_b0 + N_s0_b1 + N_s0_b2 + ... + N_s0_bm >= s0 站等待人数
    ivae
        5
    ivae  
    OP
       165 天前 via iPhone
    @sillydaddy 谢谢,我试试
    Sawyerhou
        6
    Sawyerhou  
       165 天前 via Android
    如果是算法题,不建议调包,会和面试官手里的答案对不上。如果是生产问题,那楼上说的对,组合优化的包很好用。
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   实用小工具   ·   5404 人在线   最高记录 6679   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 22ms · UTC 07:51 · PVG 15:51 · LAX 23:51 · JFK 02:51
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.