Algoritmo de lanzamiento de bomba

Tengo una n x mmatriz que consiste en enteros no negativos. Por ejemplo:

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

"Lanzar una bomba" disminuye en uno el número de la celda objetivo y sus ocho vecinos, a un mínimo de cero.

x x x 
x X x
x x x

¿Qué es un algoritmo que determinaría la cantidad mínima de bombas necesarias para reducir todas las celdas a cero?

Opción B (debido a que no soy un lector cuidadoso)

En realidad, la primera versión del problema no es la que busco respuesta. No leí cuidadosamente toda la tarea, hay restricciones adicionales, digamos:

¿Qué pasa con el problema simple, cuando la secuencia en la fila no debe aumentar:

8 7 6 6 5 es posible secuencia de entrada

7 8 5 5 2 no es posible ya que 7 -> 8 crece en una secuencia.

Tal vez encontrar la respuesta para el caso "más fácil" ayudaría a encontrar una solución para el más difícil.

PD: Creo que cuando tenemos varias situaciones que requieren bombas mínimas para despejar la línea superior, elegimos una que use la mayoría de las bombas en el "lado izquierdo" de la fila. ¿Todavía alguna prueba que pueda ser correcta?

Hay una manera de reducir esto a un simple subproblema.

Hay dos partes en la explicación, el algoritmo y la razón por la cual el algoritmo proporciona una solución óptima. El primero no tendrá sentido sin el segundo, así que comenzaré con el por qué.

Si piensa en bombardear el rectángulo (suponga un rectángulo grande, todavía no hay bordes) puede ver que la única forma de reducir el rectángulo hueco de cuadrados en el perímetro a 0 es bombardear el perímetro o bombardear el rectángulo hueco de cuadrados justo dentro del perímetro. Llamaré al perímetro capa 1, y al rectángulo dentro de él capa 2.

Una idea importante es que no hay un punto de bombardeo de la capa 1, porque el "radio de explosión" que obtienes al hacerlo siempre está contenido dentro del radio de explosión de otro cuadrado de la capa 2. Deberías poder convencerte fácilmente de esto.

Entonces, podemos reducir el problema a encontrar una forma óptima de bombardear el perímetro, luego podemos repetir eso hasta que todos los cuadrados sean 0.

Pero, por supuesto, eso no siempre encontrará una solución óptima si es posible bombardear el perímetro de una manera menos que óptima, pero al usar X bombas adicionales, el problema de reducir la capa interna es más simple con> X bombas. Entonces, si llamamos a la capa uno de permisos, si colocamos bombas X adicionales en algún lugar de la capa 2 (justo dentro de la capa 1), ¿podemos reducir el esfuerzo de bombardear más tarde la capa 2 en más de X? En otras palabras, tenemos que demostrar que podemos ser codiciosos al reducir el perímetro exterior.

Pero, sabemos que podemos ser codiciosos. Debido a que ninguna bomba en la capa 2 puede ser más eficiente para reducir la capa 2 a 0 que una bomba colocada estratégicamente en la capa 3. Y por la misma razón que antes, siempre hay una bomba que podemos colocar en la capa 3 que afectará a cada casilla de la capa 2 que puede colocar una bomba en la capa 2. Entonces, nunca nos puede hacer daño ser codiciosos (en este sentido de codicia).

Entonces, todo lo que tenemos que hacer es encontrar la manera óptima de reducir el permiso a 0 bombardeando la siguiente capa interna.

Nunca nos duele bombardear primero la esquina a 0, porque solo la esquina de la capa interna puede alcanzarla, por lo que realmente no tenemos otra opción (y, cualquier bomba en el perímetro que pueda alcanzar la esquina tiene un radio de explosión contenido en el radio de explosión desde la esquina de la capa interna).

Una vez que lo hayamos hecho, los cuadrados en el perímetro adyacente a la esquina 0 solo se pueden alcanzar por 2 cuadrados desde la capa interna:

0       A       B

C       X       Y

D       Z

En este punto, el perímetro es efectivamente un circuito cerrado de 1 dimensión, porque cualquier bomba reducirá 3 cuadrados adyacentes. Excepto por algunas rarezas cerca de las esquinas: X puede "golpear" A, B, C y D.

Ahora no podemos usar ningún truco de radio de explosión: la situación de cada cuadrado es simétrica, a excepción de las esquinas extrañas, e incluso si no hay radio de explosión es un subconjunto de otro. Tenga en cuenta que si se tratara de una línea (como explica el Coronel Panic) en lugar de un circuito cerrado, la solución es trivial. Los puntos finales deben reducirse a 0, y nunca le perjudica bombardear los puntos adyacentes a los puntos finales, nuevamente porque el radio de explosión es un superconjunto. Una vez que haya hecho su punto final 0, todavía tiene un nuevo punto final, así que repita (hasta que la línea sea todo 0).

Entonces, si podemos reducir de manera óptima un solo cuadrado en la capa a 0, tenemos un algoritmo (porque hemos cortado el ciclo y ahora tenemos una línea recta con puntos finales). Creo que el bombardeo adyacente al cuadrado con el valor más bajo (que le da 2 opciones) de modo que el valor más alto dentro de 2 cuadrados de ese valor más bajo sea el mínimo posible (puede que tenga que dividir su bombardeo para manejar esto) será óptimo, pero yo ¿No tiene (todavía?) una prueba.

Pólya dice "Si no puede resolver un problema, entonces hay un problema más fácil que puede resolver: encontrarlo".

El problema más simple y obvio es el problema unidimensional (cuando la cuadrícula es una sola fila). Comencemos con el algoritmo más simple: bombardear con avidez al objetivo más grande. ¿Cuándo sale esto mal?

