set_cover_naive.m

来自「麻省理工学院的人工智能工具箱,很珍贵,希望对大家有用!」· M 代码 · 共 41 行

function covers = set_cover_naive(A, c)
% SET_COVER_NAIVE Find a set of minimal sets x such that each x has nonemtpy intersection with every row of A
% covers = set_cover_naive(A, c)
%
% A(i,j) = 1 if case i contains element j and is 0 otherwise (m x n matrix)
% c is an optional vector of the covering costs (default: ones(1,n)).
% covers{k} is the k'th set x which minimizes
%   sum_j c(j) x(j) s.t. sum_j A(i,j) x(j) >= 1
%
% This naive implementation enumerates all subsets of columns of A
% to find the least cost covers.
%
% Example: sets = {1,2}  {2,3} {1,3}
% A = [1 1 0;
%      0 1 1;
%      1 0 1];
% covers = { [1,2], [1,3], [2,3] }
%
% Example: sets = {1,2}  {2,3} {1,2,3}
% A = [1 1 0;
%      0 1 1;
%      1 1 1];
% covers = { [2] }

[m n] = size(A);
if nargin < 2, c = ones(1, n); end
SS = subsets(1:n);
nSS = length(SS); % 2^n
cost = zeros(1, nSS);
for i=1:nSS
  u = SS{i};
  covering = all(any(A(:,u), 2));
  if covering
    cost(i) = sum(c(u));
  else
    cost(i) = inf;
  end
end
ndx = find(cost==min(cost));
covers = SS(ndx);