Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- 1 2 2 4 % top left corner 1 2 - bottom right corner 2 4
- 1 3 1 1 % top left corner 1 1 - bottom right corner 3 1
- %% PROBLEM
- %
- % let P be a matrix whose elements are zeros and ones
- % find the best(*) combination of non-overlapping submatrices of P
- % so that each submatrix respect these properties:
- % - contains at least L zeros and L ones (min area=2*L)
- % - contains at most H elements (max area=H)
- %
- % (*) the best is the one which maximize the total number of elements in all the submatrices
- %
- % notices: the best combination could be not unique
- % is not always possibile to cover all the elements of P with the submatrices of the best combination
- %
- %% INPUT
- P=round(rand(8,8)); L=1; H=5;
- %P=dlmread('small.txt'); L=1; H=5; % small can be found here https://pastebin.com/RTc5L8We
- %P=dlmread('medium.txt'); L=2; H=8; % medium can be found here https://pastebin.com/qXJEiZTX
- %P=dlmread('big.txt'); L=4; H=12; % big can be found here https://pastebin.com/kBFFYg3K
- %P=[0 0 0 0 0 1;0 0 0 0 0 1;0 1 0 1 0 1;0 0 0 0 0 0;0 0 0 0 0 0]; L=1; H=6;
- P=[0 0 0 0 0;0 1 1 1 0;0 0 0 0 0]; L=1; H=6;
- %P=[1,0,0,0,0;1,1,1,1,1;1,0,0,0,0]; L=1; H=5;
- %% FIND ALL THE SUBMATRICES OF AREA >= 2*L & <= H
- %
- % conv2(input_matrix,shape_matrix,'valid')
- % creates a matrix, where each element is the sum of all the elements contained in
- % the submatrix (contained in input_matrix and with the shape given by shape_matrix)
- % having its top left corner at said element
- %
- % ex. conv2([0,1,2;3,4,5;6,7,8],ones(2,2),'valid')
- % ans =
- % 8 12
- % 20 24
- % where 8=0+1+3+4 12=1+2+4+5 20=3+4+6+7 24=4+5+7+8
- %
- s=[]; % will contain the indexes and the area of each submatrix
- % i.e. 1 3 2 5 9 is the submatrix with area 9 and corners in 1 2 and in 3 5
- for sH = H:-1:2*L
- div_sH = divisors(sH);
- fprintf('_________AREA %d_________n',sH)
- for k = 1:length(div_sH)
- a = div_sH(k);
- b = div_sH(end-k+1);
- convP = conv2(P,ones(a,b),'valid');
- [i,j] = find((convP >= L) & (convP <= sH-L));
- if ~isempty([i,j])
- if size([i,j],1) ~= 1
- % rows columns area
- s = [s;[i,i-1+a , j,j-1+b , a*b*ones(numel(i),1)]];
- else
- s = [s;[i',i'-1+a,j',j'-1+b,a*b*ones(numel(i),1)]];
- end
- fprintf('[%dx%d] submatrices: %dn',a,b,size(s,1))
- end
- end
- end
- fprintf('n')
- s(:,6)=1:size(s,1);
- %% FIND THE BEST COMBINATION
- tic
- [R,C]=size(P); % rows and columns of P
- no_ones=sum(P(:)); % counts how many ones are in P
- % a combination of submatrices cannot contain more than max_no_subm submatrices
- if no_ones <= R*C-no_ones
- max_no_subm=floor(no_ones/L);
- else
- max_no_subm=floor(R*C-no_ones/L);
- end
- comb(2,1)=R*C+1; % will contain the best combination
- s_copy=s; % save a copy of s
- [comb,perfect]=recursion(s,s_copy,comb,0,0,R,C,0,false,H,[],size(s,1),false,[0,0,0],0,0,0,0,0,0,max_no_subm);
- fprintf('ntime: %2.2fsnn',toc)
- if perfect
- disp('***********************************')
- disp('*** PERFECT COMBINATION FOUND ***')
- disp('***********************************')
- end
- %% PRINT RESULTS
- if (R < 12 && C < 12)
- for i = 1:length(find(comb(2,3:end)))
- optimal_comb_slices(i,:)=s(comb(2,i+2),:);
- end
- optimal_comb_slices(:,1:5)
- P
- end
- function [comb,perfect,counter,area,v,hold_on,ijk,printed,first_for_i,second_for_i,third_for_i] = recursion(s,s_copy,comb,counter,area,R,C,k,hold_on,H,v,size_s,perfect,ijk,size_s_ovrlppd,size_s_ovrlppd2,printed,third_for_i,second_for_i,first_for_i,max_no_subm)
- %
- % OUTPUT (that is actually going to be used in the main script)
- % comb [matrix] a matrix of two rows, the first one contains the current combination
- % the second row contains the best combination found
- % perfect [boolean] says if the combination found is perfect (a combination is perfect if
- % the submatrices cover all the elements in P and if it is made up with
- % the minimum number of submatrices possible)
- %
- % OUTPUT (only needed in the function itself)
- % counter [integer] int that keeps track of how many submatrices are in the current combination
- % area [integer] area covered with all the submatrices of the current combination
- % v [vector] keeps track of the for loops that are about to end
- % hold_on [boolean] helps v to remove submatrices from the current combination
- %
- % OUTPUT (only needed to print results)
- % ijk [vector] contains the indexes of the first three nested for loops (useful to see where the function is working)
- % printed [boolean] used to print text on different lines
- % first_for_i second_for_i third_for_i [integers] used by ijk
- %
- %
- % INPUT
- % s [matrix] the set of all the submatrices of P
- % s_copy [matrix] the set of all the submatrices that don't overlap the ones in the current combination
- % (is equal to s when the function is called for the first time)
- % R,C [integers] rows and columns of P
- % k [integer] area of the current submatrix
- % H [integer] maximum number of cells that a submatrix can contains
- % size_s [integer] number of rows of s i.e. number of submatrices in s
- % size_s_ovrlppd [integer] used by ijk
- % size_s_ovrlppd2 [integer] used by ijk
- % max_no_subm [integer] maximum number of submatrices contained in a combination
- %
- %
- % the function starts considering the first submatrix (call it sub1) in the set 's' of all the submatrices
- % and adds it to the combination
- % then it finds 's_ovrlppd' i.e. the set of all the submatrices that don't overlap sub1
- % and the function calls itself considering the first submatrix (call it sub2) in the set 's_ovrlppd'
- % and adds it to the combination
- % then it finds the set of all the submatrices that don't overlap sub2 and
- % so on until there are no more non-overlapping submatrices
- % then it replaces the last submatrix in the combination with the second one of the last set of non-overlapping
- % submatrices and saves the combination which covers more elements in P
- % and so on for all the submatrices of the set 's'
- %
- % DOWNSIDE OF THIS METHOD
- % if 's' contains thousands of submatrices, the function will create hundreds of nested for loops
- % so both time and space complexities can be really high and the computer might freeze
- %
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- %%%% SAVE AND RESET COMBINATIONS %%%
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- % s_copy is empty when no more submatrices can be added to the current
- % combination, in this case we have to check if this combination is
- % better the best combination previosly found, if so then we overwrite it
- %
- % then we have to remove one or more submatrices from the combination (depending on
- % how many nested for loops are about to be closed)
- % and compute another combination
- % to 'remove one or more submatrices from the combination' it is necessary to do these things:
- % - reduce the area
- % - reduce the combination
- % - reduce the counter
- %
- if isempty(s_copy)
- comb(1,2)=counter; % final no of submatrices in the combination
- comb(1,1)=R*C-area; % no. of cells remained in P after removing the cells contained in the submatrices of the combination
- % if the combination just found is better than the previous overwrite it
- if comb(1,1)<comb(2,1) || (comb(1,1)==comb(2,1) && comb(1,2)<comb(2,2))
- comb(2,:)=comb(1,:);
- disp(['[area_left] ', num2str(comb(2,1)), ' [slices] ', num2str(comb(2,2))])
- printed=true;
- end
- area=area-k; % tot area of the combination excluding the last sumatrix
- if ~isempty(v) && ~hold_on % more than one submatrix must be removed
- i=size(v,2);
- if i>length(find(v)) % if v contains at least one 0
- while v(i)==1 % find the index of the last 0
- i=i-1;
- end
- last_i_counter=size(v(i+1:end),2); % no. of consecutive for loop that are about to end
- v=v(1:i-1);
- else
- last_i_counter=i;
- v=[];
- end
- for i=1:last_i_counter
- area=area-s(comb(1,2+counter-i),5); % reduce the area
- end
- comb(1,2+counter-last_i_counter:2+counter)=0; % remove submatrices from the combination
- counter=counter-(last_i_counter+1); % reduce the counter
- hold_on=true;
- else % exactly one submatrix must be removed
- comb(1,2+counter)=0;
- counter=counter-1;
- end
- % USED TO SHOW THAT WITHOUT s_ovrlppd(s_ovrlppd(:,6)<pos,:)=[]; THERE ARE
- % LOT OF REPEATING COMBINATIONS
- % if isempty(s_copy)
- % comb(size(comb,1)+1,:)=comb(1,:);
- % comb(size(comb,1),2)=counter; % final no of slices in the combination
- % comb(size(comb,1),1)=R*C-area; % no. of cells remained in P after removing the cells contained in the slices of the combination
- %
- % area=area-k;
- % if first_for_i == 34
- % comb(1:2,:)=[];
- % end
- % if ~isempty(v) && ~hold_on
- % i=size(v,2);
- % if i>length(find(v))
- % while v(i)==1
- % i=i-1;
- % end
- % last_i_counter=size(v(i+1:end),2);
- % v=v(1:i-1);
- % else
- % last_i_counter=i;
- % v=[];
- % end
- % for i=1:last_i_counter
- % area=area-s(comb(1,2+counter-i),5);
- % end
- % comb(1,2+counter-last_i_counter:2+counter)=0;
- % counter=counter-(last_i_counter+1);
- % hold_on=true;
- % else
- % comb(1,2+counter)=0;
- % counter=counter-1;
- % end
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- %%% FIND COMBINATIONS %%%
- %%%%%%%%%%%%%%%%%%%%%%%%%%%%%
- else
- for i = 1:size(s_copy,1) % fix the i-th submatrix
- % if the combination cover all elements of P & the no. of submatrices is the minimum possibile
- if comb(2,1)==0 && comb(2,2)==ceil(R*C/H)
- perfect=true;
- return
- end
- pos=s_copy(i,6); % position of current submatrix in s
- comb(1,3+counter)=pos; % add the position to the combination
- k=s(pos,5); % save the area of the current submatrix
- area=area+k; % area covered with all the submatrices of the combination up now
- counter=counter+1;
- % if the area in P covered by the current combination could not
- % be bigger than the best combination found up now, then discard
- % the current combination and consider the next one
- if R*C-area-(max_no_subm-counter)*H > comb(2,1) && i < size(s_copy,1)
- % R*C-area-(max_no_subm-counter)*H can be negative if ceil(R*C/H) < max_no_subm
- counter=counter-1;
- comb(1,3+counter)=0;
- area=area-k;
- else
- s_ovrlppd=s_copy; % initializing the set of non-overlapping submatrices
- s_ovrlppd(s_copy(:,1)<=s_copy(i,2) & s_copy(:,2)>=s_copy(i,1) & s_copy(:,3)<=s_copy(i,4) & s_copy(:,4)>=s_copy(i,3),:)=[]; % delete submatrices that overlap the i-th one
- s_ovrlppd(s_ovrlppd(:,6)<pos,:)=[]; % remove submatrices that will generate combinations already studied
- % KEEP TRACK OF THE NESTED 'FOR' LOOPS ENDS REACHED
- if i==size(s_copy,1) % if i is the last cycle of the current for loop
- v(size(v,2)+1)=1; % a 1 means that the code entered the last i of a 'for' loop
- if size(s_ovrlppd,1)~=0 % hold on until an empty s_ovrlppd is found
- hold_on=true;
- else
- hold_on=false;
- end
- elseif ~isempty(v) && size(s_ovrlppd,1)~=0
- v(size(v,2)+1)=0; % a 0 means that s_ovrlppd in the last i of a 'for' loop is not empty => a new 'for' loop is created
- end
- %%%%%%%%%%%%%%%%%%%%%%%%
- %%% PRINT STATUS %%%
- %%%%%%%%%%%%%%%%%%%%%%%%
- if size(s_copy,1)==size_s
- ijk(1)=i;
- ijk(2:3)=0;
- % if ~printed && i~=1
- % fprintf(repmat('b',1,numel(num2str(first_for_i))+numel(num2str(second_for_i))+numel(num2str(third_for_i))+2+2+1)) % [] ,, return
- % else
- % printed=false;
- % end
- fprintf('[%d,%d,%d]n',ijk)
- size_s_ovrlppd=size(s_ovrlppd,1);
- first_for_i=i;
- second_for_i=0;
- elseif size(s_copy,1)==size_s_ovrlppd
- ijk(2)=i;
- ijk(3)=0;
- if ~printed
- fprintf(repmat('b',1,numel(num2str(first_for_i))+numel(num2str(second_for_i))+numel(num2str(third_for_i))+2+2+1)) % [] ,, return
- else
- printed=false;
- end
- fprintf('[%d,%d,%d]n',ijk)
- size_s_ovrlppd2=size(s_ovrlppd,1);
- second_for_i=i;
- third_for_i=0;
- elseif size(s_copy,1)==size_s_ovrlppd2
- ijk(3)=i;
- if ~printed
- fprintf(repmat('b',1,numel(num2str(first_for_i))+numel(num2str(second_for_i))+numel(num2str(third_for_i))+2+2+1))
- else
- printed=false;
- end
- fprintf('[%d,%d,%d]n',ijk)
- third_for_i=i;
- end
- [comb,perfect,counter,area,v,hold_on,ijk,printed,first_for_i,second_for_i,third_for_i]=recursion(s,s_ovrlppd,comb,counter,area,R,C,k,hold_on,H,v,size_s,perfect,ijk,size_s_ovrlppd,size_s_ovrlppd2,printed,third_for_i,second_for_i,first_for_i,max_no_subm);
- end
- end
- end
- end
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement