查找大小为 k 的所有精确覆盖

Question

我正在寻找一些关于如何解决以下问题的想法。我的主要语言是 R。

描述

我有一个集合S和一组有效子集U。我希望找到U中S的所有精确覆盖，并且恰好使用k个子集。

例如

• 设S = {1,2,3,4}
• 有效子集U = {{1,2,3,4},{1,2},{3,4},{1,4},{2,3},{1},{4}}
• 当k = 1 时，有 1 个解 {1,2,3,4}
• 当k = 2 时，有 2 个解 {{{1,2}{3,4}},{{1,4}{2,3}}}
• 当k = 3 时，有 1 个解
• 当k >= 4 时无解

问题

在我的现实生活示例中，集合S有 500 个元素，U有 500,000 个子集。每个子集都有 1 到 8 个元素。使用线性程序，我发现最小精确覆盖的大小为 70。我正在寻找大小为 70 的所有覆盖。理论上，我可以循环线性程序，为现有解决方案添加约束，以便找到新的解决方案。我怀疑这会很慢。

我还尝试了 R 中修改的跳舞链接方法，如果深度大于k ，则带有停止点。这适用于较小的示例，但似乎会陷入更深入的搜索。我可以通过切换到 C++ 或使用更高级的数据结构（例如 ZDD）来添加一些改进。

任何替代方法的建议将不胜感激。

尝试线性优化

下面的代码是我如何使用线性规划找到最小覆盖范围

library(Rsymphony)

mat #sparse matrix of 1s with dimensions 500 x 500,000
dir <- rep("==",500)
rhs <- rep(1,500)
types <- rep("B",500000)
score <- rep(-1,500000)
max <- T

soln <- Rsymphony_solve_LP(score,mat,dir,rhs,max = max,types = types)

Answer 1

您在问题中提到，您愿意接受与 Dancing Links 实现相关的建议并切换到 C++ 作为替代方案，因此我将提出与此替代方案相关的建议。

您提到您已经通过 Dancing Links 实现了高德纳算法 X。因此，如果没有代码，我会相信您已经正确实现了它，并且只提到一些可以加快速度的关键优化。

1. 确保您的选择启发式选择要覆盖的项目是所有可用选项中最难访问的项目。在下图中，我选择第一个遇到的、最难访问的项目来尝试用k = 2 进行覆盖，以便找到两个总数中的一个可能的解决方案。这可以加快速度。所选项目和用于覆盖它的选项均标有红色星号。

2. 在选择要覆盖的项目时，还要确保检查所有剩余项目，看看是否有由于过去选择的选项而无法访问的项目。如果某个项目在选项中出现次数为零，则应停止沿该分支递归。这将修剪你的递归搜索并阻止你继续探索毫无意义的分支，同时也加快速度。

3. 考虑 Knuth 对 Dancing Links 实际实现的最新修改，并将链接放入数组或向量中，而不是作为网格中的四重链接节点。您可以在易于调试、内存安全并且提供良好的局部性/缓存友好性的数据结构中获得相同的功能。在 C++ 中，以下是我如何布局您的问题以及舞蹈链接如何出现在内存中。

struct header {
    int title;
    int left;
    int right;
};
struct link {
    int topOrLen;
    int up;
    int down;
};
/* This vector controls recursion and is how you 
 * decide what item to attempt to cover.
 */
std::vector<header> lookupTable = {
    {-1, 4, 1},
    {1, 0, 2},
    {2, 1, 3},
    {3, 2, 4},
    {4, 3, 0},
};
/* The top row tracks the number of appearances of a given item.
 * Row spacers point to the first item in the previous row and 
 * last item in the current row. Links in each row point above
 * and below--left and right is implicit--and always point back
 * up to the column header.
 */
std::vector<link> dancingLinks = {
    // 0          1         2         3         4
    {0,0,0},    {4,23,6}, {3,20,7}, {3,21,8}, {4,25,9},
    // 5          6-1       7-2       8-3       9-4
    {-1,0,9},   {1,1,11}, {2,2,12}, {3,3,14}, {4,4,15},
    // 10         11-1      12-2
    {-2,6,12},  {1,6,17}, {2,7,20},
    // 13                             14-3      15-4
    {-3,11,15},                     {3,8,21}, {4,9,20},
    // 16         17-1                          18-4
    {-4,14,18}, {1,11,23},                    {4,15,25},
    // 19                   20-2      21-3
    {-5,17,21},           {2,12,2}, {4,14,3},
    // 22         23-1
    {-6,20,23}, {1,17,1},
    // 24                                       25-4
    {-7,23,25},                               {4,18,4},
    // 25
    {INT_MIN,25,INT_MIN}
};

请注意，在 Knuth 的一些使用数组的 DLX 求解器的评论中，Knuth 提到，与链接节点相比，这种数组方法并没有减少内存访问或mems的数量，因为他在算法中调用了它们。不过，我仍然认为提到的好处是值得的。尽管如此，这仍然是您所描述的一个难题。

最后，如果您想了解如何在 C++ 中通过 Dancing Links 实现算法 X，我在这里使用该技术解决了一个问题：dancing-links-and-planning-pokemon。这是一个愚蠢的虚构问题，但它可能会给您一些切换到 C++ 的想法，并且确切的覆盖实现忠实于 Knuth 的算法。