Maximize a soma de números "sem sobreposição" em uma matriz quadrada - ajude com a prova

Uma pergunta foi postada no Stack Overflow solicitando um algoritmo para resolver esse problema:

Eu tenho uma matriz (chame de A) que é nxn. Desejo selecionar um subconjunto (denominado B) de pontos da matriz A. O subconjunto consistirá em n elementos, nos quais um e apenas um elemento é obtido de cada linha e de cada coluna de A. A saída deve fornecer uma solução ( B) de modo que a soma dos elementos que compõem B seja o valor máximo possível, dadas essas restrições (por exemplo, 25 no exemplo abaixo). Se várias instâncias de B forem encontradas (ou seja, soluções diferentes que dão a mesma soma máxima), a solução para B que possui o maior elemento mínimo deve ser selecionada.

B também pode ser uma matriz de seleção que é nxn, mas onde apenas os n elementos desejados são diferentes de zero.

Por exemplo: se 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 seria

 |5 5 5 5 5|

I propôs uma solução de programação dinâmica que eu suspeito é tão eficiente quanto qualquer solução vai ficar. Copiei e colei meu algoritmo proposto abaixo.

---

• Deixei $A$ ser uma matriz quadrada de $n$ de $n$ números.
• Deixei $A_{i,j}$ denotar o elemento de $A$na iquinta linha e na jcoluna.
• Deixei $S( i_1:i_2, j_1:j_2 )$ denota a soma ideal de números não sobrepostos para um subarray quadrado de $A$ contendo a interseção de linhas $i_1$ para $i_2$ e colunas $j_1$ para $j_2$.

Em seguida, a soma ideal de números não sobrepostos é indicada S( 1:n , 1:n )e é apresentada da seguinte forma:

$$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.

Ou seja, a soma ideal para uma matriz quadrada de tamanho npode ser determinada calculando separadamente a soma ideal para cada uma das quatro sub-matrizes de tamanho n-1e maximizando a soma da sub-matriz e do elemento "deixado de fora" "

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

Is the best of the sums S for:

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

---

Esse é um algoritmo muito elegante e eu suspeito fortemente que esteja correto, mas não consigo encontrar uma maneira de provar que está correto.

A principal dificuldade que estou enfrentando é provar que o problema exibe uma subestrutura ideal. Acredito que, se as quatro escolhas possíveis em cada cálculo são as únicas quatro opções, isso é suficiente para mostrar a subestrutura ideal. Ou seja, preciso provar que isso:

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

Não é uma solução válida, seja porque é impossível (ou seja, prova por contradição) ou porque essa possibilidade já é explicada por uma das quatro n-1variações "quadradas".

Alguém pode apontar alguma falha no meu algoritmo ou fornecer uma prova de que realmente funciona?

Na verdade, não acredito que sua solução proposta esteja correta. Um exemplo em que você pode precisar desse caso

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

pode ser

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

A solução ideal consiste em todos os 2s, enquanto houver apenas 1s nos cantos; portanto, você não pode encontrar uma solução ideal apenas começando pelas esquinas.

Esse problema pode ser resolvido pelo algoritmo de correspondência máxima no gráfico bipartido ponderado, como o algoritmo de Kuhn-Munkres ou o algoritmo de fluxo de custo mínimo.

Imagine um gráfico bipartido $G$, cujos dois conjuntos de pontos separados são $A$ e $B$. Cada vértice$a_i \in A$ corresponde a uma linha e cada vértice $b_j \in B$corresponde a uma coluna. O peso da borda$E_{i,j}$ entre $a_i$ e $b_j$ é $M_{i, j}$, a $j$-ésimo elemento de $i$-a linha da matriz. A correspondência máxima ponderada deste gráfico corresponde a uma solução para o seu problema.

Para quebrar o empate, primeiro você precisa encontrar o valor da correspondência ponderada máxima. Deixe o valor ser$W_{max}$. Então você deve classificar todos os elementos na matriz$M$e faça uma pesquisa binária nele. Ao testar o valor$m$, ou seja, se existe uma correspondência máxima cujo elemento mínimo não seja menor que $m$, você deve modificar tudo $M_{i, j}$ para $-\infty$ E se $M_{i, j} < m$ e encontre a correspondência máxima $W_{max}'$ na matriz modificada $M'$. $W_{max}' = W_{max}$ se houver uma solução cujos elementos min em nada menos que $m$.