algorithm - write - what is pseudocode




Algoritmo de queda de bombas (20)

Mathematica Integer Linear Programming usando branch-and-bound

Como já foi mencionado, este problema pode ser resolvido usando programação linear inteira (que é NP-Hard ). O Mathematica já possui o ILP embutido. "To solve an integer linear programming problem Mathematica first solves the equational constraints, reducing the problem to one containing inequality constraints only. Then it uses lattice reduction techniques to put the inequality system in a simpler form. Finally, it solves the simplified optimization problem using a branch-and-bound method."[Veja Tutorial de Otimização Restrita no Mathematica ..]

Eu escrevi o seguinte código que utiliza bibliotecas ILP do Mathematica. É surpreendentemente rápido.

solveMatrixBombProblem[problem_, r_, c_] := 
 Module[{}, 
  bombEffect[x_, y_, m_, n_] := 
   Table[If[(i == x || i == x - 1 || i == x + 1) && (j == y || 
        j == y - 1 || j == y + 1), 1, 0], {i, 1, m}, {j, 1, n}];
  bombMatrix[m_, n_] := 
   Transpose[
    Table[Table[
      Part[bombEffect[(i - Mod[i, n])/n + 1, Mod[i, n] + 1, m, 
        n], (j - Mod[j, n])/n + 1, Mod[j, n] + 1], {j, 0, 
       m*n - 1}], {i, 0, m*n - 1}]];
  X := x /@ Range[c*r];
  sol = Minimize[{Total[X], 
     And @@ Thread[bombMatrix[r, c].X >= problem] && 
      And @@ Thread[X >= 0] && Total[X] <= 10^100 && 
      Element[X, Integers]}, X];
  Print["Minimum required bombs = ", sol[[1]]];
  Print["A possible solution = ", 
   MatrixForm[
    Table[x[c*i + j + 1] /. sol[[2]], {i, 0, r - 1}, {j, 0, 
      c - 1}]]];]

Para o exemplo fornecido no problema:

solveMatrixBombProblem[{2, 3, 4, 7, 1, 1, 5, 2, 6, 2, 4, 3, 4, 2, 1, 2, 1, 2, 4, 1, 3, 1, 3, 4, 1, 2, 1, 4, 3, 2, 6, 9, 1, 6, 4}, 7, 5]

Saídas

Para quem lê isso com um algoritmo guloso

Tente seu código no seguinte problema 10x10:

5   20  7   1   9   8   19  16  11  3  
17  8   15  17  12  4   5   16  8   18  
4   19  12  11  9   7   4   15  14  6  
17  20  4   9   19  8   17  2   10  8  
3   9   10  13  8   9   12  12  6   18  
16  16  2   10  7   12  17  11  4   15  
11  1   15  1   5   11  3   12  8   3  
7   11  16  19  17  11  20  2   5   19  
5   18  2   17  7   14  19  11  1   6  
13  20  8   4   15  10  19  5   11  12

Aqui é separado por vírgula:

5, 20, 7, 1, 9, 8, 19, 16, 11, 3, 17, 8, 15, 17, 12, 4, 5, 16, 8, 18, 4, 19, 12, 11, 9, 7, 4, 15, 14, 6, 17, 20, 4, 9, 19, 8, 17, 2, 10, 8, 3, 9, 10, 13, 8, 9, 12, 12, 6, 18, 16, 16, 2, 10, 7, 12, 17, 11, 4, 15, 11, 1, 15, 1, 5, 11, 3, 12, 8, 3, 7, 11, 16, 19, 17, 11, 20, 2, 5, 19, 5, 18, 2, 17, 7, 14, 19, 11, 1, 6, 13, 20, 8, 4, 15, 10, 19, 5, 11, 12

Para este problema, minha solução contém 208 bombas. Aqui está uma solução possível (eu consegui resolver isso em cerca de 12 segundos).

Como forma de testar os resultados que o Mathematica está produzindo, veja se o seu algoritmo guloso pode melhorar.

Eu tenho uma matriz nxm consistindo de inteiros não negativos. Por exemplo:

2 3 4 7 1
1 5 2 6 2
4 3 4 2 1
2 1 2 4 1
3 1 3 4 1
2 1 4 3 2
6 9 1 6 4

"Soltando uma bomba" diminui em um o número da célula alvo e todos os oito vizinhos, para um mínimo de zero.

x x x 
x X x
x x x

O que é um algoritmo que determinaria o número mínimo de bombas necessárias para reduzir todas as células a zero?

Opção B (Devido a eu não ser um leitor atento)

Na verdade, a primeira versão do problema não é a que estou procurando responder. Eu não li cuidadosamente toda a tarefa, há restrições adicionais, digamos:

E quanto ao problema simples, quando a sequência na linha deve ser não crescente:

8 7 6 6 5 é possível seqüência de entrada

7 8 5 5 2 não é possível desde 7 -> 8 crescendo em uma seqüência.

Talvez encontrar uma resposta para um caso "mais fácil" ajudaria a encontrar uma solução mais difícil.

PS: Acredito que quando temos várias situações iguais exigimos bombas mínimas para limpar a linha superior, escolhemos uma que use a maioria das bombas no "lado esquerdo" da linha. Ainda alguma prova que possa estar correta?


  1. Nunca bombardeie a borda (a menos que o quadrado não tenha vizinho nonborder)
  2. Canto zero.
  3. Para zerar canto, derrube valor de canto um quadrado fora diagonaly (o único nonborder vizinho)
  4. Isto irá criar novos cantos. Vá para 2

Edit: não percebi que Kostek sugeriu quase a mesma abordagem, então agora eu faço uma afirmação mais forte: se os cantos para limpar são escolhidos para estar sempre na camada mais externa, então é ótimo.

No exemplo do OP: perder 2 (como 1 + 1 ou 2) em qualquer outra coisa que não em 5 não leva a nenhum quadrado que caia em 5. Então, devemos simplesmente diminuir 2 em 5 (e 6 no canto inferior esquerdo 1 ...)

Depois disso, há apenas uma maneira de limpar (no canto superior esquerdo) o que era originalmente 1 (agora 0), e isso é largando 0 em B3 (excel como notação). E assim por diante.

Somente depois de limpar as colunas A e E inteiras e as linhas 1 e 7, comece a limpar uma camada mais profundamente.

Considerar apuradas apenas as que foram intencionalmente limpas, limpar os cantos do valor 0 não custa nada e simplifica o pensamento sobre isso.

Como todas as bombas lançadas dessa maneira devem ser descartadas e isso leva a campos limpos, é a solução ideal.

Depois de um bom sono, percebi que isso não é verdade. Considerar

  ABCDE    
1 01000
2 10000
3 00000
4 00000

Minha abordagem seria lançar bombas em B3 e C2, quando cair em B2 seria o suficiente


Esta é uma resposta parcial, estou tentando encontrar um limite inferior e superior que poderia ser o número possível de bombas.

Em placas 3x3 e menores, a solução é trivialmente sempre a maior célula numerada.

Em quadros maiores que 4x4, o primeiro limite inferior óbvio é a soma dos cantos:

*2* 3  7 *1*
 1  5  6  2
 2  1  3  2
*6* 9  6 *4*

no entanto você arranja a bomba, é impossível limpar esta placa 4x4 com menos de 2 + 1 + 6 + 4 = 13 bombas.

Foi mencionado em outras respostas que colocar a bomba no segundo-canto para eliminar o canto nunca é pior do que colocar a bomba na esquina em si, então, dada a placa:

*2* 3  4  7 *1*
 1  5  2  6  2
 4  3  4  2  1
 2  1  2  4  1
 3  1  3  4  1
 2  1  4  3  2
*6* 9  1  6 *4*

Podemos zerar os cantos colocando bombas no segundo para o canto para dar uma nova prancha:

 0  1  1  6  0
 0  3  0  5  1
 2  1  1  1  0
 2  1  2  4  1
 0  0  0  0  0
 0  0  0  0  0
 0  3  0  2  0

