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

请教一个排班算法问题

  •  
  •   juleswang · 2016-05-24 16:17:47 +08:00 · 5107 次点击
    这是一个创建于 2866 天前的主题,其中的信息可能已经有所发展或是发生改变。

    七个人, 一个人只值白班; 其他 6 个人,可以值白班和夜班,一个班 12 个小时。一天两个班

    • 当天上白班的不能连续上夜班
    • 当天上夜班的第二天不能上白班
    • 一个班必须有三个人
    • 这七个人每周还要安排休息一整天 24 个小时。

    求满足条件的解

    10 条回复    2016-05-26 14:45:22 +08:00
    mx1700
        1
    mx1700  
       2016-05-24 17:00:01 +08:00 via Android
    第一个反应是 prolog
    ammzen
        2
    ammzen  
       2016-05-24 17:32:52 +08:00
    @mx1700 看过 7 周 7 语言的后遗症吧~。~
    hitmanx
        3
    hitmanx  
       2016-05-24 17:33:15 +08:00
    笨方法要不要?递归 + 剪枝

    把白班和夜班放在一个数组里,即从 0 开始依次为 day0 白班,day0 夜班, day1 白班,day1 夜班...则一共有 7 * 2 = 14 个元素。每个元素包含 3 个子元素(一个班必须有三个人).



    伪代码:

    // - 七个人, 一个人只值白班; 其他 6 个人,可以值白班和夜班
    根据以上条件分别计算一次白班和夜班的全排列,只要全局计算一次即可


    def foo(...):

    if (已经填好的元素 > sizeof(daysPerWeek) * sizeof(shiftsPerDay))
    // - 这七个人每周还要安排休息一整天 24 个小时
    if (检查以上条件)
    输出解
    else
    return

    // - 当天上白班的不能连续上夜班
    // - 当天上夜班的第二天不能上白班
    // 这两条是一个意思,相邻的元素不能有子元素相同。
    if (和上一个元素有子元素相同)
    return

    for (根据%2 的结果选择对应的白班全排列或夜班全排列)
    填入对应元素
    foo() // 递归
    弹出对应元素
    stackpop
        4
    stackpop  
       2016-05-24 19:50:53 +08:00   ❤️ 1
    假设 C 必须白班,休假优先级为 ABCDEFG

    第一轮安排如下:

    周一 A 休假 BCD 白班 EFG 晚班
    周二 B 休假 ACD 白班 EFG 晚班
    周三 C 休假 ABD 白班 EFG 晚班
    周四 D 休假 ABC 白班 EFG 晚班
    周五 E 休假 ABC 白班 DFG 晚班
    周六 F 休假 ABC 白班 DEG 晚班
    周日 G 休假 ABC 白班 DEF 晚班

    下一轮把 G 挪到白班,周一白班必须包含 CG , A 和 B 可以随意安排一个,休假还是按每周初始排列轮替。

    最终可以保证除了 C 外,大家值白班和夜班的数量是一样的,保证公平。

    搜索算法给出所有排列容易,难的是选择一个可循环,公平的策略。
    mx1700
        5
    mx1700  
       2016-05-24 20:45:31 +08:00 via Android
    @ammzen 😄是的
    a302800411
        6
    a302800411  
       2016-05-24 20:49:33 +08:00   ❤️ 1
    想的太复杂了 手排都可以
    一周七天 一天两班 一班 三人 7*2*3=42
    42 个班分到 7 个人头上 就是一人一周要上 6 个班
    3 个人只上白班 3 个人只上夜班 还剩一个人周四休息 前三天上夜班 后三天上白班

    乳白色就是那个特殊的人 三天白班 三天夜班
    <img src='https://ooo.0o0.ooo/2016/05/24/57444de959f96.png' />

    红色 周五休息 绿色 周六休息 蓝色 周日休息
    <img src="https://ooo.0o0.ooo/2016/05/24/57444f0329cec.png" alt="QQ20160524-1.png" title="QQ20160524-1.png" />

    夜班一样
    用算法太浪费了...
    ghostheaven
        7
    ghostheaven  
       2016-05-25 06:48:47 +08:00 via Android   ❤️ 1
    @stackpop 要看题目是要什么,要一组满足条件的解,只要凑出一种就行,如果要所有解,@hitmanx 的算法。至于公平解或最优解,需要首先定义什么是最优。
    stackpop
        8
    stackpop  
       2016-05-25 10:18:54 +08:00
    @ghostheaven

    我不是在拼凑一个解,说的是一种轮转的算法,根据对称性是可以求出所有解的。相对于全排列做了剪枝。
    我也没有说最优,更没有自己定义最优。
    公平解符合常识的就是每个人都会轮流日班夜班,而且周期尽可能短。我的算法中,下一轮休假优先级,循环右移 2 个,就可以保证 3 周一轮。

    呃,不要跟我说 show me the code , 当我不会写好了~
    ghostheaven
        9
    ghostheaven  
       2016-05-25 11:04:05 +08:00 via Android
    @stackpop 题目没有说明是否要所有解,还是一组解,我只是怀疑你的算法不能保证求出所有解。如果你的算法的确给出了所有解,那相对递归算法就没有更加公平或最优。拼凑不是针对你的算法,我想说如果只是一组解的话,额外指定一些顺序,可以很容易凑出一个满足条件的解的。
    juleswang
        10
    juleswang  
    OP
       2016-05-26 14:45:22 +08:00
    感谢以上所有的回复, 我觉得手工排列确实能解决问题。而且解法有很多。以上现实世界的问题中,老上夜班确实对身体不好, 但是一会白班一会夜班,人也会受不了。保证公平,这个坑好深,已经超出了题目的范围...
    关于   ·   帮助文档   ·   博客   ·   API   ·   FAQ   ·   我们的愿景   ·   实用小工具   ·   2666 人在线   最高记录 6543   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 27ms · UTC 15:24 · PVG 23:24 · LAX 08:24 · JFK 11:24
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.