すべてのプライマサブマトリクスの最大合計

Question

タイトルに問題があります。この問題への私のアプローチは、そのようなものです：

1. n×nの非負の整数行列
2. ある1SはVを言わせて、入力中に素数を表しバイナリ行列Bを、1×1を含むすべての正の部分行列を見つける作成fom B
3. それらの合計を求めて、サブマトリックスの左上隅とその大きさで最大のものを返します。

この意味で、私のアルゴリズムのセクション2は少し複雑に思えます。私が思うには、ブルートフォースなしでそれらを見つける方法はありますか？ループを介して繰り返し、それらを見つける。私はmatlabに私が望むものを返す関数があることを望んでいます。

何か助けていただければ幸いです。

Answer 1

これはあなたが計画し何を約ある：

% generate random matrix 
sz = [20 20]; 
imax = 200; 
A = randi(imax,sz); 
% binary matrix of primes 
B = isprime(A); 
% concat both 
C = cat(3,A,B); 
% compute maximum number of rows&cols in each cc in B 
cc = bwconncomp(B,4); 
[rows,cols] = cellfun(@(ind)ind2sub(size(B),ind),cc.PixelIdxList,'UniformOutput',false); 
maxwidth = max(cellfun(@(c) max(c) - min(c),cols)) + 1; 
maxheight = max(cellfun(@(c) max(c) - min(c),rows)) + 1; 
% find max-sum sub matrix 
valMax = 0; 
idxMax = [0,0]; 
for ii = 1:maxheight 
    for jj = 1:maxwidth 
     % generate rectangle filter 
     h = ones(ii,jj); 
     n1 = ii*jj; % number of elements in filter 
     % filter the concat matrix 
     res = imfilter(C,h); 
     % indexes of cc having rectangular shape 
     idxs = find(res(:,:,2) == n1); 
     if isempty(idxs) 
      break 
     end 
     % find max value of all relevant rectangles 
     [v,i] = max(res(idxs)); 
     if v > valMax 
      valMax = v; % max value 
      [r,c] = ind2sub(size(B),idxs(i)); 
      r = r - ceil(ii/2) + 1; 
      c = c - ceil(jj/2) + 1; 
      idxMax = [c,r,jj,ii]; % max value rect [x,y,w,h] 
     end 
    end 
end