Por enquanto, tudo bem. Precisamos de 13 bombas para limpar os cantos.

Agora observe os números 6, 4, 3 e 2 marcados abaixo:

 0  1  1 *6* 0
 0  3  0  5  1
 2  1  1  1  0
*2* 1  2 *4* 1
 0  0  0  0  0
 0  0  0  0  0
 0 *3* 0  2  0

Não há como bombardear qualquer uma dessas duas células usando uma única bomba, então a bomba mínima aumentou em 6 + 4 + 3 + 2, então adicionando ao número de bombas que usamos para limpar os cantos, temos que o mínimo O número de bombas necessárias para este mapa tornou-se 28 bombas. É impossível limpar este mapa com menos de 28 bombas, este é o limite inferior para este mapa.

Você pode usar o algoritmo guloso para estabelecer um limite superior. Outras respostas mostraram que um algoritmo guloso produz uma solução que usa 28 bombas. Já que provamos anteriormente que nenhuma solução ótima pode ter menos de 28 bombas, portanto 28 bombas são de fato uma solução ótima.

Quando ganancioso e o método para encontrar o limite mínimo que eu mencionei acima não convergem, eu acho que você tem que voltar a verificar todas as combinações.

O algoritmo para encontrar o limite inferior é o seguinte:

  1. Escolha um elemento com o maior número, nomeie-o P.
  2. Marque todas as células a dois passos de distância de P e P como improvavel.
  3. Adicione P à lista de minimums .
  4. Repita para o passo 1 até que todas as células não possam ser picadas.
  5. Soma a lista de minimums para obter o limite inferior.

Existe uma maneira de reduzir isso a um subproblema simples.

Existem 2 partes para a explicação, o algoritmo e a razão pela qual o algoritmo fornece uma solução ótima. O primeiro não faz sentido sem o segundo, então vou começar com o porquê.

Se você pensar em bombardear o retângulo (suponha um grande retângulo - nenhum caso de borda ainda) você pode ver que a única maneira de reduzir o retângulo oco de quadrados no perímetro para 0 é bombardear o perímetro ou bombardear o retângulo oco de praças apenas dentro do perímetro. Vou chamar a camada de perímetro 1 e o retângulo dentro da camada 2.

Um insight importante é que não existe um ponto de bombardeio camada 1, porque o "raio de explosão" você começa a fazê-lo sempre está contido dentro do raio de explosão de outro quadrado da camada 2. Você deve ser capaz de se convencer disso facilmente.

Assim, podemos reduzir o problema para encontrar uma maneira ideal de bombardear o perímetro, então podemos repetir isso até que todos os quadrados sejam 0.

Mas é claro, isso nem sempre encontrará uma solução ideal se for possível bombardear o perímetro de uma maneira que não seja a ideal, mas usando X bombas extras tornam mais simples o problema de reduzir a camada interna por> X bombas. Então, se chamarmos a camada de permissão um, se colocarmos um X extra em algum lugar na camada 2 (apenas dentro da camada 1), podemos reduzir o esforço de bombardear mais tarde a camada 2 em mais de X? Em outras palavras, temos que provar que podemos ser gananciosos em reduzir o perímetro externo.

Mas sabemos que podemos ser gananciosos. Porque nenhuma bomba na camada 2 pode ser mais eficiente na redução da camada 2 para 0 do que uma bomba estrategicamente colocada na camada 3. E pela mesma razão de antes - há sempre uma bomba que podemos colocar na camada 3 que afetará cada quadrado da camada 2 que uma bomba colocada na camada 2 pode. Então, nunca pode nos prejudicar sermos gananciosos (nesse sentido de ganância).

Então, tudo o que temos a fazer é encontrar a maneira ideal de reduzir o autor para 0 bombardeando a próxima camada interna.

Nós nunca nos machucamos bombardeando primeiro o canto para 0, porque apenas o canto da camada interna pode alcançá-lo, então realmente não temos escolha (e, qualquer bomba no perímetro que possa alcançar o canto tem um raio de explosão contido no canto). raio de explosão a partir do canto da camada interna).

Uma vez feito isso, os quadrados no perímetro adjacente ao canto 0 só podem ser alcançados por 2 quadrados a partir da camada interna:

0       A       B

C       X       Y

D       Z

Neste ponto, o perímetro é efetivamente um loop de 1 dimensão fechado, porque qualquer bomba reduzirá 3 quadrados adjacentes. Exceto por alguma estranheza perto dos cantos - X pode "acertar" A, B, C e D.

Agora não podemos usar nenhum truque de raio de explosão - a situação de cada quadrado é simétrica, exceto pelos cantos estranhos, e mesmo assim não há raio de explosão que seja um subconjunto de outro. Note que se isso fosse uma linha (como o Coronel Panic discute) em vez de um loop fechado, a solução é trivial. Os pontos finais devem ser reduzidos para 0, e nunca prejudica você bombardear os pontos adjacentes aos pontos finais, novamente porque o raio da explosão é um superconjunto. Depois de ter feito o seu endpoint 0, você ainda tem um novo endpoint, então repita (até que a linha seja toda 0).

Então, se nós podemos otimamente reduzir um único quadrado na camada para 0, nós temos um algoritmo (porque nós cortamos o loop e agora temos uma linha reta com pontos finais). Acredito que o bombardeio adjacente ao quadrado com o menor valor (dando-lhe 2 opções) de tal forma que o maior valor dentro de 2 quadrados do menor valor seja o mínimo possível (você pode dividir seu bombardeio para administrar isso) será ótimo, mas eu não (ainda?) tem uma prova.


Não há necessidade de transformar o problema em subproblemas lineares.

Em vez disso, use uma simples heurística gananciosa, que é bombardear os cantos , começando pela maior.

No exemplo dado, existem quatro cantos, {2, 1, 6, 4}. Para cada canto não há melhor movimento do que bombardear a diagonal da célula até o canto, então sabemos de fato que nossos primeiros bombardeios 2 + 1 + 6 + 4 = 13 devem estar nessas células diagonais. Depois de fazer o bombardeio, ficamos com uma nova matriz:

2 3 4 7 1      0 1 1 6 0      0 1 1 6 0     1 1 6 0     0 0 5     0 0 0 
1 5 2 6 2      0 3 0 5 1      0 3 0 5 1  => 1 0 4 0  => 0 0 3  => 0 0 0  
4 3 4 2 1      2 1 1 1 0      2 1 1 1 0     0 0 0 0     0 0 0     0 0 3  
2 1 2 4 1  =>  2 1 2 4 1  =>  2 1 2 4 1     0 0 3 0     0 0 3      
3 1 3 4 1      0 0 0 0 0      0 0 0 0 0 
2 1 4 3 2      0 0 0 0 0      0 0 0 0 0 
6 9 1 6 4      0 3 0 2 0      0 0 0 0 0 

Após os primeiros 13 atentados, usamos a heurística para eliminar 3 0 2 através de três bombardeamentos. Agora, temos 2 novos cantos, {2, 1} na quarta linha. Nós bombardeamos aqueles, outros 3 atentados. Nós reduzimos a matriz para 4 x 4 agora. Existe um canto, o canto superior esquerdo. Nós bombardeamos isso. Agora temos 2 cantos à esquerda, {5, 3}. Como o 5 é o maior canto, bombardeá-lo primeiro, 5 bombardeios e, finalmente, bombardear os 3 no outro canto. O total é 13 + 3 + 3 + 1 + 5 + 3 = 28.


Pólya diz "Se você não pode resolver um problema, então há um problema mais fácil que você pode resolver: encontre-o."

O óbvio problema mais simples é o problema unidimensional (quando a grade é uma única linha). Vamos começar com o algoritmo mais simples - bombardear avidamente o maior alvo. Quando isso dá errado?

