定义
这就是Pre-Fascicle 5C,Dancing Links第 7 页(当前)上的确切封面问题如何扩展到非主要项目:
...一个精确的覆盖问题涉及 N 个不同的项目,其中 N1 是主要的,N2 = N - N1 是次要的。它由一系列选项定义,每个选项都是项目的子集。每个选项必须至少包含一个主要项目。任务是找到所有选项的子集,这些子集 (i) 每个主要项目恰好包含一个,并且 (ii) 每个次要项目最多包含一次。
(纯粹次要的选项被排除在这个新定义之外,因为算法 X 永远不会选择它们,因为我们已经对其进行了改进。如果由于某种原因您不喜欢该规则,您可以随时回到松弛选项。练习 19 讨论了另一个有趣的选择。)
您的问题由第一段中强调的(Knuth)句和第二段回答。Knuth 解决的确切覆盖问题不允许(或忽略)无助于覆盖主要项目的选项,即纯粹由次要项目组成。
例子
在您的问题示例中,我们称列 A、B、C,其中 A 是次要的,B 和 C 是主要的。选项包括:
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 0, 0] -- option 2: [A]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
所以这里第三行[1 0 0]
,即选项2,不包含主要项目。
您可以在名为 (say) 的文件中使用以下输入运行 Knuth 的程序 DANCE 或 DLX1 foo.dlx
:
B C | A
B
C
A
A B
B C
A B C
这些程序找到相同的四种解决方案:
$ ./dance 1 < foo.dlx
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, after 12 updates.
或者
% ./dlx1 m1 < foo.dlx
Option ignored (no primary items): A
(5 options, 2+1 items, 14 entries successfully read)
1:
C (1 of 3)
B (1 of 2)
2:
C (1 of 3)
B A (2 of 2)
3:
C B (2 of 3)
4:
C A B (3 of 3)
Altogether 4 solutions, 261+231 mems, 12 updates, 360 bytes, 6 nodes.
(请注意第二个程序中的明确警告,即选项 2 仅包含次要项 A,将被忽略。)
解决方案1:改变问题
如果您删除不包含主要项目(列)的选项(行),那么该程序已经可以运行:您获得的解决方案对于新问题确实是详尽无遗的。
解决方案 2:松弛选项
正如 Knuth 在引用的第二段中所说(忽略练习 19 的替代方案;它用于解决不同的问题),如果您真的想包含仅包含次要项目的选项,您可以回到松弛选项的想法。在 2000 年的论文中,这个想法是您引用的段落之后的下一句:
如果我们简单地为每个辅助列附加一行,在该列中包含一个 1,则广义覆盖问题可以转换为等效的精确覆盖问题。
(也就是说,对于每个次要项目,我们添加一个仅包含该项目的选项,现在将其视为仅包含主要项目的精确覆盖问题。)
更详细地说,我假设您要解决以下问题:
有 N 个不同的项目(列),其中一些是主要的,另一些是次要的。
有一些选项系列(行),每个选项都是一组项目(列)。其中一些可能不包含主要项目。
找到所有包含每个主要项目的选项的子集恰好一次,并且每个次要项目最多一次。
为了解决这个问题,我们可以做到以下几点:
在给定的选项(行)中,识别那些仅包含次要项目(列)的选项。因此,您获取给定的所有行的集合,并将其划分为两组:一组(称为 X),其中每个选项都包含至少一个主要项目,另一组(称为 Y),其中每个选项仅包含次要项目。
对于每个次要项目,形成仅包含该项目的选项(行)。令 Z 为所有此类单项(松弛)选项的集合。
现在,将您的选项列表 (X + Y) 替换为 (X + Y + Z),其中 + 是联合:Y 和 Z 之间可能有一些重叠,但您将只保留每个选项中的一个。
最后,解决最初的精确覆盖问题(所有选项都是主要的问题)。你会得到一些解决方案。
对于您获得的每个解决方案,
首先丢弃(忽略)不在 X 或 Y 中的每个选项(即,是您另外添加的松弛选项之一)
其余选项中,形成解决方案中仅包含次要项的选项集 Y'。令 X' 为剩余的集合(即解决方案中包含至少一个主要项目的选项)。
为 Y' 的每个子集附加解 (X' union S)。
在您的问题示例中: X 是以下集合:
[0, 1, 0] -- option 0: [B]
[0, 0, 1] -- option 1: [C]
[1, 1, 0] -- option 3: [A, B]
[0, 1, 1] -- option 4: [B, C]
[1, 1, 1] -- option 5: [A, B, C]
Y 是以下集合:
[1, 0, 0] -- option 2: [A]
Z 与 Y 相同,因此在这种情况下您无需添加任何内容。
你解决了最初的精确覆盖问题(一切都是主要的),并得到以下解决方案:
[0, 1, 2]。这里 X' = [0, 1] 和 Y' = [2] 并且有两个子集:空集 ([]) 和 Y 本身 ([2])。所以添加两个解 [0, 1] 和 [0, 1, 2]。
[1, 3]。这里 X' = [1, 3] 和 Y' = []。添加解决方案 [1, 3]。
[2, 4]。这里 X' = [4],Y' = [2]。添加两个解决方案 [4] 和 [2, 4]。
[5]。这里 X' = [5],Y' = []。添加解决方案 [5]。
这给出了所有六个解决方案。