Algoritmo de lançamento de bombas

212

Eu tenho uma n x mmatriz que consiste em números 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

"Soltar uma bomba" diminui em um o número da célula-alvo e todas as oito vizinhas, 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 (por eu não ser um leitor cuidadoso)

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

E o problema simples, quando a sequência na linha não deve aumentar:

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

7 8 5 5 2 não é possível porque 7 -> 8 cresce em uma sequência.

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

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

Kostek
fonte
4
Bem, acho que alguns campos podem ser ignorados, como no exemplo 2 3 1 5 Largar em 2,3,1 não faz sentido, porque largar neles causa algum dano de subconjunto que podemos causar ao largar em 5. Mas não podemos descubra como fazê-lo funcionar globalmente (se for da maneira correta). A limpeza 2 requer o uso de 2 bombas lançadas sobre qualquer vizinho e 5 está contendo outros conjuntos de danos. Mas então eu não sei o que fazer mais tarde, desde quando você o reescreve (depois de diminuir), então você tem duas opções (não há um único conjunto de danos).
abc
23
Isso é difícil para o NP por acaso? Parece ser uma variante do problema de cobertura máxima .
Mysticial
14
+1 por me dar algo interessante para pensar
Nick Mitchinson
3
@ Kostek, ótimo problema! Por favor, poste o link.
Coronel Panic
5
talvez deva esclarecer, você disse que a pergunta é: what's the minimum amount of bombs required to clean the board?isso significa que não é necessariamente necessário encontrar um padrão de bombardeio real, mas apenas o número mínimo de bombas?
Lie Ryan

Respostas:

38

Existe uma maneira de reduzir isso para um simples sub-problema.

Existem duas partes na explicação, o algoritmo e o motivo pelo qual o algoritmo fornece uma solução ideal. O primeiro não fará sentido sem o segundo, então vou começar com o porquê.

Se você pensa em bombardear o retângulo (assuma um retângulo grande - ainda não há arestas), poderá 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 quadrados dentro do perímetro. Vou chamar a camada de perímetro 1 e o retângulo dentro dela de camada 2.

Um insight importante é que não há ponto de bombardeio na camada 1, porque o "raio de explosão" obtido é sempre contido no raio de explosão de outro quadrado da camada 2. Você deve conseguir se convencer disso facilmente.

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

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

Mas sabemos que podemos ser gananciosos. Como 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 pelo mesmo motivo de antes - sempre há uma bomba que podemos colocar na camada 3 que afetará todos os quadrados da camada 2 que uma bomba colocada na camada 2 pode. Portanto, nunca pode nos prejudicar sermos gananciosos (nesse sentido de gananciosos).

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

Nunca nos machucamos ao bombardear 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 pode alcançar o canto tem um raio de explosão contido no raio de explosão do canto da camada interna).

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

0       A       B

C       X       Y

D       Z

Nesse ponto, o perímetro é efetivamente um loop unidimensional 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 nos cantos estranhos, e mesmo não há raio de explosão é um subconjunto de outro. Observe que se essa fosse uma linha (como o coronel Panic discute) em vez de um circuito fechado, a solução é trivial. Os pontos finais devem ser reduzidos a 0 e nunca é prejudicial bombardear os pontos adjacentes aos pontos finais, novamente porque o raio de explosão é um superconjunto. Depois de ter feito o seu ponto final 0, você ainda terá um novo ponto final; portanto, repita (até que a linha esteja com todos os 0).

Portanto, se podemos reduzir de maneira ideal um único quadrado da camada para 0, temos um algoritmo (porque cortamos o loop e agora temos uma linha reta com pontos finais). Acredito que bombardeios adjacentes ao quadrado com o valor mais baixo (dando-lhe 2 opções), de modo que o valor mais alto dentro de 2 quadrados desse valor mais baixo seja o mínimo possível (talvez você precise dividir seu bombardeio para gerenciar isso) será o ideal, mas eu ainda não tem uma prova.

PSR
fonte
+1 - eu ia escrever algo semelhante. Eu acho que você conseguiu!
Rex Kerr #
5
@beaker, por favor, leia o problema com atenção. Bombardear um quadrado reduz todos os oito vizinhos; portanto, sua suposição é correta.
darksky
20
But, we do know we can be greedy...- Eu não estou comprando isso. Considere 1 1 2 1 1 2no perímetro. O número mínimo de bombas é 4, mas existem três soluções distintas. Cada solução tem um impacto diferente na próxima camada. Desde que haja várias soluções mínimas para um perímetro, você não poderá isolar completamente o perímetro sem considerar as camadas internas. Realmente não acho que esse problema possa ser resolvido sem retroceder.
User1354557
4
Eu estava pensando nessa solução, mas não parecia tão simples assim. É verdade que você pode soltar uma bomba na camada2 para limpar a camada1, mas se houver várias soluções, elas efetuam soluções para camadas superiores.
Luka Rahne
12
@ PSR: Isso não funciona. O método de bombardeio ideal para a camada externa pode não ser globalmente ideal. Exemplo: 0011100 0100010 0000000 0000000 1110111. A maneira ideal de bombardear a primeira camada é bombardear no meio da segunda linha, levando um total de três bombas para matar a camada externa. Mas então você precisa de duas bombas para cuidar da próxima camada. O ideal requer apenas quatro bombas no total: duas nas duas primeiras linhas e duas na última linha.
Nneonneo 12/03
26

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

O problema óbvio 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 ganancioso é indiferente a qual célula ele bombeia primeiro. Obviamente, a célula central é melhor - zera todas as três células ao mesmo tempo. Isso 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 o bombardeio da 2ª, 3ª ou 4ª células. Mas bombardear a 2ª célula para sair 0 0 1 1 1é melhor do que bombardear a 3ª célula para sair 1 0 1 0 1. Como consertar isso? O problema com o bombardeio da 3ª célula é que ela nos deixa trabalhando para a esquerda e para a 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, concordo que um problema muito mais interessante seria o problema unidimensional alterado para que as extremidades se unam. Adoraria ver algum progresso nisso.

Coronel Panic
fonte
40
Não sei por que essa resposta está recebendo tantos votos positivos - o caso 1D é quase trivial, simplesmente sempre bombardeie o elemento à direita do primeiro elemento positivo. Isso funciona porque sempre existe exatamente uma maneira ideal de bombardear qualquer elemento que contenha apenas 0s à esquerda. Isso pode ser estendido para 2D para remover de maneira ideal os quadrados dos cantos, mas não vejo uma maneira óbvia de estendê-lo além disso ...?
BlueRaja - Danny Pflughoeft 8/13
3
@BlueRaja, votei positivamente porque ilustrava claramente que a abordagem gananciosa discutida nas outras respostas era insuficiente (pelo menos, precisava ser complementada com um critério adicional). Algumas opções de destino, mesmo que resultem em uma redução igual no número total, podem deixar as coisas mais espalhadas do que outras. Eu acho que essa é uma visão útil para o problema 2D.
Tim Goodman
3
E, em geral, "Se você está preso no gabinete 2D, tente primeiro o gabinete 1D" é um bom conselho.
Tim Goodman
21
@ Tim: "'experimente o caso 1D primeiro' é um bom conselho" Sim, é, o que o tornaria um excelente comentário; mas não é uma resposta ...
BlueRaja - Danny Pflughoeft 8/13
3
Eu acho que você tem um bom argumento, porém, de que o caso 1D pode ser um pouco enganador aqui, porque possui uma solução simples que não se estende prontamente para dimensões mais altas. Eu acho que o caso 1D com condições de contorno periódicas (o caso envolvente) pode ser melhor.
Tim Goodman
12

