2

我正在使用 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列表。编写可以搜索为此所需的最少列表数量的代码的最佳方法是什么（它会给我一个Band的输出C）？任何帮助都将不胜感激......即使只是关于如何最好地解决这个问题的概念解释（不是实际代码）也将是一个巨大的帮助！

4

2 回答 2

4

方法#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-1迭代中的长度列表来进行一些冗余计算，这些列表n已经在之前的迭代中找到（如果适用）。在这种情况下，递归解决方案可能会起作用。
  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
于 2016-03-31T07:44:01.387 回答
1

Amro提供的与 Dev-iL 的第一种方法类似的解决方案：

function varargout = q36323802A
R = [0 1 2 3 4 5 6 7 8 9];

names = {'A' 'B' 'C' 'D' 'E'};
L = {...
    [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]
};
N = numel(L);

%// powerset of L: set of all subsets (excluding empty set)
powerset = cell(1,N);
for k=1:N
    sets = nchoosek(1:N, k);
    powerset{k} = num2cell(sets,2);
end
powerset = cat(1, powerset{:});

%// for each possible subset, check if it covers the target R
mask = false(size(powerset));
for i=1:numel(powerset)
    elems = unique([L{powerset{i}}]);
    mask(i) = all(ismember(R, elems));
end
if ~any(mask), error('cant cover target'); end

%// from candidates, choose the one with least amount of sets
candidates = powerset(mask);
len = cellfun(@numel, candidates);
[~,idx] = min(len);
out = candidates{idx};
varargout{1} = names(out);
于 2016-03-31T16:23:22.557 回答