Dado 1 1 1 , o algoritmo guloso é indiferente a qual célula ele bombardeia primeiro. Claro, a célula central é melhor - zera todas as três células ao mesmo tempo. Isto sugere um novo algoritmo A, "bomba para minimizar a soma restante". Quando esse algoritmo dá errado?

Dado 1 1 2 1 1 , o algoritmo A é indiferente entre bombardear as 2ª, 3ª ou 4ª células. Mas bombardear a segunda célula para sair de 0 0 1 1 1 é melhor do que bombardear a terceira célula para sair de 1 0 1 0 1 . Como consertar isso? O problema com o bombardeio da terceira célula é que ela nos deixa trabalhar à esquerda e trabalha à direita, o que deve ser feito separadamente.

Que tal "bomba para minimizar a soma restante, mas maximizar o mínimo para a esquerda (de onde bombardeamos) mais o mínimo para a direita". Chame esse algoritmo B. Quando esse algoritmo dá errado?

Edit: Depois de ler os comentários, eu concordo que um problema muito mais interessante seria o problema unidimensional alterado para que as extremidades se juntem. Adoraria ver algum progresso nisso.


Seu novo problema, com os valores não decrescentes nas linhas, é muito fácil de resolver.

Observe que a coluna da esquerda contém os números mais altos. Portanto, qualquer solução ótima deve primeiro reduzir essa coluna a zero. Assim, podemos executar uma corrida de bombardeio 1-D sobre essa coluna, reduzindo todos os elementos a zero. Nós deixamos as bombas caírem na segunda coluna para que causem dano máximo. Há muitos posts aqui lidando com o caso 1D, eu acho, então eu me sinto seguro em pular esse caso. (Se você quiser que eu descreva, eu posso.) Por causa da propriedade decrescente, as três colunas mais à esquerda serão reduzidas a zero. Mas, provavelmente usaremos um número mínimo de bombas aqui porque a coluna da esquerda deve ser zerada.

Agora, uma vez que a coluna da esquerda está zerada, apenas recortamos as três colunas mais à esquerda que agora estão zeradas e repetimos com a matriz agora reduzida. Isso deve nos dar uma solução ótima, pois em cada estágio usamos um número de bombas provavelmente mínimo.


Você pode representar este problema como um problema de programação inteiro . (esta é apenas uma das possíveis soluções para abordar este problema)

Tendo pontos:

a b c d
e f g h
i j k l
m n o p

pode-se escrever 16 equações onde, por exemplo, o ponto f

f <= ai + bi + ci + ei + fi + gi + ii + ji + ki   

minimaised sobre a soma de todos os índices e solução inteira.

A solução é, obviamente, a soma desses índices.

Isso pode ser ainda mais simplificado definindo todos os xi nos limites 0, então você acaba tendo a equação 4 + 1 neste exemplo.

O problema é que não existe um algoritmo trivial para resolver tais problemas. Não sou especialista nisso, mas resolver este problema como programação linear é NP difícil.


Eu tive que parar em apenas uma solução parcial desde que eu estava fora do tempo, mas espero que até mesmo esta solução parcial fornece algumas idéias sobre uma abordagem em potencial para resolver este problema.

Quando me deparo com um problema difícil, gosto de criar problemas mais simples para desenvolver uma intuição sobre o espaço do problema. Aqui, o primeiro passo que tomei foi reduzir esse problema 2-D para um problema 1-D. Considere uma linha:

0 4 2 1 3 0 1

De alguma maneira ou de outra, você sabe que precisará bombardear ou rodear o 4 ponto 4 vezes para descer para 0. Já que a esquerda do local é um número menor, não há nenhum benefício em bombardear o 0 ou o 4 sobre bombardear o 2 De fato, eu acredito (mas falta uma prova rigorosa) que bombardear os 2 até que o 4 ponto desça para 0 é pelo menos tão bom quanto qualquer outra estratégia para reduzir 4 para 0. Pode-se prosseguir pela linha da esquerda para a direita em uma estratégia como esta:

index = 1
while index < line_length
  while number_at_index(index - 1) > 0
    bomb(index)
  end
  index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
  bomb(index - 1)
end

Um par de amostras de ordens de bombardeio:

0 4[2]1 3 0 1
0 3[1]0 3 0 1
0 2[0]0 3 0 1
0 1[0]0 3 0 1
0 0 0 0 3[0]1
0 0 0 0 2[0]0
0 0 0 0 1[0]0
0 0 0 0 0 0 0

4[2]1 3 2 1 5
3[1]0 3 2 1 5
2[0]0 3 2 1 5
1[0]0 3 2 1 5
0 0 0 3[2]1 5
0 0 0 2[1]0 5
0 0 0 1[0]0 5
0 0 0 0 0 0[5]
0 0 0 0 0 0[4]
0 0 0 0 0 0[3]
0 0 0 0 0 0[2]
0 0 0 0 0 0[1]
0 0 0 0 0 0 0

A idéia de começar com um número que precisa cair de uma forma ou de outra é atraente porque de repente se torna possível encontrar uma solução que, como alguns, afirmam ser pelo menos tão boa quanto todas as outras soluções.

O próximo passo em complexidade, onde esta busca de pelo menos tão boa ainda é viável, está na borda do tabuleiro. É claro para mim que nunca há qualquer benefício estrito para bombardear a borda externa; é melhor você bombardear o local e conseguir três outros espaços de graça. Dado isso, podemos dizer que bombardear o anel dentro da borda é pelo menos tão bom quanto bombardear a borda. Além disso, podemos combinar isso com a intuição de que bombardear o caminho certo dentro da borda é, na verdade, a única maneira de reduzir os limites até 0. Ainda mais, é trivialmente simples descobrir a estratégia ideal (em que menos tão bom quanto qualquer outra estratégia) para obter números de canto para 0. Colocamos tudo isso junto e podemos chegar muito mais perto de uma solução no espaço 2-D.

Dada a observação sobre as peças de canto, podemos dizer com certeza que conhecemos a estratégia ideal para ir de qualquer quadro inicial a um tabuleiro com zeros em todos os cantos. Este é um exemplo de tal placa (eu pedi os números das duas placas lineares acima). Eu rotulei alguns espaços de maneira diferente e explicarei o porquê.

0 4 2 1 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

Um vai notar na primeira linha realmente se assemelha ao exemplo linear que vimos anteriormente. Lembrando nossa observação anterior de que a maneira ideal de obter a linha de cima de todos abaixo de 0 é bombardear a segunda linha (a linha x ). Não há como limpar a linha superior bombardeando qualquer uma das linhas e nenhum benefício adicional para bombardear a linha superior sobre o bombardeio do espaço correspondente na linha x .

Poderíamos aplicar a estratégia linear a partir de cima (bombardeando os espaços correspondentes na linha x ), nos preocupando apenas com a linha superior e nada mais. Seria algo assim:

0 4 2 1 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 3 1 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 2 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 1 0 0 3 0 1 0
4 x[x]x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

0 0 0 0 3 0 1 0
4 x x x x x x 4
2 y y y y y y 2
1 y y y y y y 1
3 y y y y y y 3
2 y y y y y y 2
1 y y y y y y 1
5 y y y y y y 5
0 4 2 1 3 0 1 0

A falha nessa abordagem se torna muito óbvia nos dois últimos bombardeios. É claro, dado que os únicos locais de bombas que reduzem a figura 4 na primeira coluna na segunda linha são o primeiro x y . Os dois últimos bombardeios são claramente inferiores a apenas bombardear o primeiro x , o que teria feito exatamente o mesmo (com relação ao primeiro ponto na linha de cima, que não temos outra forma de compensação). Desde que demonstramos que nossa estratégia atual é sub-ótima, é claramente necessária uma modificação na estratégia.

Neste ponto, posso dar um passo atrás na complexidade e focar apenas um canto. Vamos considerar este:

0 4 2 1
4 x y a
2 z . .
1 b . .