Eu tive que parar com apenas uma solução parcial, pois estava sem tempo, mas espero que até essa solução parcial forneça algumas idéias sobre uma possível abordagem para solucionar esse problema.

Quando enfrento um problema difícil, gosto de apresentar 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 em um problema 1-D. Considere uma linha:

0 4 2 1 3 0 1

De uma forma ou de outra, você sabe que precisará bombardear o 4local 4 vezes ou ao redor dele para reduzi-lo a 0. Como o lado esquerdo do local é um número menor, não há benefício em bombardear o 0ou 4bombardear o excesso 2. Na verdade, eu acredito (mas falta uma prova rigorosa) de que o bombardeio 2até o 4ponto chegar a 0 é pelo menos tão bom quanto qualquer outra estratégia para reduzi- 4lo a 0. Pode-se prosseguir na linha da esquerda para a direita em uma estratégia como isso:

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

Alguns exemplos 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 diminuir 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 na complexidade, onde essa busca pelo menos boa ainda é viável, está no limite do quadro. É claro para mim que nunca há nenhum benefício estrito para bombardear a borda externa; é melhor bombardear o local um e obter três outros espaços de graça. Diante disso, podemos dizer que bombardear o anel um 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 é realmente a única maneira de reduzir os espaços da borda para zero. Ainda mais, é trivialmente simples descobrir a estratégia ideal (na medida em que menos bom do que qualquer outra estratégia) para reduzir os números de canto para zero. Reunimos tudo isso e podemos nos aproximar muito mais de uma solução no espaço 2D.

Dada a observação sobre as peças dos cantos, podemos dizer com certeza que conhecemos a estratégia ideal para ir de qualquer quadro inicial a um quadro com zeros em todos os cantos. Este é um exemplo desse quadro (peguei emprestado os números dos dois quadros lineares acima). Eu rotulei alguns espaços de maneira diferente e vou explicar 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 linha superior e realmente se assemelha ao exemplo linear vimos anteriormente. Lembrando nossa observação anterior de que a maneira ideal de obter a linha superior até 0 é bombardear a segunda linha (a xlinha). Não há como limpar a linha superior bombardeando qualquer uma das ylinhas e nenhum benefício adicional para bombardear a linha superior bombardeando o espaço correspondente na xlinha.

Nós poderia aplicar a estratégia linear de cima (a bombardear os espaços correspondentes na xlinha), preocupando-nos unicamente com a linha superior e nada mais. Seria algo como isto:

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 atentados finais. É claro, dado que os únicos sites de bombas que reduzem o 4número na primeira coluna da segunda linha são o primeiro xe o y. Os dois bombardeios finais são claramente inferiores ao bombardeio do primeiro x, o que teria feito exatamente o mesmo (com relação ao primeiro ponto na linha superior, que não temos outra maneira de limpar). Como demonstramos que nossa estratégia atual é abaixo do ideal, é 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 a única maneira de obter os espaços com 4baixo a zero estão a bombardear alguma combinação de x, ye z. Com algumas acrobacias em mente, tenho quase certeza de que a solução ideal é bombardear xtrês vezes e adepois b. Agora é uma questão de descobrir como cheguei a essa solução e se ela revela alguma intuição que podemos usar para resolver esse problema local. Percebo que não há bombardeios ye zespaços. Tentar encontrar um canto onde bombardear esses espaços faz sentido produz um canto mais ou menos assim:

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

Para este, está claro para mim que a solução ideal é bombardear y5 vezes e z5 vezes. Vamos dar um passo adiante.

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

Aqui, ele se sente da mesma forma intuitiva de que a melhor solução é bombardear ae b6 vezes e depois x4 vezes.

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

Espero que continue!

Steven Xu
fonte
10

Para perguntas atualizadas, um algoritmo simples e ganancioso fornece o melhor resultado.

Solte as bombas A [0,0] na célula A [1,1], depois solte as bombas A [1,0] na célula A [2,1] e continue esse processo para baixo. Para limpar o canto inferior esquerdo, solte o máximo de bombas (A [N-1,0], A [N-2,0], A [N-3,0]) na célula A [N-2,1]. Isso limpará completamente as três primeiras colunas.

Com a mesma abordagem, limpe as colunas 3,4,5, depois as colunas 6,7,8, etc.

Infelizmente, isso não ajuda a encontrar a solução para o problema original.


Problema "maior" (sem restrição "não-decrescente") pode ser comprovadamente difícil para NP. Aqui está o esboço de uma prova.

Suponha que tenhamos um gráfico plano de grau até 3. Vamos encontrar uma cobertura mínima de vértices para este gráfico. Segundo o artigo da Wikipedia, esse problema é NP-difícil para gráficos planares de até 3. Isso pode ser comprovado pela redução do Planar 3SAT. E dureza do Planar 3SAT - pela redução do 3SAT. Ambas as provas são apresentadas em palestras recentes em "Limites inferiores algorítmicos" pelo prof. Erik Demaine (palestras 7 e 9).

Se dividirmos algumas arestas do gráfico original (gráfico à esquerda no diagrama), cada uma com um número par de nós adicionais, o gráfico resultante (gráfico à direita no diagrama) deve ter exatamente a mesma cobertura mínima de vértices para os vértices originais. Essa transformação permite alinhar vértices do gráfico a posições arbitrárias na grade.

insira a descrição da imagem aqui

Se colocarmos vértices gráficos apenas em linhas e colunas pares (de maneira que nenhuma aresta incida em um vértice forme um ângulo agudo), insira "ones" onde houver uma aresta e insira "zeros" em outras posições da grade, poderíamos usar qualquer solução para o problema original para encontrar uma cobertura mínima de vértices.

Evgeny Kluev
fonte
De onde vem esse gráfico da esquerda? Desculpe, não entendo bem sua explicação!
ryyst
1
@ryyst: esse gráfico da esquerda é apenas um exemplo de gráfico plano. É usado para demonstrar como transformar qualquer gráfico plano de grau até 4 no gráfico alinhado à grade e depois na matriz n * m. Um algoritmo de "lançamento de bomba" aplicado a essa matriz resolverá o problema de cobertura de vértices para este gráfico transformado e, portanto, para esse gráfico "esquerdo".
Evgeny Kluev
Ah, entendi agora e acredito que sua transformação está correta. Obrigado!
ryyst
@ EvgenyKluev, acho que agora você precisa provar que a cobertura de vértices ainda é NP-difícil para "gráficos planares de grau até 4".
precisa
@ Shahbaz: Receio que esta prova seja muito longa. Então eu adicionei o link para a prova.
Evgeny Kluev
9

