Reduzierung der zeitlichen Komplexität in der maximalen Minimalsumme 2-Partitionierung eines Arrays

9

Lassen Sie array[N] ein Array von N nicht-negativen Werten. Wir versuchen, das Array rekursiv in zwei (2) Sub-Arrays zu partitionieren, so dass wir die maximale "Minimum-Summe" jedes Sub-Arrays erreichen können. Die Lösung wird durch die folgende Rekursion beschrieben:

Wir wollen opt[0][N-1] berechnen.

Lassen Sie c[x][y] die sum{array[i]} von x bis y (einschließlich) angeben. Ich habe es geschafft, die Rekursion im folgenden C ++ - Code-Snippet mit dynamischer Programmierung abzuwickeln:

%Vor%

Diese Technik analysiert alle Unterfelder, beginnend mit der Größe 1 und bis zur Größe N . Die endgültige Lösung wird somit in opt[0][N-1] gespeichert.

Beispiel: Wenn N=6 , wird die Matrix wie folgt iteriert: (0,0) (1,1) (2,2) (3,3) (4,4) (5,5) (0,1) (1,2) (2,3) (3,4) (4,5) (0,2) (1,3) (2,4) (3,5) (0,3) (1,4) (2,5) (0,4) (1,5) (0,5) . Die endgültige Antwort wird in opt[0][5] sein.

Ich habe getestet und verifiziert, dass die obige Technik funktioniert, um die Rekursion aufzuheben. Ich versuche die Komplexität weiter zu reduzieren, da dies in O (n ^ 3) laufen wird, wenn ich richtig liege. Konnte das erreicht werden?

edit: Ich merke auch die physikalische Bedeutung der Rekursion, wie sie in den Kommentaren gefragt wurde. Lassen Sie N für N Städte auf einer geraden Linie stehen. Wir sind ein Vermieter, der diese Städte kontrolliert; Am Ende eines Jahres zahlt jede Stadt i einen Vorrat an array[i] -Münzen, solange sie unter unserer Kontrolle steht.

Unsere Städte werden von einer überlegenen Macht angegriffen und eine Niederlage ist unvermeidlich. Zu Beginn jedes Jahres errichten wir eine Mauer zwischen zwei benachbarten Städten i , i+1 , x <= i <= y . Während jedes Jahres greifen die feindlichen Truppen entweder von Westen her an und erobern somit alle Städte in [x,i] , oder sie greifen aus dem Osten an und erobern somit alle Städte in [i+1,y] . Die verbleibenden Städte werden uns Ende des Jahres ihren Unterhalt zahlen. Die feindlichen Kräfte zerstören die Mauer am Ende des Jahres, ziehen sich zurück und starten im nächsten Jahr einen neuen Angriff. Das Spiel endet, wenn nur noch eine Stadt steht.

Die feindlichen Kräfte werden immer von der optimalen Position angreifen, um unser maximales Einkommen im Laufe der Zeit zu reduzieren. Unsere Strategie ist, die optimale Position der Wand zu wählen, um unser Gesamteinkommen am Ende des Spiels zu maximieren.

    
Adama 22.12.2014, 08:56
quelle

1 Antwort

1

Hier ist die endgültige Antwort auf das Problem, nach dem Beitrag von @NiklasB. . % Co_de% bezeichnet die optimale Partition eines Arrays für das Problem w(x,y) . Wie folgt, opt[x][y] . Wir nehmen an, dass die Positionen für alle Teilprobleme x <= w(x,y) < y mit einer gegebenen Subarray-Größe opt[x][y] bekannt sind.

Versuchen wir nun, die optimalen d = y-x -Positionen für alle Teilprobleme der Größe w zu finden. Wir können leicht beweisen, dass k+1 ; IOW, wenn wir ein weiteres Element rechts hinzufügen, könnte die optimale Partition "nach rechts" verschoben werden, um die beiden Summen ausgeglichener zu machen; es kann sich jedoch nicht "nach links bewegen". Auf ähnliche Weise w(x,y+1) >= w(x,y) .

NB: Es wäre hilfreich, wenn jemand versuchen könnte, das Obige mathematisch zu überprüfen.

Lassen Sie wie folgt w(x-1,y) <= w(x,y) die optimale wall[x][y] -Lösung für das Teilproblem w anzeigen. Loop opt[x][y] im Original-Snippet wird wie folgt geändert:

%Vor%

Einige wenige Modifikationen sind erforderlich, um mit den Fällen in der Ecke umzugehen, wenn for ( uint16_t w = x; w < y; w ++ ) , aber es macht den Job. Es reduziert die Laufzeitkomplexität von O (n ^ 3) nach O (n ^ 2), da die Zeit für die Berechnung der Lösung für ein größeres Teilproblem amortisiert wird, indem die Grenzen 0 <= y-x <= 1 berücksichtigt werden. Beispiel: Mit w wird der rekursive Algorithmus (mit Memo) in 58 Sekunden ausgeführt. Der O (n ^ 2) -Algorithmus läuft nur in 148 ms.

    
Adama 22.12.2014, 21:27
quelle