É claro que a única maneira de obter os espaços com 4 abaixo de zero é bombardear algumas combinações de x , y e z . Com algumas acrobacias em mente, tenho quase certeza que a solução ideal é bombardear x três vezes e depois a b . Agora, é uma questão de descobrir como cheguei a essa solução e se ela revela qualquer intuição que possamos usar para resolver esse problema local. Percebo que não há bombardeio de espaços z . Tentando encontrar um canto onde o bombardeio desses espaços faz sentido produz um canto que se parece com isso:

0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .

Para este, está claro para mim que a solução ótima é bombardear y 5 vezes z 5 vezes. Vamos um passo além.

0 4 2 5 6 0 0
4 x y a . . .
2 z . . . . .
5 b . . . . .
6 . . . . . .
0 . . . . . .
0 . . . . . .

Aqui, parece igualmente intuitivo que a solução ideal é bombardear a e b 6 vezes e depois x 4 vezes.

Agora, torna-se um jogo de como transformar essas intuições em princípios sobre os quais podemos nos basear.

Espero que continue!


Aqui está a minha solução .. Eu não vou escrever no código ainda, desde que eu não tenho tempo, mas eu acredito que isso deve produzir um número ótimo de movimentos a cada vez - embora eu não tenha certeza de quão eficiente seria encontrar os pontos para bombardear.

Em primeiro lugar, como @Luka Rahne afirmou em um dos comentários, a ordem em que você bombardeia não é importante - apenas a combinação.

Em segundo lugar, como muitos outros afirmaram, bombardear 1-off da diagonal dos cantos é ideal porque toca mais pontos do que os cantos.

Isso gera a base para a minha versão do algoritmo: Podemos bombardear o '1-off dos cantos' primeiro ou por último, não importa (em teoria) Nós bombardeamos os primeiros porque facilita as decisões posteriores (na prática) Nós bombardeamos o ponto que afeta mais pontos, enquanto simultaneamente bombardeiam esses cantos.

Vamos definir os Pontos de Resistência como os pontos no tabuleiro com os pontos mais não bombardeados + o maior número de 0 em torno deles

pontos não bombardeados podem ser definidos como pontos que não existem em nosso escopo atual do quadro que estamos examinando.

Eu também vou definir 4 limites que irão lidar com o nosso escopo: Top = 0, Left = 0, Bottom = k, right = j. (valores para começar)

Por fim, definirei bombas ótimas como bombas que são lançadas em pontos adjacentes a pontos de resistência e estão tocando (1) o ponto de maior valor de resistência e (2) o maior número de pontos possíveis.

Com relação à abordagem, é óbvio que estamos trabalhando de fora para dentro. Poderemos trabalhar com 4 'bombardeiros' ao mesmo tempo.

Os primeiros pontos de resistência são obviamente os nossos cantos. Os pontos 'out of bound' não são bombardeados (há 5 pontos fora do escopo para cada canto). Então nós bombardeamos os pontos diagonalmente um dos cantos primeiro.

Algoritmo:

  1. Encontre os 4 melhores pontos de bomba.
  2. Se um ponto de bomba está bombardeando um ponto de resistência que está tocando em 2 limites (isto é, um canto), a bomba até esse ponto é 0. Caso contrário, bombeie cada até que um dos pontos de resistência que toca o ponto de bomba ideal seja 0.
  3. para cada limite: if (sum (ligado) == 0) limite antecipado

repita até TOP = BOTTOM e LEFT = DIREITA

Vou tentar escrever o código real mais tarde


Aqui está uma solução que generaliza as boas propriedades dos cantos.

Vamos supor que poderíamos encontrar um ponto de entrega perfeito para um determinado campo, ou seja, a melhor maneira de diminuir o valor nele. Então, para encontrar o número mínimo de bombas a serem descartadas, um primeiro rascunho de um algoritmo poderia ser (o código é copiado de uma implementação em ruby):

dropped_bomb_count = 0
while there_are_cells_with_non_zero_count_left
  coordinates = choose_a_perfect_drop_point
  drop_bomb(coordinates)
  dropped_bomb_count += 1
end
return dropped_bomb_count

O desafio é choose_a_perfect_drop_point. Primeiro, vamos definir o que é um ponto de queda perfeito.

  • Um ponto de (x, y)queda para diminui o valor em (x, y). Pode também diminuir os valores em outras células.
  • Um ponto de queda a for (x, y)é melhor que um ponto de queda b para (x, y)se ele diminuir os valores em um superconjunto adequado das células que b diminui.
  • Um ponto de queda é máximo se não houver outro ponto de queda melhor.
  • Dois pontos de queda (x, y)são equivalentes se eles diminuírem o mesmo conjunto de células.
  • Um ponto de gota (x, y)é perfeito se for equivalente a todos os pontos de queda máximos para (x, y).

Se houver um ponto de queda perfeito (x, y), você não poderá diminuir o valor com (x, y)mais eficácia do que soltar uma bomba em um dos pontos de queda perfeitos (x, y).

Um ponto de gota perfeito para um determinado campo é um ponto de queda perfeito para qualquer uma das suas células.

Aqui estão alguns exemplos:

1 0 1 0 0
0 0 0 0 0
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0

O ponto de queda perfeito para a célula (0, 0)(índice baseado em zero) é (1, 1). Todos os outros pontos de queda para (1, 1), ou seja (0, 0), (0, 1)e (1, 0), diminuir menos células.

0 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

Um ponto de gota perfeito para a célula (2, 2)(índice de base zero) é (2, 2), e também todas as células circundantes (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), e (3, 3).

0 0 0 0 1
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
0 0 0 0 0

um ponto de queda perfeito para a célula (2, 2)é (3, 1): diminui o valor (2, 2)e o valor em (4, 0). Todos os outros pontos de queda (2, 2)não são máximos, pois diminuem uma célula a menos. O ponto de queda perfeito (2, 2)também é o ponto de queda perfeito (4, 0), e é o único ponto de queda perfeito para o campo. Isso leva à solução perfeita para esse campo (uma gota de bomba).

1 0 0 0 0
0 0 0 0 0
0 0 1 0 0
0 0 0 0 0
1 0 0 0 0

Não há ponto de queda perfeito para (2, 2): Ambos (1, 1)e (1, 3)diminuir (2, 2)e outra célula (eles são pontos de queda máximos para (2, 2)), mas eles não são equivalentes. No entanto, (1, 1)é um ponto de queda perfeito para (0, 0), e (1, 3)é um ponto de queda perfeito para (0, 4).

Com essa definição de pontos de queda perfeitos e uma certa ordem de verificações, recebo o seguinte resultado para o exemplo na pergunta:

Drop bomb on 1, 1
Drop bomb on 1, 1
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 5
Drop bomb on 1, 6
Drop bomb on 1, 2
Drop bomb on 1, 2
Drop bomb on 0, 6
Drop bomb on 0, 6
Drop bomb on 2, 1
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 2, 5
Drop bomb on 3, 1
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 0
Drop bomb on 3, 4
Drop bomb on 3, 4
Drop bomb on 3, 3
Drop bomb on 3, 3
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 3, 6
Drop bomb on 4, 6
28

No entanto, o algoritmo só funciona se houver pelo menos um ponto de queda perfeito após cada etapa. É possível construir exemplos onde não há pontos de queda perfeitos:

0 1 1 0
1 0 0 1
1 0 0 1
0 1 1 0

Para esses casos, podemos modificar o algoritmo para que, em vez de um ponto de queda perfeito, escolhamos uma coordenada com uma escolha mínima de pontos de queda máximos e, em seguida, calcule o mínimo para cada escolha. No caso acima, todas as células com valores têm dois pontos de queda máximos. Por exemplo, (0, 1)tem os pontos de queda máximos (1, 1)e (1, 2). Escolher qualquer um e, em seguida, calcular o mínimo leva a este resultado:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2

