algorithm - 如何找到覆盖另一个列表中所有元素所需的最小列表数

Question

我正在使用 Matlab 编写代码，其中我需要找到覆盖引用列表的所有元素所需的最少数量的列表(在某些给定列表中)。

例如，假设我的引用列表是

X = [0 1 2 3 4 5 6 7 8 9] 

我有一组给定的列表，如下所示:

A = [0 1 3 5 6 7 9]
B = [0 1 2 3 4]
C = [5 6 7 8 9]
D = [1 2 3 4]
E = [1 5 7 8]

覆盖X中每个元素所需的最小列表数量是2(B和C)但是，如果我最初只搜索覆盖最多元素的列表 (A)，然后尝试查找将覆盖剩余元素的其他列表，那么我最终将至少使用 3 列表。编写可以搜索所需列表的最少数量的代码的最佳方法是什么(它会给我 B 和 C 的输出)？任何帮助都将不胜感激......即使只是如何最好地解决这个问题的概念解释(而不是实际代码)也会有巨大的帮助!

Answer 1

方法#1:迭代“暴力”所有可能的组合

下面是一种可能的算法，说明了如何解决该问题。代码本身应该是不言自明的，但其想法是我们测试列表的所有可能组合，直到找到有效的组合(因此我们不会遇到您所描述的问题，即我们错误地根据列表的长度选择列表)。

function varargout = q36323802
R = [0 1 2 3 4 5 6 7 8 9]; %// Reference List

L = {... // As per Dan's suggestion:
 [0 1 3 5 6 7 9]
 [0 1 2 3 4]
 [5 6 7 8 9]
 [1 2 3 4]
 [1 5 7 8]
 };
out = []; %// Initialize output
%% // Brute-force approach:
nLists = numel(L);
for indN = 1:nLists
  setCombinationsToCheck = nchoosek(1:nLists,indN);  
  for indC = 1:size(setCombinationsToCheck,1)
    u = unique(cat(2,L{setCombinationsToCheck(indC,:)}));
    if all(ismember(R,u))
      out = setCombinationsToCheck(indC,:);
      disp(['The minimum number of required sets is ' num2str(indN) ...
      ', and their indices are: ' num2str(out)]);
      return;
    end
  end
end
disp('No amount of lists found to cover the reference.');

if nargout > 0 
  varargout{1} = out;
end

对于您的示例，输出为:

The minimum number of required sets is 2, and their indices are: 2 3

注意事项:

1. 此方法通过在迭代 n 中不使用长度为 n-1 的列表来执行一些冗余计算，这些列表已在之前的迭代中找到(如果适用)。在这种情况下，递归解决方案可能会起作用。
2. 可能有一种方法可以对此进行矢量化，但我并没有真正深入考虑。
3. 我假设所有输入都是行向量。如果不是这种情况，则必须采取一些额外的步骤。

---

感谢前往 Adiel 建议一些改进，以及 Amro用于发现一些错误!

---

方法#2:树搜索^_实验

我还尝试构建一个递归求解器。现在它找到了解决方案，但不够通用(实际上问题是它只返回第一个结果，不一定是最好的结果)。这种方法背后的原因是，我们可以将您的问题视为树搜索问题，因此我们可以采用搜索/寻路算法(参见 BFS 、 DFS 、 IDS 等)。我认为下面的算法最接近DFS。和以前一样，这应该主要说明解决问题的方法。

function q36323802_DFS(R,L)
%% //Input checking:
if nargin < 2 || isempty(L)
  L = {... // As per Dan's suggestion:
   [0 1 3 5 6 7 9]
   [0 1 2 3 4]
   [5 6 7 8 9]
   [1 2 3 4]
   [1 5 7 8]
   };
end
if nargin < 1 || isempty(R)
  R = [0 1 2 3 4 5 6 7 8 9]; %// Reference List
end
%% // Algorithm (DFS: breadth-first search):
out = DFS_search(R,L,0);
if isempty(out)
  disp('No amount of lists found to cover the reference.');
else
  disp(['The minimum number of required sets is ' num2str(numel(out)) ...
    ', and their indices are: ' num2str(out)]);
end
end

function out = DFS_search(R,L,depth)
  %// Check to see if we should stop:
  if isempty(R) || isempty(L)
    % // Backtrack here?
    out = [];
    return;
  end
  if isnan(R)
    out = [];
    return;
  end

  nLists = numel(L);
  reducedR = cellfun(@(R,L)setdiff(R,L),repmat({R},[nLists,1]),L,'UniformOutput',false)';
 %'//  We consider a case where the reduction had no effect as "hopeless" and
  %// "drop" it.
  isFullCoverage = cellfun(@isempty,reducedR);
  isHopeless = cellfun(@(R)all(isnan(R)),reducedR) | cellfun(@(rR)isequal(rR,R),reducedR);
  reducedR(isHopeless) = deal({NaN});
  if all(isHopeless) && ~any(isFullCoverage)
    out = [];
    return
  end
  if any(isFullCoverage) %// Check current "breadth level"
    out = find(isFullCoverage,1,'first');
    return
  else
    for indB = 1:nLists
      out = DFS_search(reducedR{indB},L,depth+1);
      if ~isempty(out)
        out = [indB out]; %#ok
        %// TODO: test if one of the sets is covered by the others and remove it
        %// from the list "out".
        %// Also, keep track of the best path and only return (finally) if shortest
        return
      end
    end
  end  
end