Dado 1 1 1, el codicioso algoritmo es indiferente a qué célula bombardea primero. Por supuesto, la celda central es mejor: pone a cero las tres celdas a la vez. Esto sugiere un nuevo algoritmo A, "bomba para minimizar la suma restante". ¿Cuándo sale mal este algoritmo?

Dado 1 1 2 1 1, el algoritmo A es indiferente entre bombardear las células 2da, 3ra o 4ta. Pero bombardear la segunda celda para irse 0 0 1 1 1es mejor que bombardear la tercera celda para irse 1 0 1 0 1. ¿Cómo arreglar eso? El problema con bombardear la tercera celda es que nos deja trabajar a la izquierda y a la derecha, lo que debe hacerse por separado.

¿Qué tal "bomba para minimizar la suma restante, pero maximizar el mínimo a la izquierda (de donde bombardeamos) más el mínimo a la derecha". Llame a este algoritmo B. ¿Cuándo sale mal este algoritmo?

Editar: después de leer los comentarios, estoy de acuerdo en que un problema mucho más interesante sería el problema unidimensional cambiado para que los extremos se unan. Me encantaría ver algún progreso en eso.

Tuve que detenerme solo en una solución parcial ya que no tenía tiempo, pero espero que incluso esta solución parcial proporcione algunas ideas sobre un enfoque potencial para resolver este problema.

Cuando me enfrento a un problema difícil, me gusta pensar en problemas más simples para desarrollar una intuición sobre el espacio del problema. Aquí, el primer paso que tomé fue reducir este problema 2-D a un problema 1-D. Considera una línea:

0 4 2 1 3 0 1

De una forma u otra, sabes que necesitarás bombardear en el 4lugar o alrededor de él 4 veces para bajarlo a 0. Dado que a la izquierda del lugar hay un número menor, no hay ningún beneficio en bombardear 0o 4sobre bombardear 2. De hecho, creo (pero me falta una prueba rigurosa) que bombardear 2hasta que el 4punto baje a 0 es al menos tan bueno como cualquier otra estrategia para 4bajarlo a 0. Se puede avanzar por la línea de izquierda a derecha en una estrategia Me gusta esto:

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

Un par de muestras de órdenes de bombardeo:

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

La idea de comenzar con un número que debe ir de una forma u otra es atractiva porque de repente se puede encontrar una solución que, según algunos, es al menos tan buena como todas las demás.

El siguiente paso en la complejidad en esta búsqueda de al menos tan buena es todavía viable está en el borde de la placa. Para mí está claro que nunca hay un beneficio estricto para bombardear el borde exterior; es mejor bombardear el lugar y obtener otros tres espacios gratis. Dado esto, podemos decir que bombardear el anillo dentro del borde es al menos tan bueno como bombardear el borde. Además, podemos combinar esto con la intuición de que bombardear el derecho dentro del borde es en realidad la única forma de reducir los espacios de borde a 0. Aún más, es trivialmente simple descubrir la estrategia óptima (en el sentido de que está en menos bueno que cualquier otra estrategia) para reducir los números de esquina a 0. Ponemos todo esto junto y podemos acercarnos mucho más a una solución en el espacio 2D.

Dada la observación sobre las esquinas, podemos decir con certeza que conocemos la estrategia óptima para pasar de cualquier tablero inicial a un tablero con ceros en todas las esquinas. Este es un ejemplo de dicha tabla (tomé prestados los números de las dos tablas lineales anteriores). He etiquetado algunos espacios de manera diferente, y explicaré por qué.

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

Se dará cuenta de la fila superior realmente se parece mucho al ejemplo lineal vimos anteriormente. Recordando nuestra observación anterior de que la forma óptima de bajar la fila superior a 0 es bombardear la segunda fila (la xfila). No hay forma de despejar la fila superior bombardeando ninguna de las yfilas y no hay ningún beneficio adicional al bombardear la fila superior sobre bombardear el espacio correspondiente en la xfila.

Nos podríamos aplicar la estrategia lineal desde arriba (el bombardeo de los espacios correspondientes de la xfila), preocuparnos solamente por la fila superior y nada más. Sería algo así:

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

La falla en este enfoque se vuelve muy obvia en los dos bombardeos finales. Está claro, dado que los únicos sitios de bombas que reducen la 4cifra en la primera columna de la segunda fila son el primero xy el y. Los dos últimos bombardeos son claramente inferiores a solo bombardear el primero x, lo que habría hecho exactamente lo mismo (con respecto al primer lugar en la fila superior, que no tenemos otra forma de eliminar). Como hemos demostrado que nuestra estrategia actual es subóptima, es claramente necesaria una modificación en la estrategia.

En este punto, puedo dar un paso atrás en complejidad y enfocarme en una esquina. Consideremos este:

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

Está claro que la única manera de conseguir los espacios con 4hasta cero son para bombardear una combinación de x, yy z. Con algunas acrobacias en mi mente, estoy bastante seguro de que la solución óptima es bombardear xtres veces y aluego b. Ahora es cuestión de averiguar cómo llegué a esa solución y si revela alguna intuición que podamos usar para resolver incluso este problema local. Noto que no hay bombardeos yy zespacios. Intentar encontrar un rincón donde bombardear esos espacios tiene sentido produce un rincón que se ve así:

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

Para este, es claro para mí que la solución óptima es bombardear y5 veces y z5 veces. Vamos un paso más allá.

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

Aquí, se siente igualmente intuitivo que la solución óptima es bombardear ay b6 veces y luego x4 veces.

Ahora se convierte en un juego de cómo convertir esas intuiciones en principios sobre los que podemos construir.

¡Con suerte para continuar!

Para una pregunta actualizada, un algoritmo codicioso simple da un resultado óptimo.

Coloca bombas A [0,0] en la celda A [1,1], luego suelta bombas A [1,0] en la celda A [2,1] y continúa este proceso hacia abajo. Para limpiar la esquina inferior izquierda, suelte las bombas max (A [N-1,0], A [N-2,0], A [N-3,0]) en la celda A [N-2,1]. Esto limpiará completamente las primeras 3 columnas.

