请教一个排班算法问题

[juleswang]

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

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

求满足条件的解

[mx1700]

第一个反应是 prolog

[ammzen]

@mx1700 看过 7 周 7 语言的后遗症吧~。~

[hitmanx]

笨方法要不要？递归 + 剪枝

把白班和夜班放在一个数组里，即从 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]

假设 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]

@ammzen 😄是的

[a302800411]

想的太复杂了 手排都可以
一周七天 一天两班 一班 三人 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]

@stackpop 要看题目是要什么，要一组满足条件的解，只要凑出一种就行，如果要所有解，@hitmanx 的算法。至于公平解或最优解，需要首先定义什么是最优。

[stackpop]

@ghostheaven

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

呃，不要跟我说 show me the code ， 当我不会写好了~

[ghostheaven]

@stackpop 题目没有说明是否要所有解，还是一组解，我只是怀疑你的算法不能保证求出所有解。如果你的算法的确给出了所有解，那相对递归算法就没有更加公平或最优。拼凑不是针对你的算法，我想说如果只是一组解的话，额外指定一些顺序，可以很容易凑出一个满足条件的解的。

[juleswang]

感谢以上所有的回复， 我觉得手工排列确实能解决问题。而且解法有很多。以上现实世界的问题中，老上夜班确实对身体不好， 但是一会白班一会夜班，人也会受不了。保证公平，这个坑好深，已经超出了题目的范围...