der Suche nach Matrizen in Matlab

Question

Mein Problem ist wie folgt:

Ich habe die folgenden Matrizen:

0 1 
    1 1 

oder

1 1 1 
    1 1 1 
    0 1 0 

oder

1 1 1 0 
    1 1 1 1 
    0 1 1 0 

Und ich will um die folgenden Matrizen zu erhalten:

0 1 
    2 1 

oder

1 1 1 
    1 1 1 
    0 2 0 

oder

1 1 1 0 
    1 1 1 2 
    0 3 3 0 

Was ich will, ist die Sub-Matrizen (oder col-Vektor oder Zeilenvektor im Fall, dass Untermatrizen nicht möglich ist) zu erhalten, wie groß wie möglich.

Ich gehe eindeutig erklären:

Wenn die Eingabe die dritte Matrix ist:

1 1 1 0 
    1 1 1 1 
    0 1 1 0 

ich Gruppenelemente will vertikal oder horizontal, diese Untermatrizen so groß wie möglich zu machen. Die größte Submatrix in diesem Beispiel:

x x x 0 
    x x x 1 
    0 1 1 0 

Eine weitere mögliche Submatrix, das ist auch am größten ist:

1 x x 0 
    1 x x 1 
    0 x x 0 

Sowohl durch x vertreten.

Dann gibt es drei Elemente mit 1, noch. Also ich möchte wieder gruppieren. Die größten Submatrizen (oder Untervektoren) erneut abrufen. An diesem Punkt in Abhängigkeit von der vorherige Bewegung, wir bekommen:

x x x 0 
    x x x 1 
    0 y y 0 

oder

y x x 0 
    y x x 1 
    0 x x 0 

Vertreten durch y.

Jetzt haben wir ein weiteres Element, das nicht ist, gruppiert hat, und jetzt machen wir eine andere Gruppe (dargestellt durch z):

y x x 0 
    y x x z 
    0 x x 0 

Wenn wir jetzt einen anderen Eingang wählen, haben wir die folgenden Schritte:

0 1 
    1 1 

wir haben zwei Untervektor, also haben wir zwei mögliche Lösungen:

0 1 
    x x 

oder

0 x 
    1 x 

Und dann, abhängig von der gewählten Lösung, haben wir die folgende Lösung:

0 y 
    x x 

oder

0 x 
    y x 

allein das andere Element Gruppierung.

schließlich im zweiten Fall haben wir nur eine mögliche Lösung:

1 1 1 
    1 1 1 
    0 1 0 

gibt es die größte Submatrix haben wir diese Lösung:

x x x 
    x x x 
    0 1 0 

Und dann, Gruppe das letzte Element allein:

x x x 
    x x x 
    0 y 0 

Vielen Dank im Voraus.

Answer 1

Es wird nicht schnell sein, aber roher Zwang würde Ihren Weg durchgehen (für kleine Probleme). Pseudo-Code wie:

A = [1, 0; 1, 1]; 
B = zeros(size(A)); 
bCount = 1; 
while any(A ~= 0) 
globalmax = 0; 
for i,j = 1 : sizeOfMatrix 
    localmax = 0; 
    for ii,jj = i,j : sizeOfMatrix 
     if ((ii-i+1) * (jj-j+1) > localmax ... && 
      && all(A(i:ii, j:jj) ~= 0)) 
      localmax = (ii-i+1) * (jj-j+1); 
      localmaxPoints = [i, ii; j, jj]; 
     end 
    end 
    if (localmax > globalmax) 
     globalmax = localmax; 
     globalmaxPoints = localmaxPoints; 
    end 
end 
A[globalmaxPoints] = 0; 
B[globalmaxPoints] = bCount; 
bCount = bCount+1; 
end 

Hinweis: dieser Code nicht direkt funktionieren, aber es sollte einfach sein, es zu beheben. Offensichtlich ist der Ansatz nur für kleine Matrizen geeignet - zu langsam für alles Große. Es gibt einige kleine Optimierungen, die trivial sind, aber nicht viel ändern werden.

Sie benötigen etwas Besseres, um das Optimum für eine riesige Matrix zu finden. Wenn Sie nicht über einige Eigenschaften in diesen Matrizen verfügen, die Sie verwenden könnten (z. B. sind Nullen nur entlang der Kanten vorhanden), müssen Sie Optimierungstechniken verwenden. Sie werden vielleicht nicht die optimale Lösung bekommen, aber es wird eine sehr gute sein.