Você pode representar esse problema como um problema de programação inteira . (esta é apenas uma das soluções possíveis para abordar esse 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   

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

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

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

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

Luka Rahne
fonte
8
Todos os problemas em NP pode ser formulado como problemas de programação inteira, e isso não é muito útil, a menos que já sabemos que o problema é NP-Completo
BlueRaja - Danny Pflughoeft
1
Concordo. Também não é necessário saber os movimentos exatos que devem ser feitos para saber qual é a solução.
Luka Rahne 8/03
1
Quando você define o limite para 0, o número de desigualdades ainda é 16.
darksky
9

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

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

Em placas 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*

por mais que você organize a bomba, é impossível limpar esta placa 4x4 com menos de 2 + 1 + 6 + 4 = 13 bombas.

Já foi mencionado em outras respostas que colocar a bomba na segunda esquina para eliminar a esquina nunca é pior do que colocar a bomba na própria esquina, de acordo com o quadro:

*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 um novo quadro:

 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 o número 6, 4, 3 e 2 marcado 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 duas dessas células usando uma única bomba; portanto, a bomba mínima aumentou 6 + 4 + 3 + 2; portanto, aumentando o número de bombas que usamos para limpar os cantos, obtemos o mínimo o número de bombas necessárias para este mapa se tornou 28 bombas. É impossível limpar este mapa com menos de 28 bombas, este é o limite inferior para este mapa.

Você pode usar o algoritmo ganancioso para estabelecer um limite superior. Outras respostas mostraram que um algoritmo ganancioso produz uma solução que usa 28 bombas. Como já provamos anteriormente que nenhuma solução ideal pode ter menos de 28 bombas, portanto 28 bombas são realmente uma solução ideal.

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

O algoritmo para encontrar o limite inferior é o seguinte:

  1. Escolha um elemento com o número mais alto e denomine P.
  2. Marque todas as células a dois passos de P e P como imperceptíveis.
  3. Adicione P à minimumslista.
  4. Repita a etapa 1 até que todas as células não possam ser selecionadas.
  5. Soma a minimumslista para obter o limite inferior.
Lie Ryan
fonte
9

Esta seria uma abordagem gananciosa:

  1. Calcule uma matriz de "pontuação" da ordem n X m, em que pontuação [i] [j] é a dedução total de pontos na matriz se a posição (i, j) for bombardeada. (A pontuação máxima de um ponto é 9 e a pontuação mínima é 0)

  2. Movendo-se em linha, encontre e escolha a primeira posição com a maior pontuação (digamos (i, j)).

  3. Bomba (i, j). Aumente a contagem de bombas.

  4. Se todos os elementos da matriz original não forem zero, vá para 1.

Tenho minhas dúvidas de que esta seja a solução ideal.

Editar:

A abordagem gananciosa que publiquei acima, enquanto funciona, provavelmente não nos dá a solução ideal. Então, achei que deveria adicionar alguns elementos do DP a ele.

Acho que podemos concordar que, a qualquer momento, uma das posições com a "pontuação" mais alta (pontuação [i] [j] = dedução total de pontos se (i, j) for bombardeado) deve ser direcionada. Começando com essa suposição, aqui está a nova abordagem:

NumOfBombs (M): (retorna o número mínimo de atentados necessários)

  1. Dada uma matriz M de ordem n X m. Se todos os elementos de M forem zero, retorne 0.

  2. Calcular a matriz "score" M.

    Seja k posições distintas P1, P2, ... Pk (1 <= k <= n * m), sejam as posições em M com as pontuações mais altas.

  3. return (1 + min (NumOfBombs (M1), NumOfBombs (M2), ..., NumOfBombs (Mk))))

    onde M1, M2, ..., Mk são as matrizes resultantes se bombardearmos as posições P1, P2, ..., Pk, respectivamente.

Além disso, se quisermos que a ordem das posições seja adicional, além disso, teremos que acompanhar os resultados de "min".

SidR
fonte
3
Eu me pergunto se definir pontuação como a soma dos valores atuais produziria melhores resultados. Isso essencialmente achataria o terreno com mais eficiência.
Eugene
@ Eugene: Ponto muito interessante. Eu não consigo pensar em uma razão pela qual o seu caminho não deve produzir melhores resultados ...
Sidr
@ Eugene: Talvez a soma dos valores atuais nas proximidades possa ser usada para a medida de "prioridade"? Nuke o nó com maior pontuação e mais alta prioridade ..
Sidr
Basta ler esta resposta, acho que é semelhante à segunda resposta que acabei de postar (talvez explicada um pouco mais na minha resposta). Eu acho que seria ótimo se houvesse sempre um único espaço com a pontuação máxima, porque você estaria garantido que todo bombardeio tem o maior efeito possível. A ordem dos atentados não importa, portanto, escolher o melhor a cada passo deve ser o ideal. Mas como pode haver laços para o "melhor", talvez para uma solução ideal, você precise voltar atrás e tentar as duas quando houver um empate.
Tim Goodman
1
@ Eugene, talvez eu não esteja te seguindo. Qual é a diferença entre a maior redução e a menor soma de todos os valores restantes? A soma dos valores restantes (após o bombardeio) é apenas o valor total atual menos a redução do bombardeio nesse espaço, então não são equivalentes?
Tim Goodman
8

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

Observe que a coluna da esquerda contém os números mais altos. Portanto, qualquer solução ideal deve primeiro reduzir esta coluna a zero. Assim, podemos executar um bombardeio 1-D sobre esta coluna, reduzindo todos os elementos nela a zero. Deixamos as bombas caírem na segunda coluna para causar danos máximos. Existem muitos posts aqui lidando com o caso 1D, eu acho, então 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, depois que a coluna esquerda estiver zerada, apenas cortamos 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 comprovadamente mínimo de bombas.

nneonneo
fonte
Entendi. Eu pensei em uma idéia semelhante. : S Da próxima vez vou ler com mais cuidado. Mas, graças a isso, muitas pessoas têm um problema 'bom' para resolver '.
abc
4

Programação linear inteira do Mathematica usando desvio e vinculação

Como já foi mencionado, esse problema pode ser resolvido usando a programação linear inteira (que é NP-Hard ). O Mathematica já possui 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."[Consulte 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

insira a descrição da imagem aqui

Para quem lê isso com um algoritmo ganancioso

Experimente o 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 está separado por vírgulas:

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 esse problema, minha solução contém 208 bombas. Aqui está uma solução possível (consegui resolver isso em cerca de 12 segundos).

insira a descrição da imagem aqui

