2

我已经实现了Knuth 的“Dancing Links”算法来探索广义精确覆盖问题(即,使用辅助列)。对于精确覆盖(即所有列都是主列),代码按预期工作,因此对于简单的稀疏矩阵:

[0, 1, 0]
[0, 0, 1]
[1, 0, 0]
[1, 1, 0]
[0, 1, 1]
[1, 1, 1]

我的代码返回以下一组行作为解决方案:

[0, 1, 2]
[1, 3]
[2, 4]
[5]

而且我还用许多其他确切的封面示例对此进行了测试,并进行了检查。但是,关于辅助列的细节有点模糊。根据我从各种Knuth /非 Knuth资源中收集到的信息,它表明您需要做的是:

唯一的区别是我们通过只为主要列制作列标题的循环列表来初始化数据结构。每个辅助列的标题应具有简单地指向自身的 L 和 R 字段。该算法的其余部分与以前完全相同,因此我们仍将其称为算法 DLX。

在对矩阵/节点/标题的表示方式进行了这些更改,然后将第一列设置为辅助列(即,只有第 2 列和第 3 列是主要列)之后,我最终得到了以下几组行作为解决方案:

[0, 1]
[1, 3]
[4]
[5]

虽然所有这些都是有效的解决方案,并且有些与精确的精确覆盖解决方案重叠,但似乎缺少其他解决方案(即,来自精确覆盖解决方案集中的一些解决方案):

[0, 1, 2]
[2, 4]

也许这是我的一个误解,但我是否在概念上遗漏了一些东西,或者 Knuth 的解释不完整?

如果你能证明你的算法产生了完整的解决方案,这甚至会很有帮助,这将帮助我确认我的算法是不完整的!

不幸的是,即使是Knuth 关于舞蹈链接的“计算机编程艺术”似乎也没有提供太多帮助。

4

1 回答 1

2

定义

这就是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]。

这给出了所有六个解决方案。

于 2019-01-28T19:53:30.140 回答