Eu acredito que para minimizar a quantidade de bombas você simplesmente precisa maximizar a quantidade de dano .. para que isso aconteça é necessário verificar a área que tem a força mais forte .. então você primeiro analisa o campo com um kernel 3x3 e verifica onde a soma é mais forte .. e bombeie lá .. e faça até que o campo esteja plano .. para este arquivado a resposta é 28

var oMatrix = [
[2,3,4,7,1],
[1,5,2,6,2],
[4,3,4,2,1],
[2,1,2,4,1],
[3,1,3,4,1],
[2,1,4,3,2],
[6,9,1,6,4]
]

var nBombs = 0;
do
{
    var bSpacesLeftToBomb = false;
    var nHigh = 0;
    var nCellX = 0;
    var nCellY = 0;
    for(var y = 1 ; y<oMatrix.length-1;y++) 
        for(var x = 1 ; x<oMatrix[y].length-1;x++)  
        {
            var nValue = 0;
            for(var yy = y-1;yy<=y+1;yy++)
                for(var xx = x-1;xx<=x+1;xx++)
                    nValue += oMatrix[yy][xx];

            if(nValue>nHigh)
            {
                nHigh = nValue;
                nCellX = x;
                nCellY = y; 
            }

        }
    if(nHigh>0)
    {
        nBombs++;

        for(var yy = nCellY-1;yy<=nCellY+1;yy++)
        {
            for(var xx = nCellX-1;xx<=nCellX+1;xx++)
            {
                if(oMatrix[yy][xx]<=0)
                    continue;
                oMatrix[yy][xx] = --oMatrix[yy][xx];
            }
        }
        bSpacesLeftToBomb = true;
    }
}
while(bSpacesLeftToBomb);

alert(nBombs+'bombs');

Não consigo pensar em uma maneira de calcular o número real sem apenas calcular a campanha de bombardeio usando minha melhor heurística e espero obter um resultado razoável.

Então, meu método é calcular uma métrica de eficiência de bombardeio para cada célula, bombardear a célula com o valor mais alto, ... iterar o processo até eu achatar tudo. Alguns têm defendido o uso de danos potenciais simples (ou seja, pontuação de 0 a 9) como uma métrica, mas isso é insuficiente ao atingir as células de alto valor e não fazer uso da sobreposição de danos. Eu calcularia cell value - sum of all neighbouring cells, redefiniria qualquer positivo para 0 e usaria o valor absoluto de qualquer coisa negativa. Intuitivamente, essa métrica deve fazer uma seleção que ajude a maximizar a sobreposição de danos nas células com contagens altas, em vez de atacá-las diretamente.

O código abaixo atinge a destruição total do campo de teste em 28 bombas (note que usando dano potencial como métrica rende 31!).

using System;
using System.Collections.Generic;
using System.Linq;

namespace 
{
  internal class Program
  {
    // store the battle field as flat array + dimensions
    private static int _width = 5;
    private static int _length = 7;
    private static int[] _field = new int[] {
        2, 3, 4, 7, 1,
        1, 5, 2, 6, 2,
        4, 3, 4, 2, 1,
        2, 1, 2, 4, 1,
        3, 1, 3, 4, 1,
        2, 1, 4, 3, 2,
        6, 9, 1, 6, 4
    };
    // this will store the devastation metric
    private static int[] _metric;

    // do the work
    private static void Main(string[] args)
    {
        int count = 0;

        while (_field.Sum() > 0)
        {
            Console.Out.WriteLine("Round {0}:", ++count);
            GetBlastPotential();
            int cell_to_bomb = FindBestBombingSite();
            PrintField(cell_to_bomb);
            Bomb(cell_to_bomb);
        }
        Console.Out.WriteLine("Done in {0} rounds", count);
    } 

    // convert 2D position to 1D index
    private static int Get1DCoord(int x, int y)
    {
        if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
        else
        {
            return (y * _width) + x;
        }
    }

    // Convert 1D index to 2D position
    private static void Get2DCoord(int n, out int x, out int y)
    {
        if ((n < 0) || (n >= _field.Length))
        {
            x = -1;
            y = -1;
        }
        else
        {
            x = n % _width;
            y = n / _width;
        }
    }

    // Compute a list of 1D indices for a cell neighbours
    private static List<int> GetNeighbours(int cell)
    {
        List<int> neighbours = new List<int>();
        int x, y;
        Get2DCoord(cell, out x, out y);
        if ((x >= 0) && (y >= 0))
        {
            List<int> tmp = new List<int>();
            tmp.Add(Get1DCoord(x - 1, y - 1));
            tmp.Add(Get1DCoord(x - 1, y));
            tmp.Add(Get1DCoord(x - 1, y + 1));
            tmp.Add(Get1DCoord(x, y - 1));
            tmp.Add(Get1DCoord(x, y + 1));
            tmp.Add(Get1DCoord(x + 1, y - 1));
            tmp.Add(Get1DCoord(x + 1, y));
            tmp.Add(Get1DCoord(x + 1, y + 1));

            // eliminate invalid coords - i.e. stuff past the edges
            foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
        }
        return neighbours;
    }

    // Compute the devastation metric for each cell
    // Represent the Value of the cell minus the sum of all its neighbours
    private static void GetBlastPotential()
    {
        _metric = new int[_field.Length];
        for (int i = 0; i < _field.Length; i++)
        {
            _metric[i] = _field[i];
            List<int> neighbours = GetNeighbours(i);
            if (neighbours != null)
            {
                foreach (int j in neighbours) _metric[i] -= _field[j];
            }
        }
        for (int i = 0; i < _metric.Length; i++)
        {
            _metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
        }
    }

    //// Compute the simple expected damage a bomb would score
    //private static void GetBlastPotential()
    //{
    //    _metric = new int[_field.Length];
    //    for (int i = 0; i < _field.Length; i++)
    //    {
    //        _metric[i] = (_field[i] > 0) ? 1 : 0;
    //        List<int> neighbours = GetNeighbours(i);
    //        if (neighbours != null)
    //        {
    //            foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
    //        }
    //    }            
    //}

    // Update the battle field upon dropping a bomb
    private static void Bomb(int cell)
    {
        List<int> neighbours = GetNeighbours(cell);
        foreach (int i in neighbours)
        {
            if (_field[i] > 0) _field[i]--;
        }
    }

    // Find the best bombing site - just return index of local maxima
    private static int FindBestBombingSite()
    {
        int max_idx = 0;
        int max_val = int.MinValue;
        for (int i = 0; i < _metric.Length; i++)
        {
            if (_metric[i] > max_val)
            {
                max_val = _metric[i];
                max_idx = i;
            }
        }
        return max_idx;
    }

    // Display the battle field on the console
    private static void PrintField(int cell)
    {
        for (int x = 0; x < _width; x++)
        {
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
            }
            Console.Out.Write(" || ");
            for (int y = 0; y < _length; y++)
            {
                int c = Get1DCoord(x, y);
                if (c == cell)
                    Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
                else
                    Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
            }
            Console.Out.WriteLine();
        }
        Console.Out.WriteLine();
    }           
  }
}

O padrão de bombardeio resultante é produzido da seguinte forma (valores de campo à esquerda, métrica à direita)

Round 1:
  2   1   4   2   3   2   6  ||   7  16   8  10   4  18   6
  3   5   3   1   1   1   9  ||  11  18  18  21  17  28   5
  4  [2]  4   2   3   4   1  ||  19 [32] 21  20  17  24  22
  7   6   2   4   4   3   6  ||   8  17  20  14  16  22   8
  1   2   1   1   1   2   4  ||  14  15  14  11  13  16   7