Con el mismo enfoque, limpie las columnas 3,4,5, luego las columnas 6,7,8, etc.

Lamentablemente, esto no ayuda a encontrar una solución para el problema original.

Se puede demostrar que el problema "mayor" (sin la restricción "no engrasante") es NP-duro. Aquí hay un boceto de una prueba.

Supongamos que tenemos un gráfico plano de grado hasta 3. Busquemos el mínimo cobertura vértice para este gráfico. Según el artículo de Wikipedia, este problema es NP-difícil para gráficos planos de grado hasta 3. Esto podría probarse mediante la reducción de Planar 3SAT. Y dureza de Planar 3SAT - por reducción de 3SAT. Ambas pruebas se presentan en conferencias recientes en "Algorithmic Lower Bounds" por el profesor. Erik Demaine (conferencias 7 y 9).

Si dividimos algunos bordes del gráfico original (gráfico izquierdo en el diagrama), cada uno con un número par de nodos adicionales, el gráfico resultante (gráfico derecho en el diagrama) debería tener exactamente la misma cobertura mínima de vértice para los vértices originales. Dicha transformación permite alinear vértices de gráficos a posiciones arbitrarias en la cuadrícula.

Si colocamos vértices del gráfico solo en filas y columnas pares (de tal manera que no haya dos bordes incidentes en un vértice que formen un ángulo agudo), inserte "unos" donde haya un borde e inserte "ceros" en otras posiciones de la cuadrícula, podríamos usar cualquier solución para el problema original para encontrar la cobertura mínima de vértice.

Puede representar este problema como programación entera problema de . (esta es solo una de las posibles soluciones para abordar este problema)

Tener puntos:

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

se pueden escribir 16 ecuaciones donde, por ejemplo, para el punto f

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

minimizado sobre la suma de todos los índices y la solución entera.

La solución es, por supuesto, la suma de estos índices.

Esto se puede simplificar aún más estableciendo todos los xi en los límites 0, por lo que terminará teniendo una ecuación 4 + 1 en este ejemplo.

El problema es que no hay un algoritmo trivial para resolver tales problemas. No soy experto en esto, pero resolver este problema como programación lineal es NP difícil.

Esta es una respuesta parcial, estoy tratando de encontrar un límite inferior y un límite superior que podría ser el número posible de bombas.

En tableros 3x3 y más pequeños, la solución es trivialmente siempre la celda numerada más grande.

En tableros de más de 4x4, el primer límite inferior obvio es la suma de las esquinas:

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

Independientemente de cómo organice la bomba, es imposible despejar este tablero 4x4 con menos de 2 + 1 + 6 + 4 = 13 bombas.

Se ha mencionado en otras respuestas que colocar la bomba en la segunda esquina para eliminar la esquina nunca es peor que colocar la bomba en la esquina misma, así que dado el tablero:

*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 poner a cero las esquinas colocando bombas en la segunda esquina para dar una nueva tabla:

 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

Hasta aquí todo bien. Necesitamos 13 bombas para despejar las esquinas.

Ahora observe los números 6, 4, 3 y 2 marcados a continuación:

 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

No hay forma de bombardear dos de esas celdas con una sola bomba, por lo que la bomba mínima se ha incrementado en 6 + 4 + 3 + 2, por lo que al agregar el número de bombas que usamos para despejar las esquinas, obtenemos que el mínimo El número de bombas necesarias para este mapa se ha convertido en 28 bombas. Es imposible limpiar este mapa con menos de 28 bombas, este es el límite inferior para este mapa.

Puede usar un algoritmo codicioso para establecer un límite superior. Otras respuestas han demostrado que un algoritmo codicioso produce una solución que usa 28 bombas. Como hemos demostrado anteriormente que ninguna solución óptima puede tener menos de 28 bombas, por lo tanto, 28 bombas es una solución óptima.

Aunque codicioso y el método para encontrar el límite mínimo que he mencionado anteriormente no converge, supongo que tienes que volver a verificar todas las combinaciones.

El algoritmo para encontrar el límite inferior es el siguiente:

1. Elija un elemento con el número más alto, asígnele el nombre P.
2. Marque todas las celdas a dos pasos de P y P en sí como no marcables.
3. Agregue P a la minimumslista.
4. Repita con el paso 1 hasta que todas las celdas no se puedan marcar.
5. Suma la minimumslista para obtener el límite inferior.

Este sería un enfoque codicioso:

1. Calcule una matriz de "puntaje" de orden n X m, donde el puntaje [i] [j] es la deducción total de puntos en la matriz si se bombardea la posición (i, j). (La puntuación máxima de un punto es 9 y la puntuación mínima es 0)

2. Moviendo la fila sabiamente, encuentre y elija la primera posición con la puntuación más alta (digamos (i, j)).

3. Bomba (i, j). Aumentar el recuento de bombas.

4. Si todos los elementos de la matriz original no son cero, pase a 1.

Sin embargo, tengo mis dudas de que esta sea la solución óptima.

Editar:

El enfoque codicioso que publiqué anteriormente, aunque funciona, probablemente no nos brinde la solución óptima. Así que pensé que debería agregarle algunos elementos de DP.

Creo que podemos estar de acuerdo en que en cualquier momento, una de las posiciones con el "puntaje" más alto (puntaje [i] [j] = deducción total de puntos si (i, j) es bombardeada) debe ser atacada. Comenzando con esta suposición, aquí está el nuevo enfoque:

NumOfBombs (M): (devuelve el número mínimo de bombardeos requeridos)

1. Dada una Matriz M de orden n X m. Si todos los elementos de M son cero, entonces devuelve 0.

