Split-Matrix in 4 Sub-Matrizen mit dem niedrigsten Unterschied zwischen ihrer Summe

Question

Ich muss den Unterschied zwischen der Summe von 4 Sub-Matrizen, die ich nach dem Aufteilen der Matrix A in irgendeiner Weise, um zu erhalten niedrigste Differenz zwischen der Summe der Sub-Matrix.

Zum Beispiel für eine Matrix A,

3 0 2 -8 -8 
5 3 2 2 3 
2 5 2 1 4 
3 4 -1 4 2 
-3 6 2 4 3 

ich es wie folgt aufgeteilt könnte:

3 | 0 2 -8 -8 
5 | 3 2 2 3 
2 | 5 2 1 4 
------------------- 
3 4 -1 | 4 2 
-3 6 2 | 4 3 

Die Summe aller Elemente innerhalb jeder Untermatrix ergibt folgendes Ergebnis:

10 | 8 
------- 
11 | 13 

Danach berechne ich alle möglichen absoluten Unterschiede zwischen den Summen, d.h.

abs(10 - 8) = 2 
abs(10 - 11) = 1 
abs(10 - 13) = 3 
abs(8 - 11) = 3 
abs(8 - 13) = 5 
abs(11 -13) = 2 

Schließlich habe ich den maximalen Abstand gewählt, der ist.

Allerdings, wenn ich die Matrix A auf andere Weise aufteilen, wird es eine andere maximale Entfernung geben, die ich nicht will. Ich muss nur finden, aber wenn ich diese rohe Kraft mache, verbringe ich einfach zu viel Zeit damit, alle Möglichkeiten zu finden. Hat dieses Problem einen Namen oder kannst du mir einen Hinweis geben?

ADDED

Die zulässigen Splits sind eine horizontal durch eine vertikale Teilung gefolgt Split oberhalb und einer gegebenenfalls unterschiedlichen vertikale Teilung unterhalb der horizontalen Split. Im Beispiel gibt es 4 x 4 x 4 = 64 zulässige Partitionen der Matrix.

Der maximale Unterschied zwischen den Submatrizen einer bestimmten Partition wird gebildet, indem alle Paare der 4 Submatrizen dieser Partition berücksichtigt werden (es wird 6 solche Paare geben) und die größte Differenz zwischen den Summen der Elemente eines der Submatrizen des Paares und die Summe der Elemente der anderen Submatrix des Paares. Wir möchten das Minimum über alle maximalen Unterschiede finden.

Die eigentliche Matrix bis zu 4000 sein kann, x 4000.

Answer 1

Es gibt einige Speed-ups über Brute-Force. Zuallererst können Sie, indem Sie Summen in Zeilen und dann in Spalten aufaddieren, eine Tabelle erstellen, die für jeden Punkt die Gesamtsumme aller Punkte einschließlich des einen, nicht weiter oben als dieses und nicht weiter rechts als dieses gibt. Dann können Sie die Summe in jedem Rechteck berechnen, indem Sie höchstens vier dieser Zwischensummen subtrahieren: grob gesagt die Summe von der oberen rechten Ecke plus die Summe von der unteren linken Ecke minus den Summen von den anderen zwei Ecken.

Für das Split-Muster, das das OP grafisch darstellt, mit einer horizontalen Linie, die die gesamte Matrix aufteilt, gefolgt von verschiedenen vertikalen Linien, die sich in jeder Hälfte teilen, müssen die vertikalen Teilungen die gleichmäßigste vertikale Teilung ihrer Hälfte sein. Wenn der extremste Unterschied zwischen Summen innerhalb einer vertikalen Teilung ist, können die vertikalen Aufspaltungen abends nur verbessern. Wenn der extremste Unterschied zwischen den Summen zwischen (zum Beispiel) einer hohen Summe von oben links und einer niedrigen Summe unten rechts liegt, dann wird eine vertikale Aufspaltung entweder die hohe Summe nach unten oder die niedrige Summe nach oben bringen der extremste Unterschied.Dies bedeutet, dass Sie nur die beste Aufteilung in der oberen Hälfte und die beste Aufteilung in der unteren Hälfte berücksichtigen müssen - Sie müssen nicht alle Paare von Aufteilungen berücksichtigen.

Für den Fall, dass Sie zwei vertikale Splits auf der gleichen Seite eines horizontalen Splits haben, müssen Sie nicht alle Paare von Positionen für die vertikalen Splits versuchen: Sie können mit dem linken Split ganz links beginnen, und Passe die rechte Spalte an, um den Rest so gleichmäßig wie möglich in zwei Teile zu schneiden. Bewegen Sie dann den Split ganz links langsam nach rechts und währenddessen können Sie den Split ganz rechts so einstellen, dass er sich nach rechts bewegt, um den Rest möglichst gleichmäßig aufzuteilen.

Mit diesen Ideen scheint es mir, dass Sie für jedes mögliche Splitmuster die minimale Kostenaufspaltung dieses Musters in der Zeit finden können, wenn Sie die Position der längsten Linie in diesem Muster wählen, die O (N) ist. für eine quadratische Matrix der Seite N, also mit N Positionen für eine längste Linie, die O (N^2) ist, was ungefähr die gleiche Zeit ist, die benötigt wird, um eine Tabelle von Summen von Punkten unterhalb und links von jedem aufzubauen Punkt, der die Zeit linear in der Gesamtzahl der Zellen in der Matrix nimmt, oder O (N^2) für eine quadratische Matrix von Seite N. - aber es ist ärgerlich, dass dort sechs verschiedene Split-Muster erscheinen.