Round 2:
  2   1   4   2   3   2   6  ||   5  13   6   9   4  18   6
  2   4   2   1   1  [1]  9  ||  10  15  17  19  17 [28]  5
  3   2   3   2   3   4   1  ||  16  24  18  17  17  24  22
  6   5   1   4   4   3   6  ||   7  14  19  12  16  22   8
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 3:
  2   1   4   2   2   1   5  ||   5  13   6   7   3  15   5
  2   4   2   1   0   1   8  ||  10  15  17  16  14  20   2
  3  [2]  3   2   2   3   0  ||  16 [24] 18  15  16  21  21
  6   5   1   4   4   3   6  ||   7  14  19  11  14  19   6
  1   2   1   1   1   2   4  ||  12  12  12  10  13  16   7

Round 4:
  2   1   4   2   2   1   5  ||   3  10   4   6   3  15   5
  1   3   1   1   0   1   8  ||   9  12  16  14  14  20   2
  2   2   2   2   2  [3]  0  ||  13  16  15  12  16 [21] 21
  5   4   0   4   4   3   6  ||   6  11  18   9  14  19   6
  1   2   1   1   1   2   4  ||  10   9  10   9  13  16   7

Round 5:
  2   1   4   2   2   1   5  ||   3  10   4   6   2  13   3
  1   3   1   1   0  [0]  7  ||   9  12  16  13  12 [19]  2
  2   2   2   2   1   3   0  ||  13  16  15  10  14  15  17
  5   4   0   4   3   2   5  ||   6  11  18   7  13  17   6
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 6:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   9  12  16  11   8  13   0
  2   2   2   2   0   2   0  ||  13  16  15   9  14  14  15
  5   4  [0]  4   3   2   5  ||   6  11 [18]  6  11  15   5
  1   2   1   1   1   2   4  ||  10   9  10   8  11  13   5

Round 7:
  2   1   4   2   1   0   4  ||   3  10   4   5   2  11   2
  1   3   1   1   0   0   6  ||   8  10  13   9   7  13   0
  2  [1]  1   1   0   2   0  ||  11 [15] 12   8  12  14  15
  5   3   0   3   3   2   5  ||   3   8  10   3   8  15   5
  1   1   0   0   1   2   4  ||   8   8   7   7   9  13   5

Round 8:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   7  13   0
  1   1   0   1   0   2   0  ||   8   8  10   6  12  14  15
  4   2   0   3   3  [2]  5  ||   2   6   8   2   8 [15]  5
  1   1   0   0   1   2   4  ||   6   6   6   7   9  13   5

Round 9:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  11   2
  0   2   0   1   0   0   6  ||   7   7  12   7   6  12   0
  1   1   0   1   0  [1]  0  ||   8   8  10   5  10 [13] 13
  4   2   0   3   2   2   4  ||   2   6   8   0   6   9   3
  1   1   0   0   0   1   3  ||   6   6   6   5   8  10   4

Round 10:
  2   1   4   2   1   0   4  ||   1   7   2   4   2  10   1
  0   2  [0]  1   0   0   5  ||   7   7 [12]  7   6  11   0
  1   1   0   1   0   1   0  ||   8   8  10   4   8   9  10
  4   2   0   3   1   1   3  ||   2   6   8   0   6   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 11:
  2   0   3   1   1   0   4  ||   0   6   0   3   0  10   1
  0   1   0   0   0  [0]  5  ||   4   5   5   5   3 [11]  0
  1   0   0   0   0   1   0  ||   6   8   6   4   6   9  10
  4   2   0   3   1   1   3  ||   1   5   6   0   5   8   3
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 12:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   7   1
  0   1   0   0   0   0   4  ||   4   5   5   4   1   7   0
  1   0   0   0   0  [0]  0  ||   6   8   6   4   5  [9]  8
  4   2   0   3   1   1   3  ||   1   5   6   0   4   7   2
  1   1   0   0   0   1   3  ||   6   6   6   4   6   7   2

Round 13:
  2   0   3   1   0   0   3  ||   0   6   0   2   1   6   0
  0   1   0   0   0   0   3  ||   4   5   5   4   1   6   0
  1  [0]  0   0   0   0   0  ||   6  [8]  6   3   3   5   5
  4   2   0   3   0   0   2  ||   1   5   6   0   4   6   2
  1   1   0   0   0   1   3  ||   6   6   6   3   4   4   0

Round 14:
  2   0   3   1   0  [0]  3  ||   0   5   0   2   1  [6]  0
  0   0   0   0   0   0   3  ||   2   5   4   4   1   6   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   5   5
  3   1   0   3   0   0   2  ||   0   4   5   0   4   6   2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 15:
  2   0   3   1   0   0   2  ||   0   5   0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   4   4
  3   1   0   3   0  [0]  2  ||   0   4   5   0   4  [6]  2
  1   1   0   0   0   1   3  ||   4   4   5   3   4   4   0

Round 16:
  2  [0]  3   1   0   0   2  ||   0  [5]  0   2   1   4   0
  0   0   0   0   0   0   2  ||   2   5   4   4   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1   0   3   0   0   1  ||   0   4   5   0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 17:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   4   4   4   3   3   3   3
  3   1  [0]  3   0   0   1  ||   0   4  [5]  0   3   3   1
  1   1   0   0   0   0   2  ||   4   4   5   3   3   3   0

Round 18:
  1   0   2   1   0   0   2  ||   0   3   0   1   1   4   0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   3   3   2   2   2   3   3
  3  [0]  0   2   0   0   1  ||   0  [4]  2   0   2   3   1
  1   0   0   0   0   0   2  ||   2   4   2   2   2   3   0

Round 19:
  1   0   2   1   0  [0]  2  ||   0   3   0   1   1  [4]  0
  0   0   0   0   0   0   2  ||   1   3   3   3   1   4   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   3   3
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 20:
  1  [0]  2   1   0   0   1  ||   0  [3]  0   1   1   2   0
  0   0   0   0   0   0   1  ||   1   3   3   3   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0   0   1  ||   0   2   2   0   2   3   1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 21:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
  0   0   0   0   0   0   0  ||   2   2   2   2   2   2   2
  2   0   0   2   0  [0]  1  ||   0   2   2   0   2  [3]  1
  0   0   0   0   0   0   2  ||   2   2   2   2   2   3   0

Round 22:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0   0   0   0   0   1  ||   0   1   2   2   1   2   0
 [0]  0   0   0   0   0   0  ||  [2]  2   2   2   2   1   1
  2   0   0   2   0   0   0  ||   0   2   2   0   2   1   1
  0   0   0   0   0   0   1  ||   2   2   2   2   2   1   0

Round 23:
  0   0   1   1   0   0   1  ||   0   1   0   0   1   2   0
  0   0  [0]  0   0   0   1  ||   0   1  [2]  2   1   2   0
  0   0   0   0   0   0   0  ||   1   1   2   2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 24:
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0  [0]  0   0   0   0  ||   1   1  [2]  2   2   1   1
  1   0   0   2   0   0   0  ||   0   1   2   0   2   1   1
  0   0   0   0   0   0   1  ||   1   1   2   2   2   1   0

Round 25:
  0   0   0   0   0  [0]  1  ||   0   0   0   0   0  [2]  0
  0   0   0   0   0   0   1  ||   0   0   0   0   0   2   0
  0   0   0   0   0   0   0  ||   1   1   1   1   1   1   1
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 26:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
 [0]  0   0   0   0   0   0  ||  [1]  1   1   1   1   0   0
  1   0   0   1   0   0   0  ||   0   1   1   0   1   1   1
  0   0   0   0   0   0   1  ||   1   1   1   1   1   1   0

Round 27:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0  [0]  0   0   0   0  ||   0   0  [1]  1   1   0   0
  0   0   0   1   0   0   0  ||   0   0   1   0   1   1   1
  0   0   0   0   0   0   1  ||   0   0   1   1   1   1   0

Round 28:
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0   0   0  ||   0   0   0   0   0   0   0
  0   0   0   0   0  [0]  0  ||   0   0   0   0   0  [1]  1
  0   0   0   0   0   0   1  ||   0   0   0   0   0   1   0