2. Calcule la matriz de "puntuación" M.

   Deje que las k posiciones distintas P1, P2, ... Pk (1 <= k <= n * m), sean las posiciones en M con las puntuaciones más altas.

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

   donde M1, M2, ..., Mk son las matrices resultantes si bombardeamos las posiciones P1, P2, ..., Pk respectivamente.

Además, si queremos que el orden de las posiciones sea nuclear además de esto, tendríamos que hacer un seguimiento de los resultados de "min".

Su nuevo problema, con los valores no decrecientes en las filas, es bastante fácil de resolver.

Observe que la columna izquierda contiene los números más altos. Por lo tanto, cualquier solución óptima primero debe reducir esta columna a cero. Por lo tanto, podemos realizar un bombardeo 1-D sobre esta columna, reduciendo cada elemento en ella a cero. Dejamos que las bombas caigan en la segunda columna para que hagan el máximo daño. Creo que hay muchas publicaciones relacionadas con el caso 1D, así que me siento seguro al omitir ese caso. (Si quieres que lo describa, puedo hacerlo). Debido a la propiedad decreciente, las tres columnas más a la izquierda se reducirán a cero. Pero, probablemente utilizaremos un número mínimo de bombas aquí porque la columna izquierda debe ponerse a cero.

Ahora, una vez que la columna izquierda está puesta a cero, simplemente recortamos las tres columnas más a la izquierda que ahora están puestas a cero y repetimos con la matriz ahora reducida. Esto debe darnos una solución óptima ya que en cada etapa usamos un número mínimo comprobable de bombas.

Programación lineal de enteros de Mathematica usando bifurcación

Como ya se ha mencionado, este problema se puede resolver utilizando programación lineal entera (que es NP-Hard ). Mathematica ya tiene ILP incorporado. "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."[Vea Tutorial de optimización restringida en Mathematica ..]

Escribí el siguiente código que utiliza las bibliotecas ILP de Mathematica. Es sorprendentemente 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 el ejemplo proporcionado en el 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]

Salidas

Para cualquiera que lea esto con un algoritmo codicioso

Pruebe su código en el siguiente problema de 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

Aquí está separado por comas:

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, mi solución contiene 208 bombas. Aquí hay una posible solución (pude resolver esto en unos 12 segundos).

Como una forma de probar los resultados que Mathematica está produciendo, vea si su codicioso algoritmo puede mejorar.

No hay necesidad de transformar el problema en subproblemas lineales.

En su lugar, use una heurística codiciosa simple, que es bombardear las esquinas , comenzando por la más grande.

En el ejemplo dado hay cuatro esquinas, {2, 1, 6, 4}. Para cada esquina no hay mejor movimiento que bombardear la diagonal de la celda hacia la esquina, por lo que sabemos con certeza que nuestros primeros 2 + 1 + 6 + 4 = 13 bombardeos deben estar en estas celdas diagonales. Después de hacer el bombardeo, nos queda una nueva 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 

Después de los primeros 13 bombardeos, usamos la heurística para eliminar 3 0 2 a través de tres bombardeos. Ahora, tenemos 2 nuevas esquinas, {2, 1} en la cuarta fila. Bombardeamos esos, otros 3 bombardeos. Hemos reducido la matriz a 4 x 4 ahora. Hay una esquina, la esquina superior izquierda. Bombardeamos eso. Ahora nos quedan 2 esquinas, {5, 3}. Dado que 5 es la esquina más grande, primero bombardeamos, 5 bombardeos, y finalmente bombardean los 3 en la otra esquina. El total es 13 + 3 + 3 + 1 + 5 + 3 = 28.

Esto hace una búsqueda amplia del camino más corto (una serie de bombardeos) a través de este "laberinto" de posiciones. No, no puedo demostrar que no haya un algoritmo más rápido, lo siento.

#!/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))

Parece que un enfoque de programación lineal puede ser muy útil aquí.

Sea P _{m xn} la matriz con los valores de las posiciones:

Ahora definamos una matriz de bomba B (x, y) _mxn , con 1 ≤ x ≤ m , 1 ≤ y ≤ n como se muestra a continuación

de una manera que

Por ejemplo:

Entonces, estamos buscando una matriz B _{m xn} = [ b _ij ] que

1. Se puede definir como una suma de matrices de bombas:

   

   ( q _ij sería entonces la cantidad de bombas que dejaríamos caer en la posición p _ij )

2. p _ij - b _ij ≤ 0 (para ser más sucinto, digamos que P - B ≤ 0 )

Además, B debería minimizar la suma .

También podemos escribir B como la matriz fea más adelante:

y dado que P - B ≤ 0 (lo que significa P ≤ B ) tenemos el siguiente sistema de desigualdad bastante lineal a continuación:

Siendo q _{mn x 1} definido como

p _{mn x 1} definido como

Podemos decir que tenemos un sistema. El siguiente sistema se representa como producto de matrices http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D siendo S _{mn x En} la matriz a invertir para resolver el sistema. No lo expandí yo mismo, pero creo que debería ser fácil hacerlo en código.

Ahora, tenemos un problema mínimo que se puede expresar como

Creo que es algo fácil, casi trivial de resolver con algo como el algoritmo simplex (hay un documento bastante bueno al respecto ). Sin embargo, no conozco casi ninguna programación lineal (tomaré un curso al respecto en Coursera pero es solo en el futuro ...), tuve algunos dolores de cabeza tratando de entenderlo y tengo un gran trabajo independiente para terminar, así que solo ríndete aquí. Puede ser que hice algo mal en algún momento, o que no puede ir más lejos, pero creo que este camino puede conducir a la solución. De todos modos, estoy ansioso por sus comentarios.

(Un agradecimiento especial por este increíble sitio para crear imágenes de expresiones LaTeX )

Esta codiciosa solución parece ser correcta :

Como se señaló en los comentarios, fallará en 2D. Pero tal vez puedas mejorarlo.

