set_cover_greedy.m

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

function cover = set_cover_greedy(A, c)
% SET_COVER_GREEDY Find an approx. minimal set x s.t. x has nonemtpy intersection with every row of A
% x = set_cover_greedy(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)).
% x = arg min  sum_j c(j) x(j) s.t. sum_j A(i,j) x(j) >= 1
%
% We use the greedy heuristic on p466 of "Integer and Combinatorial Optimization",
% Nemhauser and Wolsey, Wiley 1988.
% This selects the column that covers the largest number of uncovered rows per unit cost,
% and stops as soon as a feasible solution is found.
%
% Example: sets = {1,2}  {2,3} {1,3}
% A = [1 1 0;
%      0 1 1;
%      1 0 1];
% x = [1 2]
%
% Example: sets = {1,2}  {2,3} {1,2,3}
% A = [1 1 0;
%      0 1 1;
%      1 1 1];
% x = [2]


% preprocess A to remove any columns which are all 0s
empty = all(~A);
nonempty = find(~empty);
A = A(:, nonempty);

[m n] = size(A);
if nargin < 2, c = ones(1, n); end
ms = 1:m;
ns = 1:n;
done = 0;
while ~done 
  score = zeros(1, length(ns));
  for ji=1:length(ns)
    j = ns(ji);
    Mj = find(A(:,j)==1);
    L = length(myintersect(Mj, ms));
    if L == 0
      score(ji) = inf;
    else
      score(ji) = c(j) / L;
    end
  end
  j = ns(argmin(score));
  Mj = find(A(:,j)==1); 
  assert(~isempty(Mj));
  ns = mysetdiff(ns, j);
  ms = mysetdiff(ms, Mj);
  if isempty(ms)
    done = 1;
    % the eliminated ns (columns) are the ones to keep
    cover = mysetdiff(1:n, ns);

    % post-process to deal with columns of all 0s
    N = length(empty);
    bigdom = 1:N;
    smalldom = nonempty;
    map = find_equiv_posns(smalldom, bigdom);
    cover = bigdom(map(cover));
  end
end