Done in 28 rounds

Parece que uma abordagem de programação linear pode ser muito útil aqui.

Seja P mxn a matriz com os valores das posições:

Agora vamos definir uma matriz de bomba B (x, y) mxn , com 1 ≤ x ≤ m , 1 ≤ y ≤ n como abaixo

de tal forma que

Por exemplo:

Então, estamos olhando para uma matriz B mxn = [ b ij ] que

  1. Pode ser definido como uma soma de matrizes de bomba:

    ( q ij seria então a quantidade de bombas que cairíamos na posição p ij )

  2. p ij - b ij ≤ 0 (para ser mais sucinto, digamos como P - B ≤ 0 )

Além disso, B deve minimizar a soma .

Também podemos escrever B como a feia matriz à frente:

e como P - B ≤ 0 (que significa P ≤ B ), temos o seguinte sistema de desigualdade bastante linear abaixo:

Sendo q mn x 1 definido como

p mn x 1 definido como

Podemos dizer que temos um sistema O sistema abaixo representado como produto de matrizes http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D sendo S mn x mn a matriz a ser invertida para resolver o sistema. Eu mesmo não o expandi, mas acredito que seja fácil fazer isso em código.

Agora, temos um problema mínimo que pode ser declarado como

Eu acredito que é algo fácil, quase trivial de ser resolvido com algo parecido com o algoritmo simplex (há um documento bem legal sobre isso ). No entanto, eu não sei quase nenhuma programação linear (vou fazer um curso sobre isso no Coursera, mas é apenas no futuro ...), eu tive algumas dores de cabeça tentando entender e eu tenho um enorme trabalho freelance para terminar, então eu apenas desista aqui. Pode ser que eu fiz algo errado em algum momento, ou que ele não pode ir mais longe, mas acredito que este caminho pode eventualmente levar à solução. Enfim, estou ansioso pelo seu feedback.

(Agradecimento especial por este site incrível para criar imagens de expressões LaTeX )


função de avaliação, soma total:

int f (int ** matrix, int width, int height, int x, int y)
{
    int m[3][3] = { 0 };

    m[1][1] = matrix[x][y];
    if (x > 0) m[0][1] = matrix[x-1][y];
    if (x < width-1) m[2][1] = matrix[x+1][y];

    if (y > 0)
    {
        m[1][0] = matrix[x][y-1];
        if (x > 0) m[0][0] = matrix[x-1][y-1];
        if (x < width-1) m[2][0] = matrix[x+1][y-1];
    }

    if (y < height-1)
    {
        m[1][2] = matrix[x][y+1];
        if (x > 0) m[0][2] = matrix[x-1][y+1];
        if (x < width-1) m[2][2] = matrix[x+1][y+1];
    }

    return m[0][0]+m[0][1]+m[0][2]+m[1][0]+m[1][1]+m[1][2]+m[2][0]+m[2][1]+m[2][2];
}

função objetiva:

Point bestState (int ** matrix, int width, int height)
{
    Point p = new Point(0,0);
    int bestScore = 0;
    int b = 0;

    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
        {
            b = f(matrix,width,height,i,j);

            if (b > bestScore)
            {
                bestScore = best;
                p = new Point(i,j);
            }
        }

    retunr p;
}

destruir a função:

void destroy (int ** matrix, int width, int height, Point p)
{
    int x = p.x;
    int y = p.y;

    if(matrix[x][y] > 0) matrix[x][y]--;
    if (x > 0) if(matrix[x-1][y] > 0) matrix[x-1][y]--;
    if (x < width-1) if(matrix[x+1][y] > 0) matrix[x+1][y]--;

    if (y > 0)
    {
        if(matrix[x][y-1] > 0) matrix[x][y-1]--;
        if (x > 0) if(matrix[x-1][y-1] > 0) matrix[x-1][y-1]--;
        if (x < width-1) if(matrix[x+1][y-1] > 0) matrix[x+1][y-1]--;
    }

    if (y < height-1)
    {
        if(matrix[x][y] > 0) matrix[x][y+1]--;
        if (x > 0) if(matrix[x-1][y+1] > 0) matrix[x-1][y+1]--;
        if (x < width-1) if(matrix[x+1][y+1] > 0) matrix[x+1][y+1]--;
    }
}

função objetivo:

bool isGoal (int ** matrix, int width, int height)
{
    for (int i=0; i<width; i++)
        for (int j=0; j<height; j++)
            if (matrix[i][j] > 0)
                return false;
    return true;
}

função de maximização linear:

void solve (int ** matrix, int width, int height)
{
    while (!isGoal(matrix,width,height))
    {
        destroy(matrix,width,height, bestState(matrix,width,height));
    }
}

Isso não é o ideal, mas pode ser otimizado por meio de uma melhor função de avaliação.

.. mas pensando sobre este problema, eu estava pensando que uma das principais questões é obter figuras abandonadas no meio dos zeros em algum momento, então eu tomaria outra abordagem ... que é dominar os valores mínimos em zero, então tentar zeros de escape quanto possível, o que leva à minimização geral do (s) valor (es) mínimo (s) existente (s)


Bem, suponha que nós numeramos as posições 1, 2, ..., nx m. Qualquer sequência de gotas de bomba pode ser representada por uma sequência de números neste conjunto, onde os números podem se repetir. No entanto, o efeito no tabuleiro é o mesmo, independentemente da ordem em que você soltar as bombas, então qualquer escolha de drop de bomba pode ser representada como uma lista de números nxm, onde o primeiro número representa o número de bombas lançadas na posição 1 , o segundo número representa o número de bombas lançadas na posição 2, etc. Vamos chamar essa lista de números nxm de "chave".

Você poderia tentar primeiro calcular todos os estados de tabuleiro resultantes de 1 drop de bomba, e então usá-los para calcular todos os estados de board resultantes de 2 drops de bombas, etc, até obter todos os zeros. Mas a cada passo você armazenaria os estados em cache usando a chave que eu defini acima, para que você possa usar esses resultados no cálculo da próxima etapa (uma abordagem de "programação dinâmica").

Mas, dependendo do tamanho de n, m e dos números na grade, os requisitos de memória dessa abordagem podem ser excessivos. Você pode jogar fora todos os resultados para N bombas depois de calcular todos os resultados para N + 1, então há algumas economias lá. E é claro que você não pode armazenar nada em cache ao custo de ter que levar muito mais tempo - a abordagem de programação dinâmica troca memória por velocidade.


Eu também tenho 28 movimentos. Eu usei dois testes para o melhor próximo passo: primeiro o movimento produzindo a soma mínima para o tabuleiro. Em segundo lugar, para somas iguais, o movimento que produz a densidade máxima, definido como:

number-of-zeros / number-of-groups-of-zeros

Este é o Haskell. "solve board" mostra a solução do mecanismo. Você pode jogar o jogo digitando "main", em seguida, insira um ponto de destino, "melhor" para uma recomendação ou "sair" para sair.

SAÍDA:
* Main> resolve board
[(4,4), (3,6), (3,3), (2,2), (2,2), (4,6), (4,6), (2,6), (3,2), (4,2), (2,6), (3,3), (4,3), (2,6), (4,2), (4 , 6), (4,6), (3,6), (2,6), (2,6), (2,4), (2,4), (2,6), (3,6 ), (4,2), (4,2), (4,2), (4,2)]

import Data.List
import Data.List.Split
import Data.Ord
import Data.Function(on)

board = [2,3,4,7,1,
         1,5,2,6,2,
         4,3,4,2,1,
         2,1,2,4,1,
         3,1,3,4,1,
         2,1,4,3,2,
         6,9,1,6,4]

n = 5
m = 7

