I would like to know if the problem could be solved at all in Matlab or maybe any toolboxes would be of any help since for a 30*30 square matrix , there are 30! possible ways the rows can be sorted to find out this maximum non negative values next to the diagonal
Sorting to have continuous non negative values next to diagonal of square matrix
1 次查看(过去 30 天)
显示 更早的评论
Hello
I have a square matrices of different sizes. I want to reorder the rows of the matrix in such a way that I get the maximum number of continuous nonnegative values at the positions occurring immediately to the next of the diagonal matrix. The diagonal of the matrix will always be -1.
For example in square matrix 5*5
% 1 2 3 4 5
[-1 1 2 -1 3 % 1
0 -1 -1 -1 4 % 2
5 -1 -1 6 7 % 3
-1 -1 8 -1 9 % 4
10 11 12 13 -1] % 5
In this case I want maximum number of continuous non negative values on the positions (1,2),(2,3),(3,4),(4,5). Currently we can see that (1,2) has a positive value and since (2,3) has a negative value. But if we rearrange the rows then we can have more continuous values.
One more point to be noted is that the values in the rows and column are interlinked. What I mean by this is that suppose you swap rows 2 and 5 , then you need to swap columns 2 and 5 as well. This will ensure that diagonal matrix will remain -1.
If we do this we get
% 1 2 3 4 5
[-1 3 2 -1 1 % 1
10 -1 12 13 11 % 2
5 7 -1 6 7 % 3
-1 9 8 -1 -1 % 4
0 4 -1 -1 -1] % 5
We swap rows 2 and 5 first and then followed by swapping columns 2 and 5, we have 3 continuous non negative values at (1,2),(2,3) and (3,4).
% 1 2 3 4 5
[-1 9 8 -1 -1 % 1
13 -1 12 10 11 % 2
6 7 -1 5 -1 % 3
-1 3 2 -1 1 % 4
-1 4 -1 0 -1] % 5
And if we swap rows 1 and 4 and also columns 1 and 4 , we get continuous values at all 4 positions and by sorting in such a way we get maximum of continuous non negative values.
Note that I just want to get the maximum of continuous non negative values, may be in another example for a 5*5 matrix, it could just have 1 or 2 continuous values, but that should be the maximum.
I hope I have explained my problem and any help would be appreciated. This is just an example and I have square matrices of the size 30*30 on which I need to perform the operation.
采纳的回答
Matt J
2014-11-17
编辑:Matt J
2014-11-17
The code below does the job, I believe. Or at least, I find that it works with all of your sample inputs, and with a worst case time of 8.5 seconds on my machine (for Input_six).
Note that the sorting problem really turns out to be a Longest Path Problem which is known to be NP-hard. Therefore, sparsity of the non-negative values is key to keeping the computation time low.
function [Msorted,rowperm] = mySort(M)
%Sorts input M to achieve a maximum length string of non-negative values on
%diag(Msorted,1). Optionally, also, returns "rowperm", an index vector
%satisfying
%
% Msorted=M(rowperm,rowperm)
n=size(M,1);
p=LongestPath(M>=0);
rowperm=[p,setdiff(1:n,p)];
Msorted=M(rowperm,rowperm);
function out=LongestPath(G,options)
%Finds a longest path through adjacency matrix, G
if nargin<2
options=1:size(G,1);
end
m=length(options);
c=cell(m,1);
for i=1:m
j=options(i);
tmp=G;
tmp(:,j)=0;
suboptions=find(tmp(j,:));
if isempty(suboptions)%nowhere to go
c{j}=j;
else
c{j}=[j,LongestPath(tmp,suboptions)];
end
end
L=cellfun('length',c);
[~,idx]=max(L);
out=c{idx};
更多回答(2 个)
Guillaume
2014-11-10
编辑:Guillaume
2014-11-11
I'm really not familiar with this problem domain (optimisation). The only way I can think of doing what you want is to try all the permutations and see which one is the best. This is only reasonable for small matrices otherwise computation time will be prohibitive.
You would use perms to generate all possible combinations of row/column indices and diag to extract the diagonal for testing:
function bestm = findbest()
m =[-1 1 2 -1 3 % 1
0 -1 -1 -1 4 % 2
5 -1 -1 6 7 % 3
-1 -1 8 -1 9 % 4
10 11 12 13 -1]; % 5
diagcount = countcontinuous(diag(m, 1));
bestm = m;
allcombs = perms(1:size(m, 1));
for comb = allcombs'
mswappedrow=m(comb, :);
mswapped = mswappedrow(:, comb);
count = countcontinuous(diag(mswapped, 1));
if count > diagcount
diagcount = count;
bestm = mswapped;
end
if count == size(m, 1)-1
break; %it's the maximum possible anyway
end
end
function count = countcontinuous(diagonal)
positive = diagonal' > 0;
transitions = diff([0 positive 0]); % a 1 is a transition from 0 to 1, a -1 from 1 to 0
%because we've put a 0 before and after we're sure to have the same number of transitions
%from 0 to 1 and from one to 0
runlength = find(transitions == -1) - find(transitions == 1);
count = max(runlength);
end
Matt J
2014-11-11
编辑:Matt J
2014-11-11
I'm not sure how robust an approach this is, but it did give me one of the non-unique solutions to your posted example
result =
-1 6 7 -1 5
8 -1 9 -1 -1
12 13 -1 11 10
-1 -1 4 -1 0
2 -1 3 1 -1
Basically, the idea is to use fmincon from the Optimization Toolbox to solve this as a nonlinear minimization problem. The code below searches for the permutation matrix P such that if A is the original matrix, then the permuted off-diagonal
b=diag(P*(A>=0)*P.',1)
will have a large sum and be smooth. I would have liked to have added the nonlinear constraint
P*P.'-eye(size(P))=0
to enforce the fact that P should be orthogonal, but when I do that, I find the optimization gets trapped very easily at local minima or non-solutions. Not so surprising, since this is a highly non-convex constraint. Without the non-linear constraint, though, the whole thing is really a quadratic program, and quadprog() would probably perform even better. I wouldn't take the trouble to recast the input data into quadprog's syntax until you're sure that it's working, though.
A= [-1 1 2 -1 3 % 1
0 -1 -1 -1 4 % 2
5 -1 -1 6 7 % 3
-1 -1 8 -1 9 % 4
10 11 12 13 -1] % 5 ]
n=size(A,1);
map=(A>=0);
Aeq= [kron(speye(n), ones(1,n));... %column sum
kron(ones(1,n), speye(n))]; %row sum
beq=ones(2*n,1);
lb=zeros(size(A));
ub=ones(size(A));
[P0,fval] = fmincon(@(P) cost(P,map),speye(n),[],[],Aeq,beq,lb,ub);
P=double(bsxfun(@ge,P0,max(P0,[],2))); %round to nearest permutation matrix
if any(Aeq*P(:)-beq) %check that it is a permutation
error 'Approximate permutation not found'
end
result=P*A*P.',
function f=cost(P,map)
b=diag(P*map*P.',1);
f=sum(diff(b).^2)-sum(b);
另请参阅
类别
在 Help Center 和 File Exchange 中查找有关 Linear Programming and Mixed-Integer Linear Programming 的更多信息
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!