Ich muss den Unterschied zwischen der Summe von 4 Submatrizen finden, die ich bekomme, nachdem ich die Matrix A in irgendeiner Weise geteilt habe, um die geringste Differenz zwischen der Summe der Submatrizen zu erhalten. Matrix.
Zum Beispiel für eine Matrix A ,
%Vor%Ich könnte es so aufteilen:
%Vor%Die Summe aller Elemente innerhalb jeder Untermatrix ergibt das folgende Ergebnis:
%Vor%Danach berechne ich alle möglichen absoluten Unterschiede zwischen den Summen, d. h.
%Vor%Schließlich wählte ich die maximale Entfernung, die 5 ist.
Wenn ich jedoch die Matrix A auf andere Weise aufspalte, ergibt sich eine andere maximale Entfernung, die ich nicht möchte. Ich muss nur 5 finden, aber wenn ich diese rohe Gewalt anwende, verbringe ich einfach zu viel Zeit damit, alle Möglichkeiten zu finden. Hat dieses Problem einen Namen, oder können Sie mir einen Hinweis geben?
HINZUGEFÜGT
Die zulässigen Splits sind eine horizontale Teilung, gefolgt von einer vertikalen Teilung oberhalb und einer möglicherweise anderen vertikalen Teilung unterhalb der horizontalen Teilung. 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 solcher Paare geben) und die größte Differenz zwischen den Summen der Elemente einer der Submatrizen nehmen des Paares und der Summe der Elemente der anderen Teilmatrix des Paares. Wir möchten das Minimum über alle maximalen Unterschiede finden.
Die tatsächliche Matrix kann bis zu 4000 x 4000 betragen.
Es gibt einige Beschleunigungen über die rohe Gewalt. 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 einem beliebigen 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 gezeichnet hat, 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. Das 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 Teilungen auf derselben Seite einer horizontalen Teilung haben, müssen Sie nicht alle Paare von Positionen für die vertikalen Teilungen ausprobieren: Sie können mit der äußersten linken Teilung ganz links beginnen und anpassen die rechte Spalte, 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 Split-Muster die minimale Kostenaufteilung dieses Musters in der Zeit finden, wenn Sie die Position der längsten Linie in diesem Muster angeben, die O (N) 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 Punkt aufzubauen , die Zeit in der Gesamtzahl der Zellen in der Matrix linear nimmt, oder O (N ^ 2) für eine quadratische Matrix von Seite N. - aber es ist ärgerlich, dass dort sechs verschiedene Split-Muster erscheinen.