updateBoard board pt =
  let x = fst pt
      y = snd pt
      precedingLines = replicate ((y-2) * n) 0
      bomb = concat $ replicate (if y == 1
                                    then 2
                                    else min 3 (m+2-y)) (replicate (x-2) 0 
                                                         ++ (if x == 1 
                                                                then [1,1]
                                                                else replicate (min 3 (n+2-x)) 1)
                                                                ++ replicate (n-(x+1)) 0)
  in zipWith (\a b -> max 0 (a-b)) board (precedingLines ++ bomb ++ repeat 0)

showBoard board = 
  let top = "   " ++ (concat $ map (\x -> show x ++ ".") [1..n]) ++ "\n"
      chunks = chunksOf n board
  in putStrLn (top ++ showBoard' chunks "" 1)
       where showBoard' []     str count = str
             showBoard' (x:xs) str count =
               showBoard' xs (str ++ show count ++ "." ++ show x ++ "\n") (count+1)

instances _ [] = 0
instances x (y:ys)
  | x == y    = 1 + instances x ys
  | otherwise = instances x ys

density a = 
  let numZeros = instances 0 a
      groupsOfZeros = filter (\x -> head x == 0) (group a)
  in if null groupsOfZeros then 0 else numZeros / fromIntegral (length groupsOfZeros)

boardDensity board = sum (map density (chunksOf n board))

moves = [(a,b) | a <- [2..n-1], b <- [2..m-1]]               

bestMove board = 
  let lowestSumMoves = take 1 $ groupBy ((==) `on` snd) 
                              $ sortBy (comparing snd) (map (\x -> (x, sum $ updateBoard board x)) (moves))
  in if null lowestSumMoves
        then (0,0)
        else let lowestSumMoves' = map (\x -> fst x) (head lowestSumMoves) 
             in fst $ head $ reverse $ sortBy (comparing snd) 
                (map (\x -> (x, boardDensity $ updateBoard board x)) (lowestSumMoves'))   

solve board = solve' board [] where
  solve' board result
    | sum board == 0 = result
    | otherwise      = 
        let best = bestMove board 
        in solve' (updateBoard board best) (result ++ [best])

main :: IO ()
main = mainLoop board where
  mainLoop board = do 
    putStrLn ""
    showBoard board
    putStr "Pt: "
    a <- getLine
    case a of 
      "quit"    -> do putStrLn ""
                      return ()
      "best"    -> do putStrLn (show $ bestMove board)
                      mainLoop board
      otherwise -> let ws = splitOn "," a
                       pt = (read (head ws), read (last ws))
                   in do mainLoop (updateBoard board pt)

Isto pode ser resolvido usando uma árvore de profundidade O (3 ^ (n)). Onde n é a soma de todos os quadrados.

Primeiro considere que é trivial resolver o problema com uma árvore de O (9 ^ n), simplesmente considere todos os possíveis locais de bombardeio. Por exemplo, veja a implementação do Alfe .

Em seguida, perceba que podemos trabalhar para bombardear de baixo para cima e ainda obter um padrão mínimo de bombardeio.

  1. Comece pelo canto inferior esquerdo.
  2. Bombardeie até o esquecimento com as únicas jogadas que fazem sentido (para cima e para a direita).
  3. Mova um quadrado para a direita.
  4. Enquanto o alvo tem um valor maior que zero, considere cada uma das duas jogadas que fazem sentido (direto ou para cima e para a direita), reduza o valor do alvo em um, e faça um novo ramo para cada possibilidade.
  5. Mova outro para a direita.
  6. Enquanto o alvo tem um valor maior que zero, considere cada uma das 3 jogadas que fazem sentido (esquerda para cima, para cima e para cima), reduza o valor do alvo em um, e faça um novo branch para cada possibilidade.
  7. Repita as etapas 5 e 6 até que a linha seja eliminada.
  8. Suba uma linha e repita os passos de 1 a 7 até que o quebra-cabeça seja resolvido.

Este algoritmo está correto porque

  1. É necessário completar cada linha em algum momento.
  2. Completar uma linha sempre requer uma jogada, uma acima, outra abaixo ou dentro dessa linha.
  3. É sempre tão bom ou melhor escolher uma jogada acima da linha mais baixa que uma jogada na linha ou abaixo da linha.

Na prática, esse algoritmo fará regularmente melhor do que seu máximo teórico, pois bombardeará vizinhos regularmente e reduzirá o tamanho da pesquisa. Se assumirmos que cada bombardeio diminui o valor de 4 alvos adicionais, então nosso algoritmo será executado em O (3 ^ (n / 4)) ou aproximadamente O (1.3 ^ n).

Como esse algoritmo ainda é exponencial, seria sensato limitar a profundidade da pesquisa. Poderíamos limitar o número de ramificações permitidas para algum número, X, e uma vez que estamos nessa profundidade, forçamos o algoritmo a escolher o melhor caminho que ele identificou até agora (aquele que tem a soma total mínima da placa em uma de suas folhas terminais ). Em seguida, nosso algoritmo é executado em tempo O (3 ^ X), mas não é garantido que ele obtenha a resposta correta. No entanto, podemos sempre aumentar o X e testar empiricamente se o trade off entre o aumento da computação e as melhores respostas valer a pena.


Parece haver uma subestrutura de correspondência não-bipartida aqui. Considere o seguinte exemplo:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

A solução ótima para este caso tem tamanho 5, já que é o tamanho de uma cobertura mínima dos vértices de um ciclo de 9 por suas bordas.

Este caso, em particular, mostra que o relaxamento da programação linear que algumas pessoas postaram não é exato, não funciona e todas essas outras coisas ruins. Tenho certeza de que posso reduzir "cobrir os vértices do meu gráfico cúbico plano com o menor número possível de arestas" para o seu problema, o que me faz duvidar de que alguma das soluções gananciosas / de escalada de montanha funcione.

Eu não vejo uma maneira de resolver isso em tempo polinomial no pior dos casos. Pode haver uma solução de busca binária e de DP muito inteligente que não estou vendo.

EDIT : vejo que o concurso ( http://deadline24.pl ) é agnóstico de idioma; eles enviam um monte de arquivos de entrada e você envia as saídas. Portanto, você não precisa de algo que seja executado no pior momento polinomial. Em particular, você pode ver a entrada !

Há um monte de pequenos casos na entrada. Depois, há um caso de 10x1000, um caso de 100x100 e um caso de 1000x1000. Os três grandes casos são todos muito bem comportados. Entradas adjacentes horizontalmente geralmente têm o mesmo valor. Em uma máquina relativamente robusta, consigo resolver todos os casos usando o CPLEX em apenas alguns minutos. Eu tive sorte no 1000x1000; o relaxamento de LP passa a ter uma solução ótima integral. Minhas soluções concordam com os .ansarquivos fornecidos no pacote de dados de teste.

Eu aposto que você pode usar a estrutura da entrada de uma maneira muito mais direta do que eu faria se você desse uma olhada nela; Parece que você pode apenas cortar a primeira linha, ou duas, ou três repetidamente até que você não tenha mais nada. (Parece que, no 1000x1000, todas as linhas não estão aumentando? Acho que é de onde vem a sua "parte B").


Todo esse problema se resume a calcular uma distância de edição. Basta calcular uma variante da distância de Levenshtein entre a matriz fornecida e a matriz zero, onde as edições são substituídas por bombardeamentos, usando programação dinâmica para armazenar as distâncias entre as matrizes intermediárias. Eu sugiro usar um hash das matrizes como chave. No pseudo-Python:

memo = {}

def bomb(matrix,i,j):
    # bomb matrix at i,j

def bombsRequired(matrix,i,j):
    # bombs required to zero matrix[i,j]

def distance(m1, i, len1, m2, j, len2):
    key = hash(m1)
    if memo[key] != None: 
        return memo[key]

    if len1 == 0: return len2
    if len2 == 0: return len1

    cost = 0
    if m1 != m2: cost = m1[i,j]
    m = bomb(m1,i,j)
    dist = distance(str1,i+1,len1-1,str2,j+1,len2-1)+cost)
    memo[key] = dist
    return dist






matrix