我有很多长度为 10 的序列，由 0 和 1 组成。例如：
1010100000
1011000001
1011100010
1100000100
0011111011
等等。
我想找到在每列中共同具有 0 的序列。例如，算法应该返回这两个：
1100000100
0011111011
这三个：
1100110000
0011111111
1111001111
等等
有这个算法吗？
问问题
60 次
1 回答
2
您所描述的问题是您想要找到所有解决方案的精确覆盖问题的受限情况。这个问题的一般版本是 NP-hard，所以对于这个更大的问题没有已知的有效的一般算法。
要找到所有可能的解决方案，您可以尝试列出位向量的所有子集，并测试每个子集的每一列中是否正好有一个 0。您还可以考虑实施回溯搜索算法来尝试选择所有子集，但这会停止搜索可能无法工作的路径（例如，包含两个位向量且同一列中有 0 的路径）。如果您愿意，您可以尝试实现跳舞链接算法，该算法专门用于列出此一般问题的所有解决方案。
希望这可以帮助！
于 2013-03-16T16:06:58.187 回答