Como uma maneira de testar os resultados que o Mathematica está produzindo, verifique se o seu algoritmo ganancioso pode melhorar.

escuro
fonte
Eu era capaz de fazê-lo em 219 com esta resposta: stackoverflow.com/questions/15300149/bomb-dropping-algorithm/...
Anthony Rainha
3

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

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

No exemplo dado, existem quatro cantos, {2, 1, 6, 4}. Para cada canto, não há movimento melhor do que bombardear a célula diagonal para o canto; portanto, sabemos de fato que nossos primeiros bombardeios 2 + 1 + 6 + 4 = 13 devem estar nessas células diagonais. Após 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 por meio de três atentados. Agora, temos 2 novos cantos, {2, 1} na quarta linha. Nós bombardeamos esses, outros 3 atentados. Reduzimos a matriz para 4 x 4 agora. Há um canto, no canto superior esquerdo. Nós bombardeamos isso. Agora temos 2 cantos restantes, {5, 3}. Como 5 é o maior canto, bombardeamos aquele primeiro, 5 bombardeios e, finalmente, bombardeámos os 3 no outro canto. O total é 13 + 3 + 3 + 1 + 5 + 3 = 28.

Tyler Durden
fonte
1
Eu não entendo o que você faz no caso geral após cantos bombardeio
Riad
Bombardear a esquina nunca é mais eficaz do que bombear na diagonal para dentro a partir da esquina.
psr
1
psr você não entendeu o meu post, EU SOU bombardear diagonal do canto, reler o post
Tyler Durden
11
@TylerDurden: isso só funciona porque a matriz é pequena. Em matrizes maiores, depois de bombardear a esquina, geralmente você não seria mais capaz de cortar as bordas.
Lie Ryan
3

Isso faz uma busca ampla pelo caminho mais curto (uma série de atentados) através desse "labirinto" de posições. Não, não posso provar que não há algoritmo mais rápido, desculpe.

#!/usr/bin/env python

M = ((1,2,3,4),
     (2,3,4,5),
     (5,2,7,4),
     (2,3,5,8))

def eachPossibleMove(m):
  for y in range(1, len(m)-1):
    for x in range(1, len(m[0])-1):
      if (0 == m[y-1][x-1] == m[y-1][x] == m[y-1][x+1] ==
               m[y][x-1]   == m[y][x]   == m[y][x+1] ==
               m[y+1][x-1] == m[y+1][x] == m[y+1][x+1]):
        continue
      yield x, y

def bomb(m, (mx, my)):
  return tuple(tuple(max(0, m[y][x]-1)
      if mx-1 <= x <= mx+1 and my-1 <= y <= my+1
      else m[y][x]
      for x in range(len(m[y])))
    for y in range(len(m)))

def findFirstSolution(m, path=[]):
#  print path
#  print m
  if sum(map(sum, m)) == 0:  # empty?
    return path
  for move in eachPossibleMove(m):
    return findFirstSolution(bomb(m, move), path + [ move ])

def findShortestSolution(m):
  black = {}
  nextWhite = { m: [] }
  while nextWhite:
    white = nextWhite
    nextWhite = {}
    for position, path in white.iteritems():
      for move in eachPossibleMove(position):
        nextPosition = bomb(position, move)
        nextPath = path + [ move ]
        if sum(map(sum, nextPosition)) == 0:  # empty?
          return nextPath
        if nextPosition in black or nextPosition in white:
          continue  # ignore, found that one before
        nextWhite[nextPosition] = nextPath

def main(argv):
  if argv[1] == 'first':
    print findFirstSolution(M)
  elif argv[1] == 'shortest':
    print findShortestSolution(M)
  else:
    raise NotImplementedError(argv[1])

if __name__ == '__main__':
  import sys
  sys.exit(main(sys.argv))
Alfe
fonte
1
Este algoritmo irá encontrar o menor número de movimentos, mas pode demorar um tempo muito longo. Você executou isso no conjunto de dados fornecido? Isso daria uma linha de base para a comparação de outros algoritmos.
Ryan Amos
1
Um subconjunto de 5x4 da matriz fornecida foi resolvido em cerca de 2 segundos, 5x5 já levou mais de 2 minutos. Ainda não tentei mais ;-) Sim, esse algoritmo não está otimizado para nada além da tarefa original: encontre a solução mais curta.
Alfe 9/03/2013
2
Tal é a beleza da complexidade exponencial.
Ryan Amos
3

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

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

Matriz de posições

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

Matriz de bomba

de tal maneira que

Valores das posições na matriz da bomba

Por exemplo:

B (3, 3)

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

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

    B 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 que P - B ≤ 0 )

Além disso, B deve minimizar a soma soma das quantidades de bombas.

Também podemos escrever B como a matriz feia adiante:

B como uma matriz da soma das quantidades

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

Relação entre número de bombas lançadas e valores em posições

Sendo q mn x 1 definido como

Vetor de quantidades

p mn x 1 definido como

Valores de P distribuídos como um vetor

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 da matriz para ser revertidas para resolver o sistema. Eu não a expandi, mas acredito que deve ser fácil fazê-lo em código.

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

O sistema que temos que resolver

Eu acredito que é algo fácil, quase trivial de ser resolvido com algo como o algoritmo simplex (existe um documento bastante interessante sobre isso ). No entanto, eu não conheço quase nenhuma programação linear (vou fazer um curso sobre isso no Coursera, mas é no futuro ...), tive algumas dores de cabeça tentando entender e tenho um trabalho freelance enorme para terminar, então 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. De qualquer forma, estou ansioso pelo seu feedback.

(Agradecimentos especiais por este site incrível para criar imagens a partir de expressões LaTeX )

brandizzi
fonte
Tem certeza de que suas desigualdades não são revertidas? Isso é Sq> = P? isto é, o número total de vezes que um quadrado é bombardeado é maior ou igual à matriz especificada.
darksky
1
Quando as variáveis ​​de um programa linear são restritas a números inteiros, chamamos isso de "programação linear inteira" (IP). Diferente do caso contínuo, o IP é NP-Complete. Infelizmente, o algoritmo simplex não ajuda, a menos que uma aproximação seja aceitável. E o IP já foi mencionado em outra resposta .
BlueRaja - Danny Pflughoeft
@ BlueRaja-DannyPflughoeft correto. "Despite the many crucial applications of this problem, and intense interest by researchers, no efficient algorithm is known for it.consulte a página 254. A programação linear inteira é um problema computacional muito difícil. Nossa única esperança de ser eficiente é explorar as propriedades intrínsecas sobre sua matriz de S. Não é que arbitrária depois de tudo.
darksky
3

Esta solução gananciosa parece estar correta :

Como apontado nos comentários, ele falhará em 2D. Mas talvez você possa melhorá-lo.

Para 1D:
se houver pelo menos 2 números, você não precisará disparar para o número mais à esquerda, porque disparar para o segundo não é pior . Então atire para o segundo, enquanto o primeiro não é 0, porque você precisa fazer isso. Mover para a próxima célula. Não se esqueça da última célula.