Para 1D:
si hay al menos 2 números, no es necesario que dispare al extremo izquierdo porque disparar al segundo no es peor . Así que dispara a la segunda, mientras que la primera no es 0, porque tienes que hacerlo. Moverse a la siguiente celda. No te olvides de la última celda.

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])
    }
}

Entonces, para 2D: de
nuevo: no necesita disparar en la primera fila (si hay la segunda). Entonces dispara a la segunda. Resuelva la tarea 1D para la primera fila. (porque necesitas que sea nulo). Bajar. No olvides la última fila.

Para minimizar el número de bombas, tenemos que maximizar el efecto de cada bomba. Para lograr esto, en cada paso tenemos que seleccionar el mejor objetivo. Para cada punto que lo suma y son ocho vecinos, podría usarse como una cantidad eficiente de bombardeo en este punto. Esto proporcionará una secuencia de bombas cercana a la óptima.

UPD : También deberíamos tener en cuenta varios ceros, porque bombardearlos es ineficiente. De hecho, el problema es minimizar el número de ceros afectados. Pero no podemos saber cómo algún paso nos acerca a este objetivo. Estoy de acuerdo con la idea de que el problema es NP-completo. Sugiero un enfoque codicioso, que dará una respuesta casi real.

Creo que para minimizar la cantidad de bombas simplemente necesitas maximizar la cantidad de daño ... para que eso suceda, debes verificar el área que tiene la fuerza más fuerte ... así que primero analizas el campo con un núcleo de 3x3 y compruebas dónde está la suma es más fuerte ... y bombardea allí ... y lo hace hasta que el campo esté plano ... para esto archivado la respuesta es 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');

Aquí hay una solución que generaliza las buenas propiedades de las esquinas.

