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

7

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 Ai,j denotar o elemento de UMAna iquinta linha e na jcoluna.
  • Deixei S(Eu1 1:Eu2,j1 1:j2) denota a soma ideal de números não sobrepostos para um subarray quadrado de UMA contendo a interseção de linhas Eu1 1 para Eu2 e colunas j1 1 para j2.

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{S(2:n,2:n)+A1,1S(2:n,1:n1)+A1,nS(1:n1,2:n)+An,1S(1:n1,1:n1)+An,n
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?

Li-aung Yip
fonte
Mas qual é a complexidade temporal do seu algoritmo?
11
Correspondência máxima?
Aryabhata
@SaeedAmiri: Obrigado pela marcação LaTeX. E teria sido O(N^3)se funcionasse, exceto que não funciona. Tão pooh.
Li-aung Yip
A menos que eu esteja entendendo mal alguma coisa, uma redução direta do Travelling Salesman implica que o problema original é NP-difícil!
JeffE
@ Jeff: Você poderia elaborar em forma de resposta?
Li-aung Yip

Respostas:

7

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.

jpalecek
fonte
Ai. Condenação.
Li-aung Yip
5

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 UMA e B. Cada vérticeumaEuUMA corresponde a uma linha e cada vértice bjBcorresponde a uma coluna. O peso da bordaEEu,j entre umaEu e bj é MEu,j, a j-ésimo elemento de Eu-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 serWmumax. Então você deve classificar todos os elementos na matrizMe faça uma pesquisa binária nele. Ao testar o valorm, ou seja, se existe uma correspondência máxima cujo elemento mínimo não seja menor que m, você deve modificar tudo MEu,j para - E se MEu,j<m e encontre a correspondência máxima Wmumax na matriz modificada M. Wmumax=Wmumax se houver uma solução cujos elementos min em nada menos que m.

Wu Yin
fonte