Maximieren Sie die Summe der nicht überlappenden Zahlen im quadratischen Array - helfen Sie beim Beweis

Eine Frage wurde veröffentlicht am Stack - Überlauf für einen Algorithmus zu fragen , dieses Problem zu lösen:

Ich habe eine Matrix (nenne es A), die nxn ist. Ich möchte eine Teilmenge (nennen wir es B) von Punkten aus Matrix A auswählen. Die Teilmenge besteht aus n Elementen, wobei aus jeder Zeile und aus jeder Spalte von A ein und nur ein Element entnommen wird. Die Ausgabe sollte eine Lösung liefern ( B) so, dass die Summe der Elemente, aus denen B besteht, angesichts dieser Einschränkungen der maximal mögliche Wert ist (z. B. 25 im folgenden Beispiel). Wenn mehrere Instanzen von B gefunden werden (dh verschiedene Lösungen, die dieselbe maximale Summe ergeben), sollte die Lösung für B ausgewählt werden, die das größte minimale Element aufweist.

B könnte auch eine Auswahlmatrix sein, die nxn ist, bei der jedoch nur die n gewünschten Elemente ungleich Null sind.

Zum Beispiel: wenn A =

|5 4 3 2 1|
|4 3 2 1 5|
|3 2 1 5 4|
|2 1 5 4 3|
|1 5 4 3 2|

=> B wäre

 |5 5 5 5 5|

Ich schlug eine dynamische Programmierlösung vor, von der ich vermute, dass sie so effizient ist wie jede andere Lösung. Ich habe meinen vorgeschlagenen Algorithmus unten kopiert.

---

• Lassen $A$ sei eine quadratische Anordnung von $n$ durch $n$ Zahlen.
• Lassen $A_{i,j}$ bezeichnen das Element von $A$in der idritten Zeile und jSpalte.
• Lassen $S( i_1:i_2, j_1:j_2 )$ bezeichnen die optimale Summe nicht überlappender Zahlen für ein quadratisches Subarray von $A$ enthält den Schnittpunkt von Zeilen $i_1$ zu $i_2$ und Spalten $j_1$ zu $j_2$.

Dann wird die optimale Summe nicht überlappender Zahlen bezeichnet S( 1:n , 1:n )und wie folgt angegeben:

$$S( 1:n , 1:n ) = \max \left \{ \begin{array}{l} S( 2:n , 2:n ) + A_{1,1} \\ S( 2:n , 1:n-1 ) + A_{1,n} \\ S( 1:n-1 , 2:n ) + A_{n,1} \\ S( 1:n-1 , 1:n-1 ) + A_{n,n} \\ \end{array} \right.$$

Note that S( i:i, j:j ) is simply Aij.

Das heißt, die optimale Summe für ein quadratisches Array der Größe nkann bestimmt werden, indem die optimale Summe für jedes der vier Sub-Arrays der Größe separat berechnet n-1wird und dann die Summe des Sub-Arrays und des Elements maximiert wird, das "weggelassen" wurde ".

S for |# # # #|
      |# # # #|
      |# # # #|
      |# # # #|

Is the best of the sums S for:

|#      |      |      #|      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |# # #  |       |  # # #|
|  # # #|      |# # #  |      |      #|       |#      |

---

Dies ist ein sehr eleganter Algorithmus, und ich vermute sehr, dass er korrekt ist, aber ich kann keinen Weg finden, um zu beweisen, dass er korrekt ist.

Die Hauptschwierigkeit besteht darin, zu beweisen, dass das Problem eine optimale Unterstruktur aufweist. Ich glaube, wenn die vier möglichen Auswahlmöglichkeiten in jeder Berechnung die einzigen vier Auswahlmöglichkeiten sind, reicht dies aus, um eine optimale Unterstruktur zu zeigen. Das heißt, ich muss beweisen, dass dies:

|   #    |
| #   # #|
| #   # #| 
| #   # #|

Ist keine gültige Lösung, entweder weil es unmöglich ist (dh ein Beweis durch Widerspruch) oder weil diese Möglichkeit bereits durch eine der vier " n-1quadratischen" Variationen erklärt wird.

Kann jemand auf Fehler in meinem Algorithmus hinweisen oder einen Beweis dafür liefern, dass er wirklich funktioniert?

Eigentlich glaube ich nicht, dass Ihre vorgeschlagene Lösung richtig ist. Ein Beispiel, in dem Sie diesen Fall möglicherweise benötigen

|   #    |
| #   # #|
| #   # #| 
| #   # #|

könnte sein

| 1 2 1 1|
| 2 1 1 1|
| 1 1 1 2| 
| 1 1 2 1|

Die optimale Lösung besteht aus allen 2en, während sich in den Ecken nur 1en befinden. Daher können Sie keine optimale Lösung finden, indem Sie nur an den Ecken beginnen.

Dieses Problem kann durch einen Maximum-Matching-Algorithmus in einem gewichteten zweigliedrigen Graphen wie dem Kuhn-Munkres-Algorithmus oder einem Minimum-Cost-Flow-Algorithmus gelöst werden.

Stellen Sie sich einen zweigeteilten Graphen , dessen zwei disjunkte Punktmengen und . Jeder Scheitelpunkt entspricht einer Zeile, und jeder Scheitelpunkt entspricht einer Spalte. Das Gewicht der Kante zwischen und ist , das te Element der ten Zeile der Matrix. Die gewichtete maximale Übereinstimmung dieses Diagramms entspricht einer Lösung für Ihr Problem.$G$$A$$B$$a_i \in A$$b_j \in B$$E_{i,j}$$a_i$$b_j$$M_{i, j}$$j$$i$

Um das Unentschieden zu lösen, müssen Sie zuerst den Wert der maximal gewichteten Übereinstimmung ermitteln. Der Wert sei . Dann sollten Sie alle Elemente in der Matrix sortieren und eine binäre Suche durchführen. Wenn Sie den Wert testen , dh ob es eine maximale Übereinstimmung gibt, deren minimales Element nicht kleiner als , sollten Sie alle auf ändern wenn und die max finden passend zu in der modifizierten Matrix . wenn es eine Lösung gibt, deren min-Elemente nicht weniger als betragen .$W_{max}$$M$$m$$m$$M_{i, j}$$-\infty$$M_{i, j} < m$$W_{max}'$$M'$$W_{max}' = W_{max}$$m$