Supongamos que podemos encontrar un punto de caída perfecto para un campo determinado, es decir, la mejor manera de disminuir el valor en él. Luego, para encontrar el número mínimo de bombas que se lanzarán, podría ser un primer borrador de un algoritmo (el código se copia de una implementación de 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

El reto es choose_a_perfect_drop_point. Primero, definamos qué es un punto de caída perfecto.

• Un punto de caída para (x, y)disminuye el valor en (x, y). También puede disminuir los valores en otras celdas.
• Un punto de caída de una de (x, y)es mejor que un punto de goteo b para (x, y)si disminuye los valores de un superconjunto adecuada de las células que b disminuye.
• Un punto de caída es máximo si no hay otro mejor punto de caída.
• Dos puntos de caída (x, y)son equivalentes si disminuyen el mismo conjunto de celdas.
• Un punto de caída para (x, y)es perfecto si es equivalente a todos los puntos de caída máximos para (x, y).

Si hay un punto de caída perfecto para (x, y), no puede disminuir el valor de manera (x, y)más efectiva que lanzar una bomba en uno de los puntos de caída perfectos (x, y).

Un punto de caída perfecto para un campo dado es un punto de caída perfecto para cualquiera de sus celdas.

Aquí hay algunos ejemplos:

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

El punto de caída perfecto para la celda (0, 0)(índice basado en cero) es (1, 1). Todos los demás puntos de caída para (1, 1), es decir (0, 0), (0, 1), y (1, 0), disminuyen 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

Un punto de caída perfecto para la célula (2, 2)(índice basado en cero) es (2, 2), y también todas las células circundantes (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2), y (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

Un punto de caída perfecto para la celda (2, 2)es (3, 1): Disminuye el valor (2, 2)y el valor en (4, 0). Todos los demás puntos de caída (2, 2)no son máximos, ya que disminuyen una celda menos. El punto de caída perfecto (2, 2)también es el punto de caída perfecto (4, 0), y es el único punto de caída perfecto para el campo. Conduce a la solución perfecta para este campo (una 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

No hay un punto de caída perfecto para (2, 2): Ambos (1, 1)y (1, 3)disminución (2, 2)y otra celda (son puntos de caída máximos para (2, 2)), pero no son equivalentes. Sin embargo, (1, 1)es un punto de caída perfecto para (0, 0), y (1, 3)es un punto de caída perfecto para (0, 4).

Con esa definición de puntos de caída perfectos y un cierto orden de comprobaciones, obtengo el siguiente resultado para el ejemplo en la pregunta:

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

Sin embargo, el algoritmo solo funciona si hay al menos un punto de caída perfecto después de cada paso. Es posible construir ejemplos donde no hay puntos de caída perfectos:

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

Para estos casos, podemos modificar el algoritmo para que, en lugar de un punto de caída perfecto, escojamos una coordenada con una elección mínima de puntos de caída máximos y luego calculemos el mínimo para cada opción. En el caso anterior, todas las celdas con valores tienen dos puntos de caída máximos. Por ejemplo, (0, 1)tiene los puntos de caída máximos (1, 1)y (1, 2). Elegir cualquiera de los dos y luego calcular el mínimo conduce a este resultado:

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

Aquí hay otra idea:

Comencemos asignando un peso a cada espacio en el tablero para cuántos números se reducirían arrojando una bomba allí. Entonces, si el espacio tiene un número distinto de cero, obtiene un punto, y si cualquier espacio adyacente tiene un número distinto de cero, obtiene un punto adicional. Entonces, si hay una cuadrícula de 1000 por 1000, tenemos un peso asignado a cada uno de los 1 millón de espacios.

Luego ordena la lista de espacios por peso y bombardea el que tenga el mayor peso. Esto se está aprovechando al máximo por nuestro dinero, por así decirlo.

Después de eso, actualice el peso de cada espacio cuyo peso se vea afectado por la bomba. Este será el espacio que bombardeaste, y cualquier espacio inmediatamente adyacente a él, y cualquier espacio inmediatamente adyacente a esos. En otras palabras, cualquier espacio que podría tener su valor reducido a cero por el bombardeo, o el valor de un espacio vecino reducido a cero.

Luego, vuelva a ordenar los espacios de la lista por peso. Dado que solo un pequeño subconjunto de espacios cambió su peso por el bombardeo, no necesitará recurrir a la lista completa, solo mueva esos en la lista.

Bombardee el nuevo espacio de mayor peso y repita el procedimiento.

Esto garantiza que cada bombardeo reduce la mayor cantidad de espacios posible (básicamente, golpea la menor cantidad de espacios que ya son cero como sea posible), por lo que sería óptimo, excepto que pueden ser lazos en pesos. Por lo tanto, es posible que deba realizar un seguimiento posterior cuando haya un empate para el peso máximo. Sin embargo, solo importa un empate para el peso máximo, no otros empates, así que espero que no sea demasiado retroceso.

Editar: el contraejemplo de Mysticial a continuación demuestra que, de hecho, no se garantiza que sea óptimo, independientemente de los lazos en los pesos. En algunos casos, reducir el peso tanto como sea posible en un paso dado en realidad deja las bombas restantes demasiado extendidas para lograr una reducción acumulativa tan alta después del segundo paso como podría tener con una elección un poco menos codiciosa en el primer paso. Me engañó un poco la idea de que los resultados son insensibles al orden de los bombardeos. Ellos soninsensible al orden en que podría tomar cualquier serie de bombardeos y reproducirlos desde el principio en un orden diferente y terminar con el mismo tablero resultante. Pero no se deduce de eso que pueda considerar cada bombardeo de forma independiente. O, al menos, cada bombardeo debe considerarse de una manera que tenga en cuenta qué tan bien configura el tablero para los bombardeos posteriores.

Bueno, supongamos que numeramos las posiciones del tablero 1, 2, ..., nx m. Cualquier secuencia de lanzamientos de bombas puede representarse mediante una secuencia de números en este conjunto, donde los números pueden repetirse. Sin embargo, el efecto en el tablero es el mismo independientemente del orden en el que coloque las bombas, por lo que cualquier elección de bombas puede representarse como una lista de números nxm, donde el primer número representa el número de bombas lanzadas en la posición 1 , el segundo número representa el número de bombas lanzadas en la posición 2, etc. Llamemos a esta lista de números nxm la "clave".

Primero puede intentar calcular todos los estados de la placa que resultan de una caída de 1 bomba, luego usarlos para calcular todos los estados de la tabla que resultan de 2 gotas de bomba, etc., hasta obtener todos los ceros. Pero en cada paso, almacenaría en caché los estados usando la clave que definí anteriormente, para que pueda usar estos resultados al calcular el siguiente paso (un enfoque de "programación dinámica").

Pero dependiendo del tamaño de n, my los números en la cuadrícula, los requisitos de memoria de este enfoque pueden ser excesivos. Puede tirar todos los resultados de las gotas de bomba N una vez que haya calculado todos los resultados para N + 1, por lo que hay algunos ahorros allí. Y, por supuesto, no puede almacenar en caché nada a costa de que demore mucho más: el enfoque de programación dinámica cambia la memoria por velocidad.

Si desea la solución óptima absoluta para limpiar el tablero, tendrá que usar el retroceso clásico, pero si la matriz es muy grande, llevará mucho tiempo encontrar la mejor solución, si desea una solución óptima "posible" puede usar un algoritmo codicioso , si necesita ayuda para escribir el algoritmo, puedo ayudarlo

Ahora que lo pienso es la mejor manera. Haga otra matriz allí donde almacene los puntos que elimine soltando una bomba allí, luego elija la celda con puntos máximos y suelte la bomba allí, actualice la matriz de puntos y continúe. Ejemplo:

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 de celda +1 para cada celda adyacente con un valor superior a 0

Fuerza bruta !

Sé que no es eficiente, pero incluso si encuentra un algoritmo más rápido, siempre puede probar este resultado para saber qué tan preciso es.

Use algo de recursión, así:

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);

}

Puede hacer esto más eficiente mediante el almacenamiento en caché, si una forma diferente conduce al mismo resultado, no debe repetir los mismos pasos.

Elaborar:

si bombardear la celda 1,3,5 conduce al mismo resultado que bombardear la celda 5,3,1, entonces, no debe volver a hacer todos los pasos siguientes nuevamente para ambos casos, solo 1 es suficiente, debe almacenar en algún lugar todo tabla de estados y utiliza sus resultados.

Se puede usar un hash de estadísticas de la tabla para hacer una comparación rápida.

1. Nunca bombardee el borde (a menos que el cuadrado no tenga un vecino no fronterizo)
2. Esquina cero.
3. Para poner a cero la esquina, deje caer el valor de la esquina a un cuadrado de distancia en diagonal (el único vecino no fronterizo)
4. Esto creará nuevas esquinas. Ir a 2

Editar: no noté que Kostek sugirió casi el mismo enfoque, por lo que ahora hago una afirmación más fuerte: si las esquinas para despejar se eligen para estar siempre en la capa más externa, entonces es óptimo.

En el ejemplo de OP: dejar caer 2 (como 1 + 1 o 2) en cualquier otra cosa que no sea en 5 no lleva a golpear ningún cuadrado que golpearía en 5. Entonces, simplemente debemos dejar 2 en 5 (y 6 en la parte inferior izquierda 1 ...)

Después de esto, solo hay una forma de borrar (en la esquina superior izquierda) lo que originalmente era 1 (ahora 0), y eso es soltando 0 en B3 (sobresalir como notación). Y así.

Solo después de borrar columnas enteras A y E y 1 y 7 filas, comience a borrar una capa más profunda.

Considere borrar solo aquellos borrados intencionalmente, borrar las esquinas de valor 0 no cuesta nada y simplifica pensar en ello.

Debido a que todas las bombas lanzadas de esta manera deben arrojarse y esto conduce a campos despejados, es la solución óptima.

Después de dormir bien, me di cuenta de que esto no es cierto. Considerar

  ABCDE    
1 01000
2 10000
3 00000
4 00000

Mi enfoque arrojaría bombas sobre B3 y C2, cuando arrojar sobre B2 sería suficiente

Esta es mi solución. Todavía no la escribiré en el código, ya que no tengo tiempo, pero creo que esto debería producir un número óptimo de movimientos cada vez, aunque no estoy seguro de cuán eficiente sería encontrar Los puntos para bombardear.

En primer lugar, como dijo @Luka Rahne en uno de los comentarios, el orden en que bombardeos no es importante, solo la combinación.

En segundo lugar, como muchos otros han dicho, bombardear 1-la diagonal desde las esquinas es óptimo porque toca más puntos que las esquinas.

Esto genera la base para mi versión del algoritmo: podemos bombardear el '1-off desde las esquinas' primero o último, no importa (en teoría) Bombardeamos esos primero porque hace que las decisiones posteriores sean más fáciles (en la práctica) Bombardeamos el punto que afecta la mayoría de los puntos, mientras que simultáneamente bombardeamos esas esquinas.

Definamos los Puntos de resistencia como los puntos en el tablero con la mayor cantidad de puntos no bombardeables y el mayor número de 0 a su alrededor.

Los puntos que no se pueden bombardear se pueden definir como puntos que no existen en nuestro alcance actual del tablero que estamos viendo.

También definiré 4 límites que manejarán nuestro alcance: Superior = 0, Izquierda = 0, Inferior = k, derecha = j. (valores para comenzar)

Finalmente, definiré las bombas óptimas como bombas que se lanzan sobre puntos adyacentes a puntos de resistencia y están tocando (1) el punto de resistencia de mayor valor y (2) la mayor cantidad de puntos posible.

En cuanto al enfoque, es obvio que estamos trabajando desde afuera hacia adentro. Podremos trabajar con 4 'bombarderos' al mismo tiempo.

Los primeros puntos de resistencia son obviamente nuestros rincones. Los puntos 'fuera de límite' no son bombeables (hay 5 puntos fuera del alcance de cada esquina). Así que primero bombardeamos los puntos en diagonal, uno fuera de las esquinas.

Algoritmo:

1. Encuentra los 4 puntos de bomba óptimos.
2. Si un punto de bomba está bombardeando un punto de resistencia que está tocando 2 límites (es decir, una esquina), bombardea hasta ese punto es 0. De lo contrario, bombardea cada uno hasta que uno de los puntos de resistencia que toque el punto de bomba óptimo sea 0.
3. para cada límite: si (suma (límite) == 0) límite adelantado

repita hasta ARRIBA = ABAJO e IZQUIERDA = DERECHA

Intentaré escribir el código real más tarde

Podrías usar la planificación del espacio estatal. Por ejemplo, usando A * (o una de sus variantes) junto con una heurística f = g + hcomo esta:

• g: número de bombas lanzadas hasta ahora
• h: suma sobre todos los valores de la cuadrícula divididos por 9 (que es el mejor resultado, lo que significa que tenemos una heurística admisible)

Tengo 28 movimientos también. Utilicé dos pruebas para el mejor próximo movimiento: primero el movimiento que produce la suma mínima para el tablero. Segundo, para sumas iguales, el movimiento produce la densidad máxima, definida como:

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

Este es Haskell. "resolver tablero" muestra la solución del motor. Puede jugar el juego escribiendo "principal", luego ingrese un punto objetivo, "mejor" para una recomendación, o "salir" para salir.

SALIDA:
* Principal> resolver tablero
[(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)

Parece que hay una subestructura de coincidencia no bipartita aquí. Considere la siguiente instancia:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

La solución óptima para este caso tiene el tamaño 5, ya que es el tamaño de una cubierta mínima de los vértices de un ciclo de 9 por sus bordes.

Este caso, en particular, muestra que la relajación de programación lineal que algunas personas han publicado no es exacta, no funciona y todas esas otras cosas malas. Estoy bastante seguro de que puedo reducir "cubrir los vértices de mi gráfico cúbico plano con la menor cantidad de bordes posible" a su problema, lo que me hace dudar si alguna de las soluciones codiciosas / de escalada va a funcionar.

No veo una manera de resolver esto en tiempo polinómico en el peor de los casos. Puede haber una solución muy inteligente de búsqueda binaria y DP que no estoy viendo.

EDITAR : veo que el concurso ( http://deadline24.pl ) es independiente del lenguaje; te envían un montón de archivos de entrada y tú les envías salidas. Por lo tanto, no necesita algo que se ejecute en el peor de los casos de polinomios. En particular, ¡puedes mirar la entrada !

Hay un montón de casos pequeños en la entrada. Luego hay una caja de 10x1000, una caja de 100x100 y una caja de 1000x1000. Los tres casos grandes se comportan muy bien. Las entradas adyacentes horizontalmente suelen tener el mismo valor. En una máquina relativamente robusta, puedo resolver todos los casos mediante el uso de fuerza bruta utilizando CPLEX en solo un par de minutos. Tuve suerte en el 1000x1000; La relajación LP pasa a tener una solución óptima integral. Mis soluciones están de acuerdo con los .ansarchivos provistos en el paquete de datos de prueba.

Apuesto a que puedes usar la estructura de la entrada de una manera mucho más directa que yo si la miras; parece que puedes cortar la primera fila, o dos, o tres repetidamente hasta que no te quede nada. (Parece que, en 1000x1000, ¿todas las filas no aumentan? ¿Supongo que de ahí proviene su "parte B"?)

No se me ocurre una manera de calcular el número real sin simplemente calcular la campaña de bombardeo utilizando mi mejor heurística y espero obtener un resultado razonable.

Entonces, mi método es calcular una métrica de eficiencia de bombardeo para cada celda, bombardear la celda con el valor más alto, ... repetir el proceso hasta que haya aplanado todo. Algunos han abogado por el uso de daños potenciales simples (es decir, puntaje de 0 a 9) como una métrica, pero eso se queda corto golpeando celdas de alto valor y no haciendo uso de la superposición de daños. Calcularía cell value - sum of all neighbouring cells, restablecería cualquier positivo a 0 y usaría el valor absoluto de cualquier cosa negativa. Intuitivamente, esta métrica debe hacer una selección que ayude a maximizar la superposición de daños en las células con recuentos altos en lugar de golpearlas directamente.

El siguiente código alcanza la destrucción total del campo de prueba en 28 bombas (tenga en cuenta que usar el daño potencial como métrica produce 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();
    }           
  }
}

El patrón de bombardeo resultante se emite de la siguiente manera (valores de campo a la izquierda, métrica a la derecha)

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

Esto se puede resolver utilizando un árbol de profundidad O (3 ^ (n)). Donde n es la suma de todos los cuadrados.

Primero considere que es trivial resolver el problema con un árbol de O (9 ^ n), simplemente considere todos los posibles lugares de bombardeo. Para ver un ejemplo, vea la implementación de Alfe .

Luego, tenga en cuenta que podemos trabajar para bombardear de abajo hacia arriba y aún así obtener un patrón de bombardeo mínimo.

1. Comience desde la esquina inferior izquierda.
2. Bombardea hasta el olvido con las únicas jugadas que tienen sentido (arriba y a la derecha).
3. Mueve un cuadrado a la derecha.
4. Si bien el objetivo tiene un valor mayor que cero, considere cada una de las 2 jugadas que tengan sentido (hacia arriba o hacia arriba y hacia la derecha), reduzca el valor del objetivo en uno y cree una nueva rama para cada posibilidad.
5. Mueve otro a la derecha.
6. Si bien el objetivo tiene un valor mayor que cero, considere cada una de las 3 jugadas que tengan sentido (arriba a la izquierda, arriba y arriba a la derecha), reduzca el valor del objetivo en uno y cree una nueva rama para cada posibilidad.
7. Repita los pasos 5 y 6 hasta que se elimine la fila.
8. Mueva una fila hacia arriba y repita los pasos del 1 al 7 hasta que se resuelva el rompecabezas.

Este algoritmo es correcto porque

1. Es necesario completar cada fila en algún momento.
2. Completar una fila siempre requiere una jugada ya sea una arriba, una abajo o dentro de esa fila.
3. Siempre es tan bueno o mejor elegir una jugada por encima de la fila sin borrar más baja que una jugada en la fila o debajo de la fila.

En la práctica, este algoritmo funcionará regularmente mejor que su máximo teórico porque bombardeará regularmente a los vecinos y reducirá el tamaño de la búsqueda. Si suponemos que cada bombardeo disminuye el valor de 4 objetivos adicionales, entonces nuestro algoritmo se ejecutará en O (3 ^ (n / 4)) o aproximadamente O (1.3 ^ n).

Como este algoritmo sigue siendo exponencial, sería aconsejable limitar la profundidad de la búsqueda. Podríamos limitar el número de ramas permitidas a algún número, X, y una vez que estemos tan profundos, forzamos al algoritmo a elegir el mejor camino que ha identificado hasta ahora (el que tiene la suma mínima total de la placa en una de sus hojas terminales ) Entonces nuestro algoritmo está garantizado para ejecutarse en tiempo O (3 ^ X), pero no se garantiza que obtenga la respuesta correcta. Sin embargo, siempre podemos aumentar X y probar empíricamente si la compensación entre un mayor cómputo y mejores respuestas vale la pena.

función de evaluación, suma 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];
}