Código C ++:

void bombs(vector<int>& v, int i, int n){
    ans += n;
    v[i] -= n;
    if(i > 0)
        v[i - 1] -= n;
    if(i + 1< v.size())
        v[i + 1] -= n;
}

void solve(vector<int> v){
    int n = v.size();
    for(int i = 0; i < n;++i){
        if(i != n - 1){
            bombs(v, i + 1, v[i]);
        }
        else
            bombs(v, i, v[i])
    }
}

Então, para 2D:
Novamente: você não precisa filmar na primeira linha (se houver a segunda). Então atire para o segundo. Resolva a tarefa 1D da primeira linha. (porque você precisa torná-lo nulo). Descer. Não esqueça a última linha.

RiaD
fonte
5
Um contra-exemplo: "0110","1110","1110". Você só precisa de um tiro, mas eu acredito que seu algoritmo usaria 2.
Maniek
2

Para minimizar o número de bombas, temos que maximizar o efeito de cada bomba. Para conseguir isso, a cada passo precisamos selecionar o melhor alvo. Para cada ponto que o soma e são oito vizinhos - poderia ser usado como uma quantidade eficiente de bombardeio nesse ponto. Isso fornecerá a seqüência quase ideal de bombas.

UPD : Também devemos levar em consideração o número de zeros, pois bombiná-los é ineficiente. De fato, o problema é minimizar o número de zeros atingidos. Mas não podemos saber como qualquer passo nos aproxima desse objetivo. Concordo com a ideia de que o problema está completo. Sugiro uma abordagem gananciosa, que dará uma resposta quase real.

Noofiz
fonte
Isso não é o ideal. Contra-exemplo: 1010101, 0010100(linha superior, linha inferior) Sua abordagem exigirá 3. Pode ser feito em 2.
Mysticial
2

Eu acredito que, para minimizar a quantidade de bombas, você simplesmente precisa maximizar a quantidade de dano. Para que isso aconteça, verifique a área que possui a força mais forte. é mais forte .. e bombardeie lá .. e faça até que o campo esteja plano .. para isso 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');
CaldasGSM
fonte
Este é o mesmo algoritmo que algumas das outras respostas, mas muito mais tarde.
Psr
@psr Não é só isso. Não é o ideal.
Mysticial
Postei, porque, embora esse algoritmo tenha sido proposto, não encontrei nenhum post de código ou "prof of concept". então eu pensei que poderia ajudar na discussão .. mas .. btw @Mysticial você tem o prof que existe uma maneira mais ideal?
CaldasGSM
@CaldasGSM Não se preocupe, o problema original (sem o seqüenciamento) é difícil. Até agora, existe apenas uma resposta que a resolve de maneira ideal, mas é executada em tempo exponencial.
Mysticial
2

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

