algorithm - 生成带约束的二进制排列

Question

我正在开发医生排类应用程序，我们正在使用线性规划和求解器(如 cplex/lindo)来求解我们的模型。由于一些建模限制，我们需要为夜类生成二进制模式。

通常我们会生成一个月的时间表，因此让我们考虑一下我们需要为夜类生成 30 天的模式。

夜类有一些限制，比如如果一个人连续上夜类，那么医生在接下来的五天内不能工作。下面是一些约束示例。

111000001111100000111110000011 Valid
111000001100000000111110000011 Valid
111010001111101000111110000011 Invalid 

还有其他约束，例如模式中的个数应小于某个定义值，连续个数应小于某个定义值等。

首先，我尝试了简单的算法，该算法从 0 开始并使用按位运算符并加一以获得下一个排列并根据所有约束检查下一个排列如果无效则获取下一个排列并忽略无效模式。由于此模式的长度为 30 位 (2³⁰ = 1073741824)，因此模式数量巨大，无法检查我的简单算法。我想找出所有有效模式需要 24 小时以上。

现在我的问题是

1. 对于给定的问题，我应该使用哪种算法找到所有排列，并以高效的方式应用约束？

2. 这个问题是精确覆盖问题吗？我可以将跳舞链接之类的算法应用于我面临的问题吗？

3. 请提供一些链接以阅读您针对此问题提出的解决方案？

Answer 1

我在“The Art of Computer Programming - Volume 4A – Combinatorial Algorithms, Part 1 by Donald Knuth”部分“7.2.1.2 Algorithm G(General permutation generator)”部分找到了非常好的解决方案。作者在其中描述了绕过不需要的技术 block 。我正在通过增量生成可行区域树并绕过任何不可行路径来实现该算法。我将以一种方式实现，例如从值为 0 的节点开始，该节点有两个子节点 0 和 1，并且每个节点在每次添加新子节点时都有子节点 0 和 1 我们将检查我们的约束集是否不符合约束 不要添加子节点 例如如果算法要在第 5 级添加节点并且结果字符串在第 5 级是 11101，因为夜类约束“101”在 11101 末尾不符合夜类规则，所以不要添加值为 1 的第 5 级节点。继续添加子节点，直到我们有根节点。所以最终我们会有唯一可行的区域，因为我们已经绕过了不需要的 block 。这样我就永远不会触及不可行的区域。