función 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;
}

función de destrucción:

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]--;
    }
}

función 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;
}

función de maximización lineal:

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

Esto no es óptimo, pero se puede optimizar mediante la búsqueda de una mejor función de evaluación.

... pero pensando en este problema, estaba pensando que uno de los principales problemas es obtener cifras abandonadas en medio de ceros en algún momento, por lo que tomaría otro enfoque ... que es dominar los valores mínimos en cero, luego tratar de escapar de los ceros como sea posible, lo que lleva a una minimización general de los valores mínimos existentes más o menos

Todo este problema se reduce a calcular una distancia de edición. Simplemente calcule una variante de la distancia de Levenshtein entre la matriz dada y la matriz cero, donde las ediciones se reemplazan con bombardeos, utilizando la programación dinámica para almacenar las distancias entre las matrices intermedias. Sugiero usar un hash de las matrices como clave. En 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

Esta fue una respuesta a la primera pregunta. No me había dado cuenta de que él había cambiado los parámetros.

Crea una lista de todos los objetivos. Asigne un valor al objetivo en función del número de valores positivos afectados por una caída (en sí mismo y en todos los vecinos). El valor más alto sería un nueve.

Ordene los objetivos por el número de objetivos afectados (Descendente), con un orden descendente secundario en la suma de cada objetivo afectado.

Arroja una bomba sobre el objetivo de mayor rango, luego vuelve a calcular los objetivos y repite hasta que todos los valores de los objetivos sean cero.

De acuerdo, esto no siempre es lo más óptimo. Por ejemplo,

100011
011100
011100
011100
000000
100011

Este enfoque tomaría 5 bombas para despejar. Sin embargo, de manera óptima, podría hacerlo en 4. Aún así, muy cerca y no hay retroceso. Para la mayoría de las situaciones será óptimo, o muy cercano.

Usando los números de problema originales, este enfoque se resuelve en 28 bombas.

Agregar código para demostrar este enfoque (usando un formulario con un botón):

         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];
                        }

                    }
                }
            }
        }

    }

Una clase que necesitarás:

        class Target
    {
        public int value;
        public int sum;
        public int x;
        public int y;
    }