algorithm - Algoritmo de caída de bombas
language-agnostic matrix (30)
Programación lineal de enteros de Mathematica usando derivación y enlace
Como ya se ha mencionado, este problema se puede resolver utilizando la 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."[Ver Tutorial de optimización restringida en Mathematica ..]
He escrito 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 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 solución posible (pude resolver esto en unos 12 segundos).
Como una forma de probar los resultados que produce Mathematica, vea si su algoritmo codicioso puede mejorar.
Tengo una matriz nxm 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
El "lanzamiento de una bomba" disminuye en uno el número de la celda objetivo y sus ocho vecinos, hasta un mínimo de cero.
x x x
x X x
x x x
¿Qué es un algoritmo que determinaría el número mínimo 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 responder. 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 un caso "más fácil" ayudaría a encontrar una solución para uno más difícil.
PD: Creo que cuando tenemos varias situaciones iguales, se 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 de que podría ser correcto?
- Nunca bombardee la frontera (a menos que el cuadrado no tenga vecino no fronterizo)
- Esquina cero
- A la esquina cero, suelte el valor de la esquina a una casilla de distancia en diagonal (el único vecino no fronterizo)
- Esto creará nuevas esquinas. Ir a 2
Edición: no noté que Kostek sugirió casi el mismo enfoque, así que ahora hago una afirmación más fuerte: si se eligen esquinas para despejar 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 en 5 no lleva a ningún cuadrado que golpee con 5. Así que simplemente debemos dejar caer 2 sobre 5 (y 6 en la parte inferior izquierda 1 ...)
Después de esto, solo hay una forma de despejar (en la esquina superior izquierda) lo que originalmente era 1 (ahora 0), y eso es soltar 0 en B3 (sobresalir como notación). Y así.
Solo después de borrar las columnas A y E completas y las filas 1 y 7, comience a limpiar una capa más profundamente.
Considere borrado solo aquellos que hayan sido limpiados intencionalmente, borrar 0 esquinas de valor no cuesta nada y simplifica pensar en ello.
Debido a que todas las bombas lanzadas de esta manera deben ser lanzadas y esto conduce a campos despejados, es una 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 dejaría caer bombas sobre B3 y C2, cuando caer sobre B2 sería suficiente
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 tablas de 3x3 y más pequeñas, la solución es trivialmente la celda numerada más grande.
En tablas mayores 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*
Sin embargo, si arregla la bomba, es imposible limpiar esta tabla 4x4 con menos de 2 + 1 + 6 + 4 = 13 bombas.
Se ha mencionado en otras respuestas que colocar la bomba en la segunda a la esquina para eliminar la esquina nunca es peor que colocar la bomba en la misma esquina, por lo 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 a la 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 ahora tan bueno. Necesitamos 13 bombas para despejar las esquinas.
Ahora observe el número 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 usando una sola bomba, por lo que la bomba mínima ha aumentado en 6 + 4 + 3 + 2, por lo que, sumando la cantidad de bombas que usamos para despejar las esquinas, obtenemos esa cantidad mínima. El número de bombas requeridas 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 utilizar 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. Ya que hemos demostrado anteriormente que ninguna solución óptima puede tener menos de 28 bombas, por lo tanto, 28 bombas es realmente una solución óptima.
Sin embargo, cuando la codicia y el método para encontrar el límite mínimo que he mencionado anteriormente no convergen, creo que hay que volver a verificar todas las combinaciones.
El algoritmo para encontrar el límite inferior es el siguiente:
- Elija un elemento con el número más alto, llámelo P.
- Marque todas las celdas a dos pasos de P y P como no elegibles.
- Agregue P a la lista de
minimums. - Repita el paso 1 hasta que todas las celdas no sean elegibles.
- Suma la lista de
minimumspara obtener el límite inferior.
Este sería un enfoque codicioso:
Calcule una matriz de "puntaje" de orden n X m, donde 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)
Moviendo la fila sabiamente, encuentre y elija la primera posición con la puntuación más alta (por ejemplo, (i, j)).
Bomba (i, j). Incrementa el conteo de bombas.
Si todos los elementos de la matriz original no son cero, entonces goto 1.
Sin embargo, tengo mis dudas de que esta es la solución óptima.
Editar:
El enfoque codicioso que publiqué anteriormente, mientras funciona, lo más probable es que no nos dé 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 el objetivo. A partir de este supuesto, aquí está el nuevo enfoque:
NumOfBombs (M): (devuelve el número mínimo de bombardeos requeridos)
Dada una Matriz M de orden n X m. Si todos los elementos de M son cero, entonces devuelva 0.
Calcular 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.
retorno (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 nuke además de esto, tendríamos que hacer un seguimiento de los resultados de "min".
Esto hace una amplia búsqueda del camino más corto (una serie de bombardeos) a través de este "laberinto" de posiciones. No, no puedo probar 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))
Hay una manera de reducir esto a un subproblema simple.
Hay dos partes en la explicación, el algoritmo y la razón por la que el algoritmo proporciona una solución óptima. El primero no tendrá sentido sin el segundo, así que empezaré por el por qué.
Si piensa en bombardear el rectángulo (suponga que es un rectángulo grande - no hay casos de borde todavía) puede ver que la única forma de reducir el rectángulo hueco de los 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é la capa perimetral 1, y el rectángulo dentro de ella capa 2.
Una idea importante es que no hay un punto de bombardeo de la capa 1, porque el "radio de explosión" que se obtiene al hacerlo siempre está contenido dentro del radio de explosión de otro cuadrado de la capa 2. Debería poder convencerlo fácilmente de esto.
Entonces, podemos reducir el problema para encontrar una manera óptima de bombardear el perímetro, y luego podemos repetirlo 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 bombas X. Entonces, si llamamos a la capa permitida uno, si colocamos X bombas 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 para reducir el perímetro exterior.
Pero, sí sabemos que podemos ser codiciosos. Debido a que ninguna bomba en la capa 2 puede ser más eficiente en 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 una bomba colocada en la capa 2 puede. Por lo tanto, nunca puede hacernos 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 hacemos daño bombardeando 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 pueden ser alcanzados por 2 cuadrados desde la capa interna:
0 A B
C X Y
D Z
En este punto, el perímetro es efectivamente un bucle tridimensional cerrado, 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, excepto por las esquinas extrañas, e incluso allí el radio de explosión no es un subconjunto de otro. Tenga en cuenta que si se tratara de una línea (como lo 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 hace daño 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 de 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 brinda 2 opciones) de modo que el valor más alto dentro de los 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 (todavía?) tiene una prueba.
No hay necesidad de transformar el problema en subproblemas lineales.
En su lugar, utilice una heurística codiciosa simple, que consiste en 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 celda diagonal a la esquina, por lo que sabemos a ciencia cierta que nuestros primeros 2 + 1 + 6 + 4 = 13 bombardeos deben realizarse 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 atentados utilizamos la heurística para eliminar 3 0 2 mediante tres atentados. Ahora, tenemos 2 esquinas nuevas, {2, 1} en la cuarta fila. Bombardeamos esos, otros 3 bombardeos. Hemos reducido la matriz a 4 x 4 ahora. Hay una esquina, la parte superior izquierda. Bombardeamos eso. Ahora nos quedan 2 esquinas, {5, 3}. Ya que 5 es el rincón más grande, bombardeamos ese primero, 5 bombardeos, luego finalmente bombardeamos los 3 en el otro rincón. El total es 13 + 3 + 3 + 1 + 5 + 3 = 28.
Pólya dice: "Si no puedes resolver un problema, hay un problema más fácil que puedes resolver: encontrarlo".
El problema obvio más simple es el problema de una dimensión (cuando la cuadrícula es una sola fila). Comencemos con el algoritmo más simple: bombardear con avidez el objetivo más grande. ¿Cuándo sale mal?
Dado 1 1 1 , el algoritmo codicioso 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 2, 3 o 4. Pero bombardear la segunda celda para dejar 0 0 1 1 1 es mejor que bombardear la tercera celda para dejar 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 trabajar 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?
Edit: 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 cualquier progreso en eso.
Para preguntas actualizadas, un algoritmo codicioso simple da un resultado óptimo.
Suelta las bombas A [0,0] a la celda A [1,1], luego suelta las bombas A [1,0] a 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]) a la celda A [N-2,1]. Esto limpiará completamente las 3 primeras columnas.
Con el mismo enfoque limpie las columnas 3,4,5, luego las columnas 6,7,8, etc.
Desafortunadamente, esto no ayuda a encontrar una solución para el problema original.
El problema "más grande" (sin restricción "no creciente") puede ser probado como NP-duro. Aquí está el boceto de una prueba.
Supongamos que tenemos un gráfico planar de grado hasta 3. Vamos a encontrar la cobertura mínima de vértices para este gráfico. De acuerdo con el artículo de Wikipedia, este problema es NP-duro para los gráficos planares de grado 3. Esto podría comprobarse 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 "Límites inferiores algorítmicos" por el prof. Erik Demaine (conferencias 7 y 9).
Si dividimos algunos bordes del gráfico original (gráfico de la izquierda en el diagrama), cada uno con un número par de nodos adicionales, el gráfico resultante (gráfico de la derecha en el diagrama) debe tener exactamente la misma cobertura de vértice mínimo para los vértices originales. Dicha transformación permite alinear los vértices del gráfico con posiciones arbitrarias en la cuadrícula.
Si colocamos los vértices del gráfico solo en filas y columnas uniformes (de tal manera que no haya dos bordes que inciden en un vértice formando 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 una cobertura mínima de vértices.
Parece que un enfoque de programación lineal puede ser muy útil aquí.
Sea P mxn la matriz con los valores de las posiciones:
Ahora vamos a definir una matriz de bomba B (x, y) mxn , con 1 ≤ x ≤ m , 1 ≤ y ≤ n como abajo
de una manera que
Por ejemplo:
Así que estamos buscando una matriz B mxn = [ b ij ] que
Se puede definir como una suma de matrices de bombas:
( q ij sería entonces la cantidad de bombas que colocaríamos en la posición p ij )
p ij - b ij ≤ 0 (para ser más sucinto, digámoslo como P - B ≤ 0 )
Además, B debería minimizar la suma. .
También podemos escribir B como la matriz fea por delante:
y como 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 representado como producto de matrices http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D siendo S mn x mn la matriz que se invierte para resolver el sistema. Yo no lo amplié, pero creo que debería ser fácil hacerlo en código.
Ahora, tenemos un problema mínimo que puede ser declarado como
Creo que es algo fácil, casi trivial 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 al tratar de entenderlo y tengo un gran trabajo independiente que terminar, así que sólo renunciar aquí. Puede ser que haya hecho algo mal en algún momento, o que no pueda ir más allá, pero creo que este camino puede llevar a la solución. De todos modos, estoy ansioso por sus comentarios.
(Gracias especiales por este sitio increíble para crear imágenes a partir de expresiones LaTeX )
Puede representar este problema como un problema de programación de enteros . (Esta es solo una de las posibles soluciones para abordar este problema)
Teniendo puntos:
a b c d
e f g h
i j k l
m n o p
uno puede escribir 16 ecuaciones donde para el punto f, por ejemplo, se mantiene
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 todo xi en los límites 0, por lo que terminará teniendo la ecuación 4 + 1 en este ejemplo.
El problema es que no existe un algoritmo trivial para resolver tales problemas. No soy experto en esto, pero resolver este problema ya que la programación lineal es NP difícil.
Su nuevo problema, con los valores no decrecientes en las filas, es bastante fácil de resolver.
Observe que la columna de la izquierda contiene los números más altos. Por lo tanto, cualquier solución óptima debe primero reducir esta columna a cero. Por lo tanto, podemos realizar una carrera de bombardeo 1-D sobre esta columna, reduciendo a cero todos los elementos que contiene. Dejamos caer las bombas en la segunda columna para que causen el máximo daño. Creo que hay muchas publicaciones aquí relacionadas con el caso 1D, así que me siento segura al saltarme ese caso. (Si quieres que lo describa, yo puedo). Debido a la disminución de la propiedad, las tres columnas de la izquierda se reducirán a cero. Pero, probablemente usaremos un número mínimo de bombas aquí porque la columna de la izquierda debe estar en cero.
Ahora, una vez que la columna de la izquierda está en cero, simplemente recortamos las tres columnas de la izquierda que ahora están en cero y repetimos con la matriz ahora reducida. Esto debe darnos una solución óptima, ya que en cada etapa utilizamos un número mínimo de bombas, como es de suponer.
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í misma y todos los vecinos). El valor más alto sería un nueve.
Ordene los objetivos por el número de objetivos impactados (Descendente), con una clasificación descendente secundaria en la suma de cada objetivo impactado.
Coloca una bomba en el objetivo clasificado más alto, luego vuelve a calcular los objetivos y repite hasta que todos los valores objetivo 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í, bastante cerca y no hay retroceso. Para la mayoría de las situaciones será óptimo, o muy cercano.
Usando los números de problemas originales, este enfoque se resuelve en 28 bombas.
Agregar código para demostrar este enfoque (mediante 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;
}
Tuve que detenerme solo en una solución parcial ya que estaba fuera de tiempo, pero espero que incluso esta solución parcial proporcione algunas ideas sobre un posible enfoque para resolver este problema.
Cuando me enfrento a un problema difícil, me gusta proponer 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. Considere una línea:
0 4 2 1 3 0 1
De alguna manera u otra, sabes que necesitarás bombardear en o alrededor del punto 4 4 veces para reducirlo a 0. Dado que la izquierda del lugar es un número menor, no hay beneficio de bombardear el 0 o el 4 sobre el bombardeo del 2 . De hecho, creo (pero carece de una prueba rigurosa) que bombardear el 2 hasta que el punto 4 descienda a 0 es al menos tan bueno como cualquier otra estrategia para obtener ese 4 a 0. Uno puede avanzar por la línea de izquierda a derecha En una estrategia como esta:
index = 1
while index < line_length
while number_at_index(index - 1) > 0
bomb(index)
end
index++
end
# take care of the end of the line
while number_at_index(index - 1) > 0
bomb(index - 1)
end
Un par de órdenes de bombardeo de muestra:
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 necesita bajar de una u otra forma es atractiva porque de repente se puede encontrar una solución que, como algunos dicen, sea al menos tan buena como todas las demás soluciones.
El siguiente paso en la complejidad donde esta búsqueda de al menos igual de buena todavía es factible está en el borde del tablero. Para mí está claro que nunca hay un beneficio estricto para bombardear el borde exterior; es mejor bombardear el punto uno y conseguir 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 del borde a 0. Aún más, es trivialmente sencillo descubrir la estrategia óptima (en el sentido de que es a menos tan bueno como cualquier otra estrategia) para obtener números de esquina hasta 0. Ponemos todo esto junto y podemos acercarnos mucho más a una solución en el espacio 2-D.
Dada la observación sobre las piezas de esquina, podemos decir con certeza que conocemos la estrategia óptima para pasar de cualquier tablero de inicio a un tablero con ceros en todas las esquinas. Este es un ejemplo de un tablero de este tipo (tomé prestados los números de los dos tableros lineales de arriba). 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
Uno notará que en la fila superior se parece mucho al ejemplo lineal que vimos anteriormente. Recordando nuestra observación anterior de que la forma óptima de reducir la fila superior a 0 es bombardear la segunda fila (la fila x ). No hay forma de despejar la fila superior bombardeando cualquiera de las filas y y no hay beneficio adicional de bombardear la fila superior sobre el bombardeo del espacio correspondiente en la fila x .
Podríamos aplicar la estrategia lineal desde arriba (bombardeando los espacios correspondientes en la fila x ), concerniéndonos solo con la fila superior y nada más. Iría algo como esto:
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 últimos bombardeos. Está claro, dado que los únicos sitios de bombas que reducen la cifra de 4 en la primera columna en la segunda fila son la primera x y la y . Los dos últimos bombardeos son claramente inferiores a solo bombardear el primer x , que habría hecho exactamente lo mismo (con respecto al primer punto en la fila superior, que no tenemos otra forma de despejar). Como hemos demostrado que nuestra estrategia actual es subóptima, es evidente que se necesita una modificación en la estrategia.
En este punto, puedo dar un paso atrás en la complejidad y concentrarme solo en una esquina. Consideremos este:
0 4 2 1
4 x y a
2 z . .
1 b . .
Está claro que la única forma de obtener los espacios de 4 a cero es bombardear alguna combinación de x , y y z . Con algunas acrobacias en mi mente, estoy bastante seguro de que la solución óptima es bombardear x tres veces y luego a b . Ahora es cuestión de descubrir cómo llegué a esa solución y si revela alguna intuición que podamos usar para resolver este problema local. Me doy cuenta de que no hay bombardeos de los espacios y y z . El intento de encontrar una esquina donde bombardear esos espacios tenga sentido produce una esquina que se ve así:
0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .
Para este, me queda claro que la solución óptima es bombardear y 5 veces z 5 veces. Vayamos 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 b 6 veces y luego x 4 veces.
Ahora se convierte en un juego de cómo convertir esas intuiciones en principios sobre los que podemos construir.
¡Esperemos que sea continuado!
Aquí está mi solución ... No lo escribiré en 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 encontrarlo. Los puntos para bombardear.
En primer lugar, como @Luka Rahne dijo en uno de los comentarios, el orden en el que bombardeas no es importante, solo la combinación.
En segundo lugar, como muchos otros han dicho, bombardear 1-off 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 from the corners'' primero o último, no importa (en teoría) Bombardeamos esos primeros porque facilita las decisiones posteriores (en la práctica) Bombardeamos el punto que afecta a la mayoría de los puntos, mientras bombardeamos simultáneamente esos rincones.
Definamos Puntos de resistencia como los puntos en el tablero con la mayor cantidad de puntos no bombeables + el mayor número de 0 alrededor de ellos
Los puntos no bombeables se pueden definir como puntos que no existen en nuestro alcance actual de la placa que estamos viendo.
También definiré 4 límites que manejarán nuestro alcance: Top = 0, Left = 0, Bottom = k, right = j. (valores para empezar)
Finalmente, definiré las bombas óptimas como bombas que se lanzan en puntos adyacentes a puntos de resistencia y que tocan (1) el punto de resistencia de mayor valor y (2) el mayor número de puntos posible.
Con respecto 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 se pueden bombear (hay 5 puntos fuera del alcance de cada esquina). Así que bombardeamos los puntos en diagonal uno de las esquinas primero.
Algoritmo:
- Encuentra los 4 puntos óptimos de la bomba.
- Si un punto de bomba está bombardeando un punto de resistencia que toca 2 límites (es decir, una esquina), bombee hasta que el punto sea 0. De lo contrario, bombardee cada uno hasta que uno de los puntos de resistencia que toque el punto óptimo de la bomba sea 0.
- para cada límite: if (suma (límite) == 0) avance límite
repita hasta que TOP = ABAJO e IZQUIERDA = DERECHO
Intentaré escribir el código actual más tarde
Aquí hay otra idea:
Comencemos asignando un peso a cada espacio del tablero para determinar cuántos números se reducirían al lanzar 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 es sacar el máximo partido a nuestro dinero, por así decirlo.
Después de eso, actualiza el peso de cada espacio cuyo peso se ve afectado por la bomba. Este será el espacio que bombardeó, y cualquier espacio inmediatamente adyacente a él, y cualquier espacio inmediatamente adyacente a esos. En otras palabras, cualquier espacio que pudiera haber tenido su valor reducido a cero por el bombardeo, o el valor de un espacio vecino reducido a cero.
Luego, reordena los espacios de la lista por peso. Dado que solo un pequeño subconjunto de espacios tuvo su peso cambiado por el bombardeo, no tendrá que recurrir a toda la lista, simplemente mueva esos en la lista.
Bombardea el nuevo espacio de mayor peso y repite el procedimiento.
Esto garantiza que cada bombardeo reduzca tantos espacios como sea posible (básicamente, llega a la menor cantidad de espacios que ya son cero como sea posible), por lo que sería óptimo, excepto que pueden ser vínculos en pesos. Por lo tanto, es posible que deba realizar un seguimiento de la espalda cuando haya una corbata para el peso superior. Sin embargo, solo una corbata para el peso máximo es importante, no otras corbatas, así que espero que no sea demasiado retroceso.
Edición: el contraejemplo de Mysticial a continuación demuestra que, de hecho, esto no está garantizado para ser óptimo, independientemente de los empates en pesos. En algunos casos, reducir el peso lo máximo 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 haberlo hecho con una opció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 repetirlos desde el principio en un orden diferente y terminar con el mismo tablero resultante. Pero no se sigue de eso que puedas considerar cada bombardeo de forma independiente. O, al menos, cada bombardeo debe considerarse de una manera que tenga en cuenta qué tan bien configura la placa para los bombardeos posteriores.
Aquí hay una solución que generaliza las buenas propiedades de los rincones.
Supongamos que podemos encontrar un punto de caída perfecto para un campo dado, es decir, una mejor manera de disminuir el valor en él. Luego, para encontrar el número mínimo de bombas que se pueden lanzar, podría ser un primer borrador de un algoritmo (el código se copió 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 que 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 células. - Un punto de caída a para
(x, y)es mejor que un punto de caída b porque(x, y)si disminuye los valores en un superconjunto apropiado de las celdas que b disminuye. - Un punto de caída es máximo si no hay otro punto de caída mejor.
- Dos puntos de caída para
(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 si se deja caer 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 de base 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 en (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)es también el punto de caída perfecto (4, 0)y es el único punto de gota perfecto para el campo. Conduce a la solución perfecta para este campo (una caída 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)disminuir (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 cheques, obtengo el siguiente resultado para el ejemplo de 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 selección mínima de puntos de caída máximos, y luego calculamos 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). Eligiendo uno y luego calculando los resultados mínimos para este resultado:
Drop bomb on 1, 1
Drop bomb on 2, 2
Drop bomb on 1, 2
Drop bomb on 2, 1
2
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 kernel de 3x3 y verificas dónde está la suma es más fuerte ... y bombardea allí ... y hazlo hasta que el campo sea plano ... para este campo 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'');
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.
Usa alguna recursión, 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);
}
Puede hacer esto más eficiente almacenando en caché, si diferentes maneras llevan al mismo resultado, no debe repetir los mismos pasos.
Elaborar:
si el bombardeo de la celda 1,3,5 conduce al mismo resultado que el bombardeo de la celda 5,3,1, entonces, no debe volver a realizar todos los pasos siguientes para ambos casos, solo 1 es suficiente, debe almacenar en algún lugar todo Tabla de estados y uso de sus resultados.
Se puede utilizar un hash de estadísticas de tabla para hacer una comparación rápida.
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 de la meta:
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 al encontrar una mejor función de evaluación.
... pero pensando en este problema, estaba pensando que uno de los problemas principales es obtener cifras abandonadas en medio de ceros en algún momento, así que tomaría otro enfoque ... que es dominar los valores mínimos a cero, luego tratar de escape a cero como sea posible, lo que conduce a una minimización general de los valores existentes mínimos o menos
No puedo pensar en una forma de calcular el número real sin tan solo calcular la campaña de bombardeos usando mi mejor heurística y espero obtener un resultado razonable.
Así que mi método es calcular una métrica de eficiencia de bombardeo para cada celda, bombardear la celda con el valor más alto, ... iterar el proceso hasta que lo aplané todo. Algunos han defendido el uso de un daño potencial simple (es decir, una puntuación de 0 a 9) como métrica, pero se queda corto al golpear las celdas de alto valor y no hacer 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 negativo. Intuitivamente, esta métrica debe hacer una selección que ayude a maximizar el daño de la superposición en las celdas con recuentos altos en lugar de golpearlos directamente.
El código a continuación alcanza la destrucción total del campo de prueba en 28 bombas (tenga en cuenta que si se usa el daño potencial como métricas, se obtienen 31).
using System;
using System.Collections.Generic;
using System.Linq;
namespace
{
internal class Program
{
// store the battle field as flat array + dimensions
private static int _width = 5;
private static int _length = 7;
private static int[] _field = new int[] {
2, 3, 4, 7, 1,
1, 5, 2, 6, 2,
4, 3, 4, 2, 1,
2, 1, 2, 4, 1,
3, 1, 3, 4, 1,
2, 1, 4, 3, 2,
6, 9, 1, 6, 4
};
// this will store the devastation metric
private static int[] _metric;
// do the work
private static void Main(string[] args)
{
int count = 0;
while (_field.Sum() > 0)
{
Console.Out.WriteLine("Round {0}:", ++count);
GetBlastPotential();
int cell_to_bomb = FindBestBombingSite();
PrintField(cell_to_bomb);
Bomb(cell_to_bomb);
}
Console.Out.WriteLine("Done in {0} rounds", count);
}
// convert 2D position to 1D index
private static int Get1DCoord(int x, int y)
{
if ((x < 0) || (y < 0) || (x >= _width) || (y >= _length)) return -1;
else
{
return (y * _width) + x;
}
}
// Convert 1D index to 2D position
private static void Get2DCoord(int n, out int x, out int y)
{
if ((n < 0) || (n >= _field.Length))
{
x = -1;
y = -1;
}
else
{
x = n % _width;
y = n / _width;
}
}
// Compute a list of 1D indices for a cell neighbours
private static List<int> GetNeighbours(int cell)
{
List<int> neighbours = new List<int>();
int x, y;
Get2DCoord(cell, out x, out y);
if ((x >= 0) && (y >= 0))
{
List<int> tmp = new List<int>();
tmp.Add(Get1DCoord(x - 1, y - 1));
tmp.Add(Get1DCoord(x - 1, y));
tmp.Add(Get1DCoord(x - 1, y + 1));
tmp.Add(Get1DCoord(x, y - 1));
tmp.Add(Get1DCoord(x, y + 1));
tmp.Add(Get1DCoord(x + 1, y - 1));
tmp.Add(Get1DCoord(x + 1, y));
tmp.Add(Get1DCoord(x + 1, y + 1));
// eliminate invalid coords - i.e. stuff past the edges
foreach (int c in tmp) if (c >= 0) neighbours.Add(c);
}
return neighbours;
}
// Compute the devastation metric for each cell
// Represent the Value of the cell minus the sum of all its neighbours
private static void GetBlastPotential()
{
_metric = new int[_field.Length];
for (int i = 0; i < _field.Length; i++)
{
_metric[i] = _field[i];
List<int> neighbours = GetNeighbours(i);
if (neighbours != null)
{
foreach (int j in neighbours) _metric[i] -= _field[j];
}
}
for (int i = 0; i < _metric.Length; i++)
{
_metric[i] = (_metric[i] < 0) ? Math.Abs(_metric[i]) : 0;
}
}
//// Compute the simple expected damage a bomb would score
//private static void GetBlastPotential()
//{
// _metric = new int[_field.Length];
// for (int i = 0; i < _field.Length; i++)
// {
// _metric[i] = (_field[i] > 0) ? 1 : 0;
// List<int> neighbours = GetNeighbours(i);
// if (neighbours != null)
// {
// foreach (int j in neighbours) _metric[i] += (_field[j] > 0) ? 1 : 0;
// }
// }
//}
// Update the battle field upon dropping a bomb
private static void Bomb(int cell)
{
List<int> neighbours = GetNeighbours(cell);
foreach (int i in neighbours)
{
if (_field[i] > 0) _field[i]--;
}
}
// Find the best bombing site - just return index of local maxima
private static int FindBestBombingSite()
{
int max_idx = 0;
int max_val = int.MinValue;
for (int i = 0; i < _metric.Length; i++)
{
if (_metric[i] > max_val)
{
max_val = _metric[i];
max_idx = i;
}
}
return max_idx;
}
// Display the battle field on the console
private static void PrintField(int cell)
{
for (int x = 0; x < _width; x++)
{
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _field[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _field[c]).PadLeft(4));
}
Console.Out.Write(" || ");
for (int y = 0; y < _length; y++)
{
int c = Get1DCoord(x, y);
if (c == cell)
Console.Out.Write(string.Format("[{0}]", _metric[c]).PadLeft(4));
else
Console.Out.Write(string.Format(" {0} ", _metric[c]).PadLeft(4));
}
Console.Out.WriteLine();
}
Console.Out.WriteLine();
}
}
}
El patrón de bombardeo resultante se genera de la siguiente manera (valores de campo a la izquierda, métricas 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
Si desea la solución óptima absoluta para limpiar el tablero, tendrá que usar el backtracking clásico, pero si la matriz es muy grande, le llevará mucho tiempo encontrar la mejor solución, si desea una solución óptima "posible" puede usar un algoritmo codicioso , si necesitas ayuda para escribir el algoritmo te puedo ayudar
Ahora que lo pienso es la mejor manera. Haga otra matriz allí donde almacene los puntos que elimine dejando caer una bomba allí, luego elija la celda con el máximo de puntos 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 mayor que 0
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 sueltes las bombas, por lo que realmente cualquier opción de lanzamientos 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".
Puede intentar primero calcular todos los estados de la placa resultantes de la caída de 1 bomba, luego usarlos para calcular todos los estados de la placa resultantes de las caídas de 2 bombas, etc. hasta obtener todos los ceros. Pero en cada paso almacenaría en caché los estados utilizando la clave que definí anteriormente, de modo que puede usar estos resultados para calcular el siguiente paso (un enfoque de "programación dinámica").
Pero dependiendo del tamaño de n, m y los números en la cuadrícula, los requisitos de memoria de este enfoque pueden ser excesivos. Puedes tirar todos los resultados de N bombas una vez que hayas calculado todos los resultados de N + 1, por lo que hay algunos ahorros allí. Y, por supuesto, no se 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.
Esta solución codiciosa parece ser correcta :
Como se señala en los comentarios, fallará en 2D. Pero quizás puedas mejorarlo.
Para 1D:
si hay al menos 2 números, no es necesario disparar a la izquierda porque disparar a la segunda no es peor . Así que dispara al segundo, mientras que el primero no es 0, porque tienes que hacerlo. Mover a la siguiente celda. No te olvides de la ú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])
}
}
Así que para 2D:
Nuevamente: no es necesario disparar en la primera fila (si existe la segunda). Así que dispara a la segunda. Resuelve la tarea 1D para la primera fila. (porque hay que hacerlo nulo). Bajar. No te olvides de la última fila.
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 todas las posibles ubicaciones de bombardeo. Para ver un ejemplo, vea la implementación de Alfe .
Luego, comprenda que podemos trabajar para bombardear de abajo hacia arriba y aún así obtener un patrón de bombardeo mínimo.
- Comience desde la esquina inferior izquierda.
- Bombéelo al olvido con las únicas jugadas que tienen sentido (arriba y a la derecha).
- Mueve una casilla a la derecha.
- Si bien el objetivo tiene un valor mayor que cero, considere cada una de las 2 jugadas que tienen 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.
- Mueve otro a la derecha.
- Si bien el objetivo tiene un valor mayor que cero, considera cada una de las 3 jugadas que tienen sentido (arriba a la izquierda, arriba y arriba a la derecha), reduce el valor del objetivo en uno y crea una nueva rama para cada posibilidad.
- Repita los pasos 5 y 6 hasta que se elimine la fila.
- Sube una fila y repite los pasos 1 a 7 hasta que se resuelva el rompecabezas.
Este algoritmo es correcto porque
- Es necesario completar cada fila en algún momento.
- Completar una fila siempre requiere una jugada ya sea arriba, una abajo o dentro de esa fila.
- Siempre es tan bueno o mejor elegir una jugada por encima de la fila más baja que la más baja que una jugada en la fila o debajo de la fila.
En la práctica, este algoritmo funcionará mejor que su máximo teórico porque bombardeará regularmente a los vecinos y reducirá el tamaño de la búsqueda. Si asumimos 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).
Debido a que este algoritmo es todavía exponencial, sería prudente limitar la profundidad de la búsqueda. Podríamos limitar el número de sucursales permitido a un número, X, y una vez que lleguemos a este nivel, forzamos al algoritmo a elegir la mejor ruta que haya identificado hasta ahora (la que tiene la suma total mínima de tableros en una de sus hojas terminales ). Entonces, se garantiza que nuestro algoritmo se ejecutará en O (3 ^ X), pero no se garantiza que obtenga la respuesta correcta. Sin embargo, siempre podemos aumentar X y probar empíricamente si vale la pena el intercambio entre una mayor computación y mejores respuestas.
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 sume y sus ocho vecinos, se podría usar como una cantidad eficiente de bombardeo en este punto. Esto proporcionará cerca de la secuencia óptima de bombas.
UPD : También debemos tener en cuenta el número de ceros, ya que bombardearlos es ineficiente. De hecho, el problema es minimizar el número de ceros golpeados. Pero no podemos saber cómo un 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.
Parece que hay una subestructura no partidista de ambos partidos 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 cobertura mínima de los vértices de un ciclo de 9 por sus bordes.
Este caso, en particular, muestra que la relajación de la 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 planar con la menor cantidad de bordes posible" a su problema, lo que me hace dudar de que alguna de las soluciones codiciosas / de escalada funcionará.
No veo una manera de resolver esto en el tiempo polinomial en el peor de los casos. Puede que haya una solución muy inteligente de búsqueda binaria y DP que no estoy viendo.
EDITAR : veo que el concurso ( http://deadline24.pl ) es de lenguaje agnóstico; te envían un montón de archivos de entrada y tú les envías salidas. Así que no necesitas algo que funcione en el peor momento polinomial. En particular, puedes ver la entrada !
Hay un montón de casos pequeños en la entrada. Luego hay un estuche 10x1000, un estuche 100x100 y un estuche 1000x1000. Los tres grandes casos son todos muy bien comportados. Las entradas horizontalmente adyacentes suelen tener el mismo valor. En una máquina relativamente robusta, puedo resolver todos los casos mediante el uso de CPLEX en tan solo unos minutos. Tuve suerte en el 1000x1000; La relajación del LP pasa a tener una solución óptima integral. Mis soluciones están de acuerdo con los .ansarchivos proporcionados en el paquete de datos de prueba.
Apostaría a que puedes usar la estructura de la entrada de una manera mucho más directa que yo si la miraras; Parece que puedes cortar la primera fila, o dos, o tres repetidamente hasta que no te quede nada. (Parece que, en el 1000x1000, ¿todas las filas no aumentan? ¿Supongo que de ahí viene tu "parte B"?
Podrías usar la planificación estatal del espacio. Por ejemplo, utilizando A * (o una de sus variantes) junto con una heurística f = g + hcomo esta:
- g: número de bombas lanzadas hasta el momento
- h: suma sobre todos los valores de la cuadrícula dividido por 9 (que es el mejor resultado, lo que significa que tenemos una heurística admisible)
También tengo 28 movimientos. Usé dos pruebas para el mejor movimiento siguiente: primero el movimiento que produce la suma mínima para el tablero. Segundo, para sumas iguales, el movimiento que produce la densidad máxima, definido como:
number-of-zeros / number-of-groups-of-zeros
Esto es Haskell. "resolver tablero" muestra la solución del motor. Puede jugar al juego escribiendo "main", luego ingrese un punto objetivo, "best" para una recomendación, o "quit" para salir.
SALIDA:
* Principal> panel de soluciones
[(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)
Todo este problema se reduce a calcular una distancia de edición. Simplemente calcule una variante de la distancia 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 arreglos intermedios. Sugiero usar un hash de las matrices como clave. En pseudo-pitón:
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