Vamos supor que possamos encontrar um ponto de queda 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 pode ser (o código é copiado e colado 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 gota perfeito.

  • Um ponto de (x, y)queda para diminui o valor em (x, y). Também pode diminuir valores em outras células.
  • Um ponto de queda a para (x, y)é melhor que um ponto de queda b, pois (x, y)se 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 para (x, y)são equivalentes se eles diminuírem o mesmo conjunto de células.
  • Um ponto de queda para (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 eficiência do que soltar uma bomba em um dos pontos de queda perfeitos (x, y).

Um ponto de descarte perfeito para um determinado campo é um ponto de descarte perfeito para qualquer uma de 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 vizinhas (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 em (2, 2)e o valor em (4, 0). Todos os outros pontos de queda para (2, 2)não são máximos, pois diminuem uma célula a menos. O ponto de descarte perfeito para (2, 2)também é o ponto de descarte perfeito para (4, 0)e é o único ponto de descarte 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 (são pontos de queda máximos para (2, 2)), mas 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 entrega perfeitos e uma certa ordem de verificações, obtenho o seguinte resultado para o exemplo da 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 funciona apenas 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

Nesses 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 calculemos 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 um deles e depois calcular o mínimo leva a esse resultado:

Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2
Tammo Freese
fonte
Este é praticamente o algoritmo ganancioso apresentado acima.
darksky
Bem, também é um algoritmo ganancioso, mas em vez de focar nos cantos e nas bordas, defini como escolher o próximo ponto de queda. Com o quadrado de exemplo de 5x7, é fácil falar sobre cantos, em um campo de 1000 x 1000, nem tanto. Se você verificar a ordem em que meu algoritmo limpa o campo, não é de fora para dentro, mas de cima para baixo / da esquerda para a direita.
Tammo Freese 11/03/13
2

Aqui está outra idéia:

Vamos começar atribuindo um peso a cada espaço no quadro para quantos números seriam reduzidos ao soltar uma bomba ali. Portanto, se o espaço tiver um número diferente de zero, ele receberá um ponto e, se qualquer espaço adjacente a ele tiver um número diferente de zero, receberá um ponto adicional. Portanto, se houver uma grade de 1000 por 1000, teremos um peso atribuído a cada um dos 1 milhão de espaços.

Em seguida, classifique a lista de espaços por peso e bombardeie aquele com o maior peso. Isso está recebendo o maior retorno possível, por assim dizer.

Depois disso, atualize o peso de cada espaço cujo peso seja afetado pela bomba. Este será o espaço que você bombardeou, e qualquer espaço imediatamente adjacente a ele e qualquer espaço imediatamente adjacente a eles. Em outras palavras, qualquer espaço que pudesse ter seu valor reduzido a zero pelo bombardeio ou o valor de um espaço vizinho reduzido a zero.

Em seguida, reordene os espaços da lista por peso. Como apenas um pequeno subconjunto de espaços teve seu peso alterado pelo bombardeio, você não precisará recorrer à lista inteira, basta movê-los pela lista.

Bombardeie o novo espaço de maior peso e repita o procedimento.

Isso garante que todo bombardeio reduz o maior número de espaços possível (basicamente, atinge o menor número possível de espaços que já são zero), então seria ótimo, exceto que eles podem ter laços de peso. Portanto, pode ser necessário rastrear as costas quando houver um empate para o peso máximo. Porém, apenas um empate para o peso máximo é importante, não outros empates, por isso espero que não seja muito para trás.

Edit: O contra-exemplo de Mysticial abaixo demonstra que, de fato, isso não é garantido como ideal, independentemente dos vínculos de peso. Em alguns casos, reduzir o peso o máximo possível em uma determinada etapa, na verdade, deixa as bombas restantes espalhadas demais para alcançar uma redução cumulativa tão alta após o segundo passo, como você poderia ter com uma escolha um pouco menos gananciosa no primeiro passo. Fiquei um tanto enganado com a noção de que os resultados são insensíveis à ordem dos atentados. Eles sãoinsensível à ordem, pois você pode pegar qualquer série de atentados e reproduzi-los desde o início em uma ordem diferente e acabar com o mesmo quadro resultante. Mas não decorre disso que você possa considerar cada atentado de forma independente. Ou, pelo menos, cada bombardeio deve ser considerado de uma maneira que leve em consideração o quão bem ele define o quadro para os bombardeios subsequentes.

Tim Goodman
fonte
ainda haverá muito retorno, no começo, já que os campos têm muito pouco zero, os pesos da maioria das células serão todos noves.
Lie Ryan
Sim, esse é um bom argumento, já que não há uma grande variedade nos pesos possíveis (apenas 0 a 9).
Tim Goodman
Ainda não estou 100% certo de quão necessário é o retorno ... pode ser instrutivo construir uma grade onde uma escolha de bombardeio ganancioso é inferior a outra opção de bombardeio ganancioso. Talvez haja uma maneira consistente de antecipar o que é melhor.
Tim Goodman
Na verdade, vejo que o coronel Panic fez isso em sua resposta. A razão pela qual uma escolha gananciosa pode ser melhor que a outra é que se deixa os números restantes mais dispersos.
Tim Goodman
3
1010101, 0010100pode ser um contra-exemplo que comprova que essa abordagem não é ótima. Esta abordagem requer 3. Pode ser feito em 2.
Mysticial
1

Bem, suponha que numeremos as posições 1, 2, ..., nx m. Qualquer sequência de descargas de bombas pode ser representada por uma sequência de números neste conjunto, onde os números podem se repetir. No entanto, o efeito no quadro é o mesmo, independentemente da ordem em que você solta as bombas; portanto, qualquer opção de descarte de bombas pode ser representada como uma lista de números nxm, em que 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 esta lista de números nxm de "chave".

Você pode tentar primeiro calcular todos os estados da placa resultantes de uma queda de bomba, depois usá-los para calcular todos os estados da placa resultantes de duas descargas de bombas, etc., até obter todos os zeros. Porém, em cada etapa, você armazenaria em cache os estados usando a chave definida acima, para poder usar esses resultados no cálculo da próxima etapa (uma abordagem de "programação dinâmica").

Mas, dependendo do tamanho de n, me dos números na grade, os requisitos de memória dessa abordagem podem ser excessivos. Você pode jogar fora todos os resultados das descargas de N bombas depois de calcular todos os resultados para N + 1, para que haja algumas economias. E, é claro, você não pode armazenar em cache nada com o custo de demorar muito mais - a abordagem de programação dinâmica troca memória por velocidade.

Tim Goodman
fonte
1
Dúvida, é possível desde (se eu entendi corretamente). n = m. Preciso de 10 ^ 6 int ponteiros para (10 ^ 6) ^ 2 células int. Eu tenho tantas tábuas quanto chaves na tabela. 10 ^ 12 dúvida eu posso alocar tanto em máquinas de 32 bits.
abc
Sim, acabei de ver seu comentário sobre placas sendo de até 1000 por 1000. Portanto, esse é um milhão de polegadas para o estado de cada placa, mais um milhão de polegadas para a contagem de bombas lançadas em cada posição. Assim, para cada placa você armazenar, você precisa de 2 milhões de ints, e há um monte de possíveis quadros de ...
Tim Goodman
Eu adicionei uma segunda resposta que usa uma abordagem diferente.
Tim Goodman
1
Sim. É uma abordagem de força bruta, mas acho que não é muito prático para uma prancha grande.
Tim Goodman
@ Kostek, por que uma estimativa tão baixa? É mais parecido com a memória k ^ (m * n), com k sendo o limite para os números com os quais o quadro é preenchido inicialmente.
Rotsor
1

Se você deseja que a solução ótima absoluta limpe a placa, terá que usar o retorno clássico, mas se a matriz for muito grande, levará séculos para encontrar a melhor solução, se você quiser uma solução ideal "possível", poderá usar o algoritmo ganancioso , se você precisar de ajuda para escrever o algoritmo, eu posso ajudá-lo

Venha para pensar que é o melhor caminho. Faça outra matriz lá, você armazena os pontos que remove, soltando uma bomba lá, em seguida, escolha a célula com o máximo de pontos e solte a bomba lá, atualize a matriz de pontos e continue. Exemplo:

2 3 5 -> (2+(1*3)) (3+(1*5)) (5+(1*3))
1 3 2 -> (1+(1*4)) (3+(1*7)) (2+(1*4))
1 0 2 -> (1+(1*2)) (0+(1*5)) (2+(1*2))

valor da célula +1 para cada célula adjacente com um valor maior que 0

cosmin.danisor
fonte
7
terá que usar o backtracking clássico . Você tem uma prova disso?
Shahbaz
Não tenho certeza. É do concurso para o qual estou me preparando (do ano anterior). Os limites são 1 <= n, m <= 1000 (não sei se é grande ou não). De qualquer forma, você precisa de uma resposta exata (é semelhante ao concurso CERC e assim por diante). O prazo não é dado, nem respostas, nem soluções na página do concurso.
abc
bem todos os outro algoritmo vai lhe dar uma melhor solução possível, mas até que você experimentá-los todos (backtracking), você não vai saber se essa solução é a melhor
cosmin.danisor
2
você não precisa usar o backtracking porque é uma combinação que você procura, não permutaion. Ordem de bombas droping não é importante
Luka Rahne
então você pode tentar usar uma variação de ganancioso. a cada passo criar uma nova matriz e cada ponto terá o valor de sua cela + 1 para cada célula ao lado dela> 0 desta forma irá escolher melhor onde a cair nos próximos bombas
cosmin.danisor
1

Força Bruta!

Sei que não é eficiente, mas mesmo que você encontre um algoritmo mais rápido, sempre poderá testar esse resultado para saber quão preciso é.

Use alguma recursão, como esta:

void fn(tableState ts, currentlevel cl)
{
  // first check if ts is all zeros yet, if not:
  //
  // do a for loop to go through all cells of ts, 
  // for each cell do a bomb, and then
  // call: 
  // fn(ts, cl + 1);

}

Você pode tornar isso mais eficiente armazenando em cache, se uma maneira diferente levar ao mesmo resultado, você não deve repetir as mesmas etapas.

Para elaborar:

se a célula de bombardeio 1,3,5 leva ao mesmo resultado que a célula de bombardeio 5,3,1, então você não deve refazer todas as próximas etapas novamente nos dois casos; apenas 1 é suficiente, você deve armazenar em algum lugar estados da tabela e use seus resultados.

Um hash de estatísticas da tabela pode ser usado para fazer uma comparação rápida.

sharp12345
fonte
1
  1. Nunca bombardeie a fronteira (a menos que o quadrado não tenha um vizinho que não seja da fronteira)
  2. Canto zero.
  3. Para zerar o canto, solte o valor do canto um quadrado na diagonal (o único vizinho não-limite)
  4. Isso criará novos cantos. Vá para 2

Edit: não percebeu que Kostek sugeriu quase a mesma abordagem, então agora faço uma afirmação mais forte: se os cantos a serem limpos são escolhidos para estar sempre na camada mais externa, então é ideal.

No exemplo do OP: soltar 2 (como 1 + 1 ou 2) em qualquer outra coisa que não em 5 não leva a acertar qualquer quadrado que cair em 5 seria atingido. Então, simplesmente precisamos soltar 2 em 5 (e 6 na parte inferior esquerda 1 ...)

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

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

Considere limpar apenas os que foram intencionalmente limpos, limpar 0 cantos de valor não custa nada e simplifica o pensamento a respeito.

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


Depois de dormir bem, percebi que isso não é verdade. Considerar

  ABCDE    
1 01000
2 10000
3 00000
4 00000

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

Alpedar
fonte
Mas isso é ideal?
Mysticial
7
Novas esquinas podem ser bombardeadas de duas maneiras (se a maior parte dos cantos contiver o menor dos quatro valores). Qual é o melhor bombardeio?
abc
Eu estava pensando em uma abordagem semelhante, e quando você chegar a uma situação como Kostek descrito, em seguida, começar a usar retrocesso ...
Karoly Horvath
Os cantos fornecem quantidades mínimas de bombas a serem lançadas no quadrado diagonal. Mas depois de zerá-los, o próximo bloco de borda não terá necessariamente o ponto ideal óbvio. É uma boa maneira de reduzir o espaço de pesquisa.
Eugene
Que tal escolher a nova diagonal de canto que produz a maior contagem total na caixa de ocorrências?
Julgador Maygarden
1

Aqui está minha solução. Ainda não escreverei no código, pois não tenho tempo, mas acredito que isso deve produzir um número ideal de movimentos a cada vez - embora não tenha certeza de quão eficiente seria encontrar os pontos a bombardear.

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

Em segundo lugar, como muitos outros afirmaram, bombardear 1-off a diagonal dos cantos é o ideal, pois atinge 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 último, não importa (em teoria) Nós bombardeamos os primeiros porque facilita as decisões posteriores (na prática) Bombardeamos o ponto que afeta mais pontos, ao mesmo tempo bombardeamos esses cantos.

Vamos definir Pontos de Resistência como os pontos do tabuleiro com os pontos mais não bombeáveis + o maior número de 0s ao seu redor

pontos não-bombeáveis podem ser definidos como pontos que não existem no nosso escopo atual do fórum que estamos analisando.

Também definirei 4 limites que manipularão nosso escopo: Superior = 0, Esquerdo = 0, Baixo = k, Direito = j. (valores a começar)

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

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 nossos cantos. Os pontos 'fora do limite' não são bombeáveis ​​(existem 5 pontos fora do escopo para cada canto). Então, bombardeamos os pontos na diagonal um dos cantos primeiro.

Algoritmo:

  1. Encontre os 4 pontos de bomba ideais.
  2. Se um ponto de bomba estiver bombardeando um ponto de resistência que está tocando 2 limites (ou seja, um canto), bombeie até esse ponto ser 0. Caso contrário, bombeie cada um até que um dos pontos de resistência que tocam no ponto ideal de bomba seja 0.
  3. para cada limite: if (sum (bound) == 0) limite avançado

repita até TOP = INFERIOR e ESQUERDA = DIREITA

Vou tentar escrever o código atual mais tarde

Etai
fonte
1

Você poderia usar o planejamento do espaço de estado. Por exemplo, usando A * (ou uma de suas variantes) juntamente com uma heurística f = g + hcomo esta:

  • g: número de bombas lançadas até agora
  • h: soma de todos os valores da grade divididos por 9 (que é o melhor resultado, o que significa que temos uma heurística admissível)
キ キ ジ
fonte
1

Eu também tenho 28 jogadas. Eu usei dois testes para a melhor jogada seguinte: primeiro, a jogada que produz a soma mínima para o tabuleiro. Segundo, para somas iguais, o movimento que produz a densidade máxima, definido como:

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

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

SAÍDA:
* Principal> resolver placa
[(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)
groovy
fonte
1

Parece haver uma subestrutura correspondente não bipartida aqui. Considere a seguinte instância:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

A solução ideal para este gabinete tem tamanho 5, já que é o tamanho de uma cobertura mínima dos vértices de um ciclo de 9 pelas bordas.

Esse 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 planar o mínimo possível de arestas" "ao seu problema, o que me faz duvidar se alguma das soluções gananciosas / escaladas vai funcionar.

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

EDIT : Vejo que o concurso ( http://deadline24.pl ) é independente de idioma; eles enviam vários arquivos de entrada e você envia a eles saídas. Portanto, você não precisa de algo que seja executado no pior momento polinomial. Em particular, você pode ver a entrada !

Existem vários casos pequenos na entrada. Depois, há um caso de 10x1000, um caso de 100x100 e um caso de 1000x1000. Os três casos grandes são todos muito bem-comportados. As entradas adjacentes horizontalmente normalmente têm o mesmo valor. Em uma máquina relativamente robusta, sou capaz de resolver todos os casos por força bruta usando o CPLEX em apenas alguns minutos. Eu tive sorte no 1000x1000; o relaxamento do LP tem uma solução ideal integral. Minhas soluções concordam com os .ansarquivos fornecidos no pacote de dados de teste.

Aposto que você pode usar a estrutura da entrada de uma maneira muito mais direta do que eu, se você desse uma olhada; parece que você pode cortar a primeira linha, ou duas ou três repetidamente, até não ter mais nada. (Parece que no 1000x1000 todas as linhas não aumentam? Acho que é daí que vem a sua "parte B"?)

tmyklebu
fonte
Sim. Às vezes, apenas pulo parte "irrelevante" do texto. Basta ter uma idéia breve e assim por diante. Dessa vez, basicamente, mude o nível de fácil para difícil como o inferno: P De qualquer forma, eu sei que você pode tentar criar uma heurística com um conjunto de entradas "conhecido". Por outro lado, acho que, se a resposta não for pontos percentuais, deve haver algum algoritmo que funcione facilmente durante 5h. Tudo o que encontrei tinha uma complexidade muito grande. Então eu lê-lo com mais cuidado, quando alguém perguntou sobre a origem :)
abc
Podemos dizer obrigado por pensar em muitas pessoas, mas duvido que isso possa acontecer em tempo polinomial. É engraçado como uma restrição simples altera o nível de tarefa de fácil para impossível.
abc
@ Kostek: Desculpe se não estava claro. Eu sou ... muito ruim em dar explicações em um nível apropriado para o público. :) Onde eu não estava clara?
tmyklebu
1

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

Portanto, 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é que eu achatasse tudo. Alguns têm defendido o uso de dano potencial simples (ou seja, pontuação de 0 a 9) como métrica, mas isso fica aquém do impacto das células de alto valor e da não utilização de sobreposição de dano. 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 contagem alta, em vez de bater diretamente nas células.

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

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

namespace StackOverflow
{
  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
zeFrenchy
fonte
1

Isso 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), basta considerar todos os locais de bombardeio possíveis. Para um exemplo, consulte a implementação da 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 no canto inferior esquerdo.
  2. Bombeie-o para o esquecimento com as únicas peças que fazem sentido (para cima e para a direita).
  3. Mova um quadrado para a direita.
  4. Enquanto o alvo tiver um valor maior que zero, considere cada uma das 2 jogadas que fazem sentido (para cima ou para cima e para a direita), reduza o valor do alvo em um e faça uma nova ramificação para cada possibilidade.
  5. Mova outro para a direita.
  6. Enquanto o alvo tiver um valor maior que zero, considere cada uma das três jogadas que fazem sentido (para cima, para cima e para cima e para a direita), reduza o valor do alvo em um e faça uma nova ramificação para cada possibilidade.
  7. Repita as etapas 5 e 6 até a linha ser eliminada.
  8. Mova uma fila e repita as etapas 1 a 7 até que o quebra-cabeça seja resolvido.

Este algoritmo está correto porque

  1. É necessário concluir cada linha em algum momento.
  2. A conclusão de uma linha sempre exige uma reprodução acima, abaixo ou dentro dessa linha.
  3. É sempre tão bom ou melhor escolher uma jogada acima da menor linha não limpa do que uma jogada na linha ou abaixo da linha.

Na prática, esse algoritmo se sai regularmente melhor do que o máximo teórico, porque bombardeia regularmente os vizinhos e reduz o tamanho da pesquisa. Se assumirmos que cada bombardeio diminui o valor de 4 alvos adicionais, nosso algoritmo será executado em O (3 ^ (n / 4)) ou aproximadamente O (1,3 ^ n).

Como esse algoritmo ainda é exponencial, seria aconselhável limitar a profundidade da pesquisa. Podemos limitar o número de ramificações permitidas a algum número, X, e uma vez que estamos tão profundos, forçamos o algoritmo a escolher o melhor caminho que ele identificou até agora (aquele que possui a soma total mínima da placa em uma de suas folhas terminais ) Então, nosso algoritmo é garantido para executar em O (3 ^ X), mas não é garantido que você obtenha a resposta correta. Entretanto, sempre podemos aumentar o X e testar empiricamente se vale a pena a troca entre aumento da computação e melhores respostas.

Ben Haley
fonte
1

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 é ideal, mas pode ser otimizado através da busca de uma melhor função de avaliação.

.. mas pensando nesse problema, eu estava pensando que um dos principais problemas é obter números abandonados no meio de zeros em algum momento, então eu adotaria outra abordagem .. que é dominar valores mínimos em zero e tentar zeros de escape possível, o que leva a uma minimização geral de valores mínimos mínimos, aproximadamente

Khaled A Khunaifer
fonte
0

Todo esse problema se resume a calcular uma distância de edição. Simplesmente calcule uma variante da distância de Levenshtein entre a matriz fornecida e a matriz zero, onde as edições são substituídas por bombardeios, usando programação dinâmica para armazenar as distâncias entre matrizes intermediárias. 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
Aerimore
fonte
0

Esta foi uma resposta para a primeira pergunta feita. Eu não tinha notado que ele mudou os parâmetros.

Crie uma lista de todos os destinos. Atribua um valor ao destino com base no número de valores positivos impactados por uma queda (ela própria e todos os vizinhos). O valor mais alto seria um nove.

Classifique os destinos pelo número de destinos impactados (Decrescente), com uma classificação descendente secundária na soma de cada destino impactado.

Solte uma bomba no alvo mais alto, depois recalcule os alvos e repita até que todos os valores sejam zero.

Concordado, isso nem sempre é o melhor. Por exemplo,

100011
011100
011100
011100
000000
100011

Esta abordagem levaria 5 bombas para limpar. Idealmente, você pode fazê-lo em 4. Ainda assim, bem perto e não há retorno. Para a maioria das situações, será ideal ou muito próximo.

Usando os números dos problemas originais, essa abordagem resolve em 28 bombas.

Adicionando código para demonstrar essa abordagem (usando um formulário com um botão):

         private void button1_Click(object sender, EventArgs e)
    {
        int[,] matrix = new int[10, 10] {{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}};


        int value = 0;
        List<Target> Targets = GetTargets(matrix);
        while (Targets.Count > 0)
        {
            BombTarget(ref matrix, Targets[0]);
            value += 1;
            Targets = GetTargets(matrix);
        }
        Console.WriteLine( value);
        MessageBox.Show("done: " + value);
    }

    private static void BombTarget(ref int[,] matrix, Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[a, b] > 0)
                        {
                            matrix[a, b] -= 1;
                        }
                    }
                }
            }
        }
        Console.WriteLine("Dropped bomb on " + t.x + "," + t.y);
    }

    private static List<Target> GetTargets(int[,] matrix)
    {
        List<Target> Targets = new List<Target>();
        int width = matrix.GetUpperBound(0);
        int height = matrix.GetUpperBound(1);
        for (int x = 0; x <= width; x++)
        {
            for (int y = 0; y <= height; y++)
            {
                Target t = new Target();
                t.x = x;
                t.y = y;
                SetTargetValue(matrix, ref t);
                if (t.value > 0) Targets.Add(t);
            }
        }
        Targets = Targets.OrderByDescending(x => x.value).ThenByDescending( x => x.sum).ToList();
        return Targets;
    }

    private static void SetTargetValue(int[,] matrix, ref Target t)
    {
        for (int a = t.x - 1; a <= t.x + 1; a++)
        {
            for (int b = t.y - 1; b <= t.y + 1; b++)
            {
                if (a >= 0 && a <= matrix.GetUpperBound(0))
                {
                    if (b >= 0 && b <= matrix.GetUpperBound(1))
                    {
                        if (matrix[ a, b] > 0)
                        {
                            t.value += 1;
                            t.sum += matrix[a,b];
                        }

                    }
                }
            }
        }

    }

Uma aula que você precisará:

        class Target
    {
        public int value;
        public int sum;
        public int x;
        public int y;
    }
Anthony Queen
fonte
1
Não é o ideal. Contra-exemplo: 09090Essa abordagem requer 18 bombas. Isso pode ser feito em 9.
Mysticial
@Mysticial Você não leu a resposta completamente. Como é baseado no número de campos diferentes de zero afetados, esse algoritmo bombardeava o zero médio e seria feito em 9 quedas. O valor alto de 9 é porque existem até oito vizinhos e ele próprio.
Anthony Rainha
Então que tal 1010101, 0010100?
Mysticial
@Mysticial Para o primeiro, primeiro zero, o último zero seria atingido. Seriam duas gotas. Isso porque cada vez que lança uma bomba, recalcula o próximo melhor alvo. Para o último exemplo, o zero do meio novamente; Uma gota.
Anthony Rainha
1
@ AnthonyQueen: isso não funciona. consulte chat.stackoverflow.com/transcript/message/8224273#8224273 para o meu contra-exemplo.
N