Algorithme de largage de bombes

J'ai une n x mmatrice composée d'entiers non négatifs. Par exemple:

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

"Lâcher une bombe" diminue de un le nombre de la cellule cible et de ses huit voisins, jusqu'à un minimum de zéro.

x x x 
x X x
x x x

Qu'est-ce qu'un algorithme qui déterminerait le nombre minimum de bombes nécessaires pour réduire toutes les cellules à zéro?

Option B (parce que je ne suis pas un lecteur attentif)

En fait, la première version du problème n'est pas celle pour laquelle je cherche une réponse. Je n'ai pas lu attentivement toute la tâche, il y a des contraintes supplémentaires, disons:

Qu'en est-il du problème simple, lorsque la séquence en ligne doit être non croissante:

8 7 6 6 5 est une séquence d'entrée possible

7 8 5 5 2 n'est pas possible puisque 7 -> 8 croissent en séquence.

Peut-être que trouver une réponse pour un cas "plus facile" aiderait à trouver une solution pour un cas plus difficile.

PS: Je crois que lorsque nous avons plusieurs mêmes situations nécessitant un minimum de bombes pour dégager la ligne supérieure, nous en choisissons une qui utilise la plupart des bombes sur le "côté gauche" de la rangée. Toujours une preuve qui pourrait être correcte?

Il existe un moyen de réduire cela à un simple sous-problème.

L'explication, l'algorithme et la raison pour laquelle l'algorithme fournit une solution optimale sont en deux parties. Le premier n'aura pas de sens sans le second, je vais donc commencer par le pourquoi.

Si vous pensez bombarder le rectangle (supposez un grand rectangle - pas encore de cas de bord), vous pouvez voir que la seule façon de réduire le rectangle creux des carrés sur le périmètre à 0 est de bombarder le périmètre ou de bombarder le rectangle creux de carrés juste à l'intérieur du périmètre. J'appellerai la couche de périmètre 1 et le rectangle à l'intérieur de la couche 2.

Un aperçu important est qu'il n'y a pas de couche de bombardement ponctuel 1, car le "rayon de souffle" que vous obtenez en le faisant est toujours contenu dans le rayon de souffle d'un autre carré de la couche 2. Vous devriez pouvoir vous en convaincre facilement.

Donc, nous pouvons réduire le problème à trouver un moyen optimal de bombarder le périmètre, puis nous pouvons répéter cela jusqu'à ce que tous les carrés soient à 0.

Mais bien sûr, cela ne trouvera pas toujours une solution optimale s'il est possible de bombarder le périmètre d'une manière moins qu'optimale, mais en utilisant X bombes supplémentaires, le problème de la réduction de la couche intérieure est simplifié par> X bombes. Donc, si nous appelons la couche permiter un, si nous plaçons X bombes supplémentaires quelque part dans la couche 2 (juste à l'intérieur de la couche 1), pouvons-nous réduire l'effort de bombardement ultérieur loin de la couche 2 de plus de X? En d'autres termes, nous devons prouver que nous pouvons être gourmands en réduisant le périmètre extérieur.

Mais, nous savons que nous pouvons être gourmands. Parce qu'aucune bombe dans la couche 2 ne peut jamais être plus efficace pour réduire la couche 2 à 0 qu'une bombe stratégiquement placée dans la couche 3. Et pour la même raison qu'auparavant - il y a toujours une bombe que nous pouvons placer dans la couche 3 qui affectera chaque carré de la couche 2 qu'une bombe placée dans la couche 2 peut. Ainsi, il ne peut jamais nous nuire d'être gourmand (dans ce sens de gourmand).

Donc, tout ce que nous avons à faire est de trouver le moyen optimal de réduire le permiter à 0 en bombardant la couche intérieure suivante.

Nous ne sommes jamais blessés en bombardant d'abord le coin à 0, car seul le coin de la couche intérieure peut l'atteindre, nous n'avons donc vraiment pas le choix (et, toute bombe sur le périmètre qui peut atteindre le coin a un rayon d'explosion contenu dans le rayon de souffle à partir du coin de la couche intérieure).

Une fois que nous l'avons fait, les carrés sur le périmètre adjacent au coin 0 ne peuvent être atteints que par 2 carrés de la couche intérieure:

0       A       B

C       X       Y

D       Z

À ce stade, le périmètre est effectivement une boucle fermée à une dimension, car toute bombe réduira 3 carrés adjacents. À l'exception d'une certaine bizarrerie près des coins - X peut "frapper" A, B, C et D.

Maintenant, nous ne pouvons pas utiliser d'astuces de rayon de souffle - la situation de chaque carré est symétrique, à l'exception des coins étranges, et même là, aucun rayon de souffle n'est un sous-ensemble d'un autre. Notez que s'il s'agissait d'une ligne (comme l'explique le colonel Panic) au lieu d'une boucle fermée, la solution est triviale. Les points d'extrémité doivent être réduits à 0, et cela ne vous nuit jamais de bombarder les points adjacents aux points d'extrémité, encore une fois parce que le rayon de souffle est un surensemble. Une fois que vous avez fait de votre point de terminaison 0, vous avez toujours un nouveau point de terminaison, donc répétez (jusqu'à ce que la ligne soit à 0).

Donc, si nous pouvons réduire de manière optimale un seul carré de la couche à 0, nous avons un algorithme (car nous avons coupé la boucle et avons maintenant une ligne droite avec des points de terminaison). Je crois que le bombardement adjacent au carré avec la valeur la plus basse (vous donnant 2 options) de sorte que la valeur la plus élevée dans les 2 carrés de cette valeur la plus basse soit le minimum possible (vous devrez peut-être diviser votre bombardement pour gérer cela) sera optimal mais je n'ont pas (encore?) de preuve.

Pólya dit "Si vous ne pouvez pas résoudre un problème, alors il y a un problème plus facile que vous pouvez résoudre: le trouver."

Le problème le plus simple évident est le problème à une dimension (lorsque la grille est une seule ligne). Commençons par l'algorithme le plus simple - bombardant avidement la plus grande cible. Quand est-ce que ça va mal?

Étant donné 1 1 1, l'algorithme gourmand est indifférent à la cellule qu'il bombarde en premier. Bien sûr, la cellule centrale est meilleure - elle met à zéro les trois cellules à la fois. Cela suggère un nouvel algorithme A, "bombe pour minimiser la somme restante". Quand cet algorithme tourne-t-il mal?

Étant donné 1 1 2 1 1, l'algorithme A est indifférent entre le bombardement des 2e, 3e ou 4e cellules. Mais bombarder la 2e cellule pour partir 0 0 1 1 1est mieux que bombarder la 3e cellule pour partir 1 0 1 0 1. Comment y remédier? Le problème avec le bombardement de la 3ème cellule est qu'il nous laisse travailler à gauche et à droite ce qui doit être fait séparément.

Que diriez-vous de "bombarder pour minimiser la somme restante, mais maximiser le minimum à gauche (d'où nous avons bombardé) plus le minimum à droite". Appelez cet algorithme B. Quand cet algorithme va-t-il mal?

Edit: Après avoir lu les commentaires, je conviens qu'un problème beaucoup plus intéressant serait le problème unidimensionnel changé de sorte que les extrémités se rejoignent. J'adorerais voir des progrès à ce sujet.

Je n'ai dû m'arrêter qu'à une solution partielle car je n'avais plus de temps, mais j'espère que même cette solution partielle fournit des informations sur une approche potentielle pour résoudre ce problème.

Face à un problème difficile, j'aime trouver des problèmes plus simples pour développer une intuition sur l'espace des problèmes. Ici, la première étape que j'ai prise a été de réduire ce problème 2D en un problème 1D. Considérez une ligne:

0 4 2 1 3 0 1

D'une manière ou d'une autre, vous savez que vous devrez bombarder 44 fois à l' endroit ou aux alentours pour le ramener à 0. Étant donné que la gauche de l'endroit est un nombre inférieur, il n'y a aucun avantage à bombarder le bombardement 0ou le 4bombardement excessif du 2. En fait, je crois (mais il manque une preuve rigoureuse) que bombarder le 2jusqu'à ce que le 4point descende à 0 soit au moins aussi bon que toute autre stratégie pour le ramener 4à 0. On peut continuer sur la ligne de gauche à droite dans une stratégie comme ça:

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

Quelques exemples d'ordres de bombardement:

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

L'idée de commencer par un nombre qui doit descendre d'une manière ou d'une autre est intéressante, car il devient soudainement possible de trouver une solution qui, selon certains, prétend être au moins aussi bonne que toutes les autres solutions.

La prochaine étape dans la complexité où cette recherche d' au moins aussi bonne est encore possible est à la limite. Il est clair pour moi qu'il n'y a jamais aucun avantage strict à bombarder le bord extérieur; vous feriez mieux de bombarder l'endroit et d'obtenir trois autres espaces gratuitement. Compte tenu de cela, nous pouvons dire que bombarder l'anneau à l'intérieur du bord est au moins aussi bon que bombarder le bord. De plus, nous pouvons combiner cela avec l'intuition que bombarder le bon à l'intérieur du bord est en fait le seul moyen de ramener les espaces de bord à 0. De plus, il est trivialement simple de déterminer la stratégie optimale (en ce sens qu'elle est à moins bonne que toute autre stratégie) pour ramener les nombres de coins à 0. Nous mettons tout cela ensemble et nous pouvons nous rapprocher beaucoup plus d'une solution dans l'espace 2D.

Compte tenu de l'observation des pièces d'angle, nous pouvons dire avec certitude que nous connaissons la stratégie optimale pour passer de n'importe quelle planche de départ à une planche avec des zéros à tous les coins. Ceci est un exemple d'un tel tableau (j'ai emprunté les chiffres des deux tableaux linéaires ci-dessus). J'ai étiqueté certains espaces différemment et je vais vous expliquer pourquoi.

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

On remarquera à la rangée supérieure vraiment ressemble de près l'exemple linéaire , nous avons vu plus haut. Rappelant notre observation précédente selon laquelle la meilleure façon de ramener la rangée du haut à 0 est de bombarder la deuxième rangée (la xrangée). Il n'y a aucun moyen d'effacer la rangée supérieure en bombardant l'une des yrangées et aucun avantage supplémentaire de bombarder la rangée supérieure par rapport à bombarder l'espace correspondant sur la xrangée.

Nous pourrions appliquer la stratégie linéaire par le haut (bombarder les espaces correspondants sur la xrangée), nous concernant uniquement avec la rangée supérieure et rien d'autre. Cela ressemblerait à quelque chose comme ceci:

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 faille dans cette approche devient très évidente lors des deux derniers bombardements. C'est clair, étant donné que les seuls sites de bombes qui réduisent le 4chiffre dans la première colonne de la deuxième ligne sont le premier xet le y. Les deux derniers bombardements sont clairement inférieurs au simple bombardement du premier x, ce qui aurait fait exactement la même chose (en ce qui concerne la première place de la rangée supérieure, que nous n'avons pas d'autre moyen de nettoyer). Puisque nous avons démontré que notre stratégie actuelle n'est pas optimale, une modification de stratégie est clairement nécessaire.

À ce stade, je peux prendre du recul dans la complexité et me concentrer uniquement sur un coin. Considérons celui-ci:

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

Il est clair que la seule façon d'obtenir les espaces avec 4à zéro sont à la bombe une combinaison de x, yet z. Avec quelques acrobaties dans mon esprit, je suis presque sûr que la solution optimale est de bombarder xtrois fois et aensuite b. Il s'agit maintenant de comprendre comment j'ai trouvé cette solution et si elle révèle une intuition que nous pouvons utiliser pour même résoudre ce problème local. Je remarque qu'il n'y a pas de bombardement yet des zespaces. Tenter de trouver un coin où bombarder ces espaces est logique donne un coin qui ressemble à ceci:

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

Pour celui-ci, il est clair pour moi que la solution optimale est de bombarder y5 fois et z5 fois. Allons plus loin.

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

Ici, il se sent de la même intuitive que la solution est à la bombe aet b6 fois, puis x4 fois.

Maintenant, cela devient un jeu sur la façon de transformer ces intuitions en principes sur lesquels nous pouvons nous appuyer.

J'espère que cela se poursuivra!

Pour une question mise à jour, un simple algorithme gourmand donne un résultat optimal.

Déposez des bombes A [0,0] dans la cellule A [1,1], puis déposez des bombes A [1,0] dans la cellule A [2,1] et poursuivez ce processus vers le bas. Pour nettoyer le coin inférieur gauche, déposez des bombes max (A [N-1,0], A [N-2,0], A [N-3,0]) dans la cellule A [N-2,1]. Cela nettoiera complètement les 3 premières colonnes.

Avec la même approche, nettoyer les colonnes 3,4,5, puis les colonnes 6,7,8, etc.

Malheureusement, cela n'aide pas à trouver une solution au problème d'origine.

Un problème "plus important" (sans contrainte "non croissante") peut s'avérer être NP-difficile. Voici l'esquisse d'une preuve.

Supposons que nous ayons un graphe planaire de degré jusqu'à 3. Trouvons la couverture minimale des sommets pour ce graphe. Selon un article de Wikipédia, ce problème est NP-difficile pour les graphiques planaires de degré jusqu'à 3. Cela pourrait être prouvé par une réduction de Planar 3SAT. Et la dureté de Planar 3SAT - par réduction de 3SAT. Ces deux preuves sont présentées dans des conférences récentes dans "Algorithmic Lower Bounds" par le prof. Erik Demaine (conférences 7 et 9).

Si nous divisons certaines arêtes du graphique d'origine (graphique de gauche sur le diagramme), chacune avec un nombre pair de nœuds supplémentaires, le graphique résultant (graphique de droite sur le diagramme) devrait avoir exactement la même couverture de sommet minimale pour les sommets d'origine. Une telle transformation permet d'aligner les sommets du graphe sur des positions arbitraires sur la grille.

Si nous plaçons les sommets du graphe uniquement sur des lignes et des colonnes paires (de manière à ce qu'il n'y ait pas deux arêtes incidentes à un sommet formant un angle aigu), insérons "un" partout où il y a une arête et insérez des "zéros" dans d'autres positions de la grille, nous pourrions utiliser n'importe quelle solution pour le problème d'origine pour trouver la couverture minimale des sommets.

Vous pouvez représenter ce problème comme un problème de programmation entier . (ce n'est qu'une des solutions possibles pour aborder ce problème)

Avoir des points:

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

on peut écrire 16 équations où pour le point f par exemple détient

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

minimisé sur la somme de tous les index et de la solution entière.

La solution est bien sûr la somme de ces indices.

Cela peut être encore simplifié en définissant tous les xi sur les limites 0, de sorte que vous finissez par avoir l'équation 4 + 1 dans cet exemple.

Le problème est qu'il n'y a pas d'algorithme trivial pour résoudre de tels problèmes. Je ne suis pas expert en la matière, mais résoudre ce problème en tant que programmation linéaire est difficile en NP.

Ceci est une réponse partielle, j'essaie de trouver une limite inférieure et une limite supérieure qui pourraient être le nombre possible de bombes.

En carte 3x3 et plus petite, la solution est trivialement toujours la plus grande cellule numérotée.

Dans les planches de plus de 4x4, la première borne inférieure évidente est la somme des coins:

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

quelle que soit l'organisation de la bombe, il est impossible de nettoyer cette planche 4x4 avec moins de 2 + 1 + 6 + 4 = 13 bombes.

Il a été mentionné dans d'autres réponses que placer la bombe sur le deuxième au coin pour éliminer le coin n'est jamais pire que de placer la bombe sur le coin lui-même, donc étant donné la carte:

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

Nous pouvons éliminer les coins en plaçant des bombes sur le deuxième au coin pour donner une nouvelle planche:

 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

Jusqu'ici tout va bien. Nous avons besoin de 13 bombes pour nettoyer les coins.

Observez maintenant les numéros 6, 4, 3 et 2 indiqués ci-dessous:

 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

Il n'y a aucun moyen de bombarder deux de ces cellules en utilisant une seule bombe, donc la bombe minimale a augmenté de 6 + 4 + 3 + 2, donc en ajoutant au nombre de bombes que nous avons utilisées pour dégager les coins, nous obtenons que le minimum le nombre de bombes nécessaires pour cette carte est devenu 28 bombes. Il est impossible de nettoyer cette carte avec moins de 28 bombes, c'est la limite inférieure de cette carte.

Vous pouvez utiliser un algorithme gourmand pour établir une limite supérieure. D'autres réponses ont montré qu'un algorithme gourmand produit une solution qui utilise 28 bombes. Comme nous avons prouvé précédemment qu'aucune solution optimale ne peut avoir moins de 28 bombes, donc 28 bombes est en effet une solution optimale.

Lorsque gourmand et que la méthode pour trouver la limite minimale que j'ai mentionnée ci-dessus ne convergent pas, je suppose que vous devez revenir à la vérification de toutes les combinaisons.

L'algorithme de recherche de la borne inférieure est le suivant:

1. Choisissez un élément avec le nombre le plus élevé, nommez-le P.
2. Marquez toutes les cellules à deux pas de P et P lui-même comme non récupérables.
3. Ajoutez P à la minimumsliste.
4. Répétez à l'étape 1 jusqu'à ce que toutes les cellules ne soient pas récupérables.
5. Additionnez la minimumsliste pour obtenir la borne inférieure.

Ce serait une approche gourmande:

1. Calculez une matrice «score» d'ordre n X m, où score [i] [j] est la déduction totale des points dans la matrice si la position (i, j) est bombardée. (Le score maximum d'un point est de 9 et le score minimum est de 0)

2. En vous déplaçant en ligne, trouvez et choisissez la première position avec le score le plus élevé (disons (i, j)).

3. Bombe (i, j). Augmentez le nombre de bombes.

4. Si tous les éléments de la matrice d'origine ne sont pas nuls, passez à 1.

Je doute cependant que ce soit la solution optimale.

Éditer:

L'approche gourmande que j'ai postée ci-dessus, alors qu'elle fonctionne, ne nous donne probablement pas la solution optimale. J'ai donc pensé qu'il fallait y ajouter quelques éléments de DP.

Je pense que nous pouvons convenir qu'à tout moment, l'une des positions avec le "score" le plus élevé (score [i] [j] = déduction totale des points si (i, j) est bombardé) doit être ciblée. En partant de cette hypothèse, voici la nouvelle approche:

NumOfBombs (M): (renvoie le nombre minimum de bombardements requis)

1. Soit une matrice M d'ordre n X m. Si tous les éléments de M sont nuls, retournez 0.

2. Calculez la matrice "score" M.

   Soit les k positions distinctes P1, P2, ... Pk (1 <= k <= n * m), les positions en M ayant les scores les plus élevés.

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

   où M1, M2, ..., Mk sont les matrices résultantes si nous bombardons respectivement les positions P1, P2, ..., Pk.

De plus, si nous voulons que l'ordre des positions nuke en plus de cela, nous devons garder une trace des résultats de "min".

Votre nouveau problème, avec les valeurs non décroissantes sur les lignes, est assez facile à résoudre.

Notez que la colonne de gauche contient les nombres les plus élevés. Par conséquent, toute solution optimale doit d'abord réduire cette colonne à zéro. Ainsi, nous pouvons effectuer un bombardement 1-D sur cette colonne, en réduisant chaque élément à zéro. Nous laissons les bombes tomber sur la deuxième colonne pour qu'elles causent un maximum de dégâts. Il y a beaucoup de messages ici traitant du cas 1D, je pense, donc je me sens en sécurité pour sauter ce cas. (Si vous voulez que je le décrive, je le peux.). En raison de la propriété décroissante, les trois colonnes les plus à gauche seront toutes réduites à zéro. Mais, nous allons probablement utiliser un nombre minimum de bombes ici parce que la colonne de gauche doit être mise à zéro.

Maintenant, une fois la colonne de gauche mise à zéro, nous supprimons simplement les trois colonnes les plus à gauche qui sont maintenant mises à zéro et répétons avec la matrice maintenant réduite. Cela doit nous donner une solution optimale car à chaque étape nous utilisons un nombre minimum de bombes prouvable.

Programmation linéaire en nombres entiers de Mathematica à l'aide d'une branche et d'une borne

Comme cela a déjà été mentionné, ce problème peut être résolu en utilisant une programmation linéaire entière (qui est NP-Hard ). Mathematica a déjà intégré ILP. "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."[Voir Tutoriel sur l' optimisation contrainte dans Mathematica ..]

J'ai écrit le code suivant qui utilise les bibliothèques ILP de Mathematica. C'est étonnamment rapide.

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

Pour l'exemple fourni dans le problème:

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]

Les sorties

Pour tous ceux qui lisent ceci avec un algorithme gourmand

Essayez votre code sur le problème 10x10 suivant:

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

Ici, il est séparé par des virgules:

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

Pour ce problème, ma solution contient 208 bombes. Voici une solution possible (j'ai pu résoudre ce problème en 12 secondes environ).

Pour tester les résultats que Mathematica produit, voyez si votre algorithme gourmand peut faire mieux.

Il n'est pas nécessaire de transformer le problème en sous-problèmes linéaires.

Utilisez à la place une simple heuristique gourmande, qui consiste à bombarder les coins , en commençant par le plus grand.

Dans l'exemple donné, il y a quatre coins, {2, 1, 6, 4}. Pour chaque coin, il n'y a pas de meilleur mouvement que de bombarder la cellule en diagonale vers le coin, nous savons donc que nos premiers bombardements 2 + 1 + 6 + 4 = 13 doivent être dans ces cellules diagonales. Après avoir fait le bombardement, nous nous retrouvons avec une nouvelle matrice:

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 

Après les 13 premiers bombardements, nous utilisons l'heuristique pour éliminer 3 0 2 via trois bombardements. Maintenant, nous avons 2 nouveaux coins, {2, 1} dans la 4ème rangée. Nous bombardons ces trois autres bombardements. Nous avons maintenant réduit la matrice à 4 x 4. Il y a un coin, en haut à gauche. Nous bombardons cela. Il nous reste maintenant 2 coins, {5, 3}. Puisque 5 est le plus grand coin, nous bombardons ce premier, 5 bombardements, puis finalement bombardons le 3 dans l'autre coin. Le total est de 13 + 3 + 3 + 1 + 5 + 3 = 28.

Cela fait une recherche approfondie du chemin le plus court (une série de bombardements) à travers ce "labyrinthe" de positions. Non, je ne peux pas prouver qu'il n'y a pas d'algorithme plus rapide, désolé.

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

Il semble qu'une approche de programmation linéaire puisse être très utile ici.

Soit P _{m xn} la matrice avec les valeurs des positions:

Définissons maintenant une matrice de bombe B (x, y) _mxn , avec 1 ≤ x ≤ m , 1 ≤ y ≤ n comme ci-dessous

de telle sorte que

Par exemple:

Nous cherchons donc à une matrice B _{m xn} = [ b _ij ] qui

1. Peut être défini comme une somme de matrices de bombes:

   

   ( q _ij serait alors la quantité de bombes que nous laisserions tomber en position p _ij )

2. p _ij - b _ij ≤ 0 (pour être plus succinct, disons-le comme P - B ≤ 0 )

De plus, B devrait minimiser la somme .

Nous pouvons également écrire B comme la matrice laide à venir:

et depuis P - B ≤ 0 (ce qui signifie P ≤ B ) nous avons le système d'inégalité assez linéaire suivant ci-dessous:

Étant q _{mn x 1} défini comme

p _{mn x 1} défini comme

On peut dire qu'on a un système Le système ci-dessous est représenté comme le produit de matrices http://latex.codecogs.com/gif.download?S%5Cmathbf%7Bq%7D&space;%5Cge&space;%5Cmathbf%7Bp%7D étant S _{mn x mn} la matrice à inverser pour résoudre le système. Je ne l'ai pas développé moi-même mais je pense qu'il devrait être facile de le faire en code.

Maintenant, nous avons un problème minimum qui peut être déclaré comme

Je crois que c'est quelque chose de facile, presque trivial à résoudre avec quelque chose comme l' algorithme simplex (il y a ce doc plutôt cool à ce sujet ). Cependant, je ne connais presque pas de programmation linéaire (je vais suivre un cours à ce sujet sur Coursera mais c'est juste dans le futur ...), j'ai eu quelques maux de tête en essayant de le comprendre et j'ai un énorme travail indépendant à terminer donc j'ai abandonne juste ici. Il se peut que j'aie fait quelque chose de mal à un moment donné, ou que cela ne puisse pas aller plus loin, mais je crois que cette voie peut éventuellement conduire à la solution. Quoi qu'il en soit, je suis impatient de vos commentaires.

(Un merci spécial pour ce site incroyable pour créer des images à partir d'expressions LaTeX )

Cette solution gourmande semble être correcte :

Comme indiqué dans les commentaires, il échouera en 2D. Mais vous pouvez peut-être l'améliorer.

Pour 1D:
S'il y a au moins 2 nombres, vous n'avez pas besoin de tirer vers le plus à gauche car le tir vers le second n'est pas pire . Tirez donc sur le second, alors que le premier n'est pas 0, car vous devez le faire. Passez à la cellule suivante. N'oubliez pas la dernière cellule.

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

Donc pour 2D:
Encore une fois: vous n'avez pas besoin de tirer dans la première rangée (s'il y a la seconde). Alors tirez sur le second. Résoudre la tâche 1D pour la première ligne. (parce que vous devez le rendre nul). Descendre. N'oubliez pas la dernière rangée.

Pour minimiser le nombre de bombes, nous devons maximiser l'effet de chaque bombe. Pour y parvenir, à chaque étape, nous devons sélectionner la meilleure cible. Pour chaque point qui le résume et ses huit voisins - pourrait être utilisé comme quantité d'efficacité pour bombarder ce point. Cela fournira une séquence de bombes presque optimale.

UPD : Nous devons également prendre en compte le nombre de zéros, car les bombarder est inefficace. En fait, le problème est de minimiser le nombre de zéros frappés. Mais nous ne pouvons pas savoir comment une étape nous rapproche de cet objectif. Je suis d'accord avec l'idée que le problème est NP-complet. Je propose une approche gourmande, qui donnera une réponse proche du réel.

Je crois que pour minimiser la quantité de bombes, vous devez simplement maximiser la quantité de dégâts .. pour que cela se produise, vous devez vérifier la zone qui a la force la plus forte .. vous devez donc d'abord analyser le champ avec un noyau 3x3 et vérifier où la somme est plus fort .. et bombe là-bas .. et faites jusqu'à ce que le champ soit plat .. pour cela déposé la réponse est 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');

Voici une solution qui généralise les bonnes propriétés des coins.

Supposons que nous puissions trouver un point de chute parfait pour un champ donné, c'est-à-dire une meilleure façon de diminuer sa valeur. Ensuite, pour trouver le nombre minimum de bombes à larguer, un premier projet d'algorithme pourrait être (le code est copié-collé à partir d'une implémentation 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

Le défi est choose_a_perfect_drop_point. Tout d'abord, définissons ce qu'est un point de chute parfait.

• Un point de chute pour (x, y)diminue la valeur de (x, y). Il peut également diminuer les valeurs dans d'autres cellules.
• Un point de chute a pour (x, y)vaut mieux qu'un point de goutte b pour (x, y)s'il diminue les valeurs dans un sur-ensemble correct des cellules que b diminue.
• Un point de goutte est maximal s'il n'y a pas d'autre meilleur point de goutte.
• Deux points de chute pour (x, y)sont équivalents s'ils diminuent le même ensemble de cellules.
• Un point de chute pour (x, y)est parfait s'il est équivalent à tous les points de chute maximaux pour (x, y).

S'il existe un point de largage parfait pour (x, y), vous ne pouvez pas diminuer la valeur de manière (x, y)plus efficace que de larguer une bombe sur l'un des points de largage parfaits pour (x, y).

Un point de chute parfait pour un champ donné est un point de chute parfait pour n'importe laquelle de ses cellules.

Voici quelques exemples:

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

Le point de chute parfait pour la cellule (0, 0)(indice de base zéro) est (1, 1). Tous les autres points de chute pour (1, 1), c'est-à (0, 0)- (0, 1)dire et (1, 0)diminuent moins de cellules.

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 point de chute idéal pour la cellule (2, 2)(indice de base zéro) est (2, 2), ainsi que toutes les cellules environnantes (1, 1), (1, 2), (1, 3), (2, 1), (2, 3), (3, 1), (3, 2)et (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 point de chute parfait pour la cellule (2, 2)est (3, 1): il diminue la valeur en (2, 2)et la valeur en (4, 0). Tous les autres points de chute pour (2, 2)ne sont pas maximaux, car ils diminuent d'une cellule de moins. Le point de goutte parfait pour (2, 2)est également le point de goutte parfait pour (4, 0), et c'est le seul point de goutte parfait pour le champ. Il conduit à la solution parfaite pour ce domaine (une goutte de bombe).

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

Il n'y a pas de point de chute parfait pour (2, 2): les deux (1, 1)et la (1, 3)diminution (2, 2)et une autre cellule (ce sont des points de chute maximaux pour (2, 2)), mais ils ne sont pas équivalents. Cependant, (1, 1)est un point de chute parfait pour (0, 0), et (1, 3)est un point de chute parfait pour (0, 4).

Avec cette définition de points de chute parfaits et un certain ordre de vérifications, j'obtiens le résultat suivant pour l'exemple de la question:

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

Cependant, l'algorithme ne fonctionne que s'il y a au moins un point de chute parfait après chaque étape. Il est possible de construire des exemples où il n'y a pas de points de chute parfaits:

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

Pour ces cas, nous pouvons modifier l'algorithme de sorte qu'au lieu d'un point de chute parfait, nous choisissions une coordonnée avec un choix minimal de points de chute maximaux, puis calculons le minimum pour chaque choix. Dans le cas ci-dessus, toutes les cellules avec des valeurs ont deux points de chute maximaux. Par exemple, (0, 1)a les points de chute maximaux (1, 1)et (1, 2). Choisir l'un ou l'autre, puis calculer le minimum conduit à ce résultat:

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

Voici une autre idée:

Commençons par attribuer un poids à chaque case du plateau pour savoir combien de numéros seraient réduits en y déposant une bombe. Donc, si l'espace a un nombre non nul, il obtient un point, et si tout espace adjacent à lui a un nombre non nul, il obtient un point supplémentaire. Donc, s'il y a une grille de 1000 par 1000, nous avons un poids attribué à chacun des 1 million d'espaces.

Triez ensuite la liste des espaces en fonction de leur poids et bombardez celle qui a le poids le plus élevé. C'est le plus pour notre argent, pour ainsi dire.

Après cela, mettez à jour le poids de chaque espace dont le poids est affecté par la bombe. Ce sera l'espace que vous avez bombardé, et tout espace immédiatement adjacent à lui, et tout espace immédiatement adjacent à ceux-ci. En d'autres termes, tout espace qui aurait pu voir sa valeur réduite à zéro par le bombardement, ou la valeur d'un espace voisin réduite à zéro.

Ensuite, triez à nouveau les espaces de liste en fonction de leur poids. Étant donné que seul un petit sous-ensemble d'espaces a vu son poids modifié par le bombardement, vous n'aurez pas besoin de recentrer toute la liste, il suffit de déplacer ceux-ci dans la liste.

Bombardez le nouvel espace de poids le plus élevé et répétez la procédure.

Cela garantit que chaque bombardement réduit autant d'espaces que possible (en gros, il frappe le moins d'espaces qui sont déjà zéro comme possible), donc ce serait optimal, sauf que leurs poids peuvent être liés. Vous devrez donc peut-être effectuer un suivi arrière lorsqu'il y a une cravate pour le poids supérieur. Cependant, seule une cravate pour le poids supérieur importe, pas d'autres cravates, donc j'espère que ce n'est pas trop de recul.

Edit: le contre-exemple de Mysticial ci-dessous montre qu'en fait, ce n'est pas garanti d'être optimal, indépendamment des liens de poids. Dans certains cas, réduire le poids autant que possible à une étape donnée laisse en fait les bombes restantes trop dispersées pour atteindre une réduction cumulative aussi élevée après la deuxième étape que vous pourriez avoir avec un choix légèrement moins gourmand à la première étape. J'ai été quelque peu trompé par l'idée que les résultats sont insensibles à l'ordre des bombardements. Ils sont insensible à l'ordre dans la mesure où vous pouvez prendre n'importe quelle série de bombardements et les rejouer depuis le début dans un ordre différent et vous retrouver avec le même tableau résultant. Mais il ne s'ensuit pas que vous pouvez considérer chaque bombardement indépendamment. Ou, au moins, chaque bombardement doit être considéré d'une manière qui tient compte de la façon dont il prépare le plateau pour les bombardements ultérieurs.

Eh bien, supposons que nous numérotions les positions du tableau 1, 2, ..., nx m. Toute séquence de largage de bombes peut être représentée par une séquence de nombres dans cet ensemble, où les nombres peuvent se répéter. Cependant, l'effet sur le plateau est le même quel que soit l'ordre dans lequel vous déposez les bombes, donc tout choix de largage de bombes peut être représenté comme une liste de nombres nxm, où le premier nombre représente le nombre de bombes larguées en position 1 , le deuxième nombre représente le nombre de bombes larguées en position 2, etc. Appelons cette liste de nxm la "clé".

Vous pouvez d'abord essayer de calculer tous les états de carte résultant d'une goutte de bombe, puis les utiliser pour calculer tous les états de carte résultant de 2 gouttes de bombe, etc. jusqu'à ce que vous obteniez tous les zéros. Mais à chaque étape, vous mettriez en cache les états à l'aide de la clé que j'ai définie ci-dessus, vous pouvez donc utiliser ces résultats dans le calcul de l'étape suivante (une approche de "programmation dynamique").

Mais en fonction de la taille de n, m et des nombres dans la grille, les besoins en mémoire de cette approche peuvent être excessifs. Vous pouvez jeter tous les résultats pour N bombes une fois que vous avez calculé tous les résultats pour N + 1, il y a donc des économies. Et bien sûr, vous ne pourriez rien mettre en cache au prix de le faire prendre beaucoup plus de temps - l'approche de programmation dynamique échange la mémoire contre la vitesse.

Si vous voulez la solution optimale absolue pour nettoyer la carte, vous devrez utiliser le backtracking classique, mais si la matrice est très grande, il faudra du temps pour trouver la meilleure solution, si vous voulez une solution optimale "possible", vous pouvez utiliser un algorithme gourmand , si vous avez besoin d'aide pour écrire l'algorithme, je peux vous aider

Venez à penser que c'est la meilleure façon. Faites une autre matrice là où vous stockez les points que vous supprimez en y déposant une bombe puis choisissez la cellule avec le maximum de points et déposez la bombe là-bas mettez à jour la matrice des points et continuez. Exemple:

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

valeur de cellule +1 pour chaque cellule adjacente avec une valeur supérieure à 0

Force brute !

Je sais que ce n'est pas efficace, mais même si vous trouvez un algorithme plus rapide, vous pouvez toujours tester ce résultat pour savoir à quel point il est précis.

Utilisez une récursivité, comme ceci:

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

}

Vous pouvez rendre cela plus efficace en mettant en cache, si une manière différente conduit au même résultat, vous ne devez pas répéter les mêmes étapes.

Élaborer:

si le bombardement de la cellule 1,3,5 aboutit au même résultat que le bombardement de la cellule 5,3,1, alors, vous ne devriez pas recommencer toutes les étapes suivantes dans les deux cas, 1 seul suffit, vous devez tout stocker quelque part table des états et utilisez ses résultats.

Un hachage de statistiques de table peut être utilisé pour effectuer une comparaison rapide.

1. Ne bombardez jamais la frontière (à moins que le carré n'ait pas de voisin non frontalier)
2. Coin zéro.
3. Pour zéro coin, déposez la valeur du coin à une case en diagonale (le seul voisin non frontalier)
4. Cela créera de nouveaux coins. Aller à 2

Edit: je n'ai pas remarqué que Kostek a suggéré presque la même approche, alors maintenant je fais une affirmation plus forte: si les coins à effacer sont choisis pour être toujours sur la couche la plus externe, alors c'est optimal.

Dans l'exemple d'OP: laisser tomber 2 (comme 1 + 1 ou 2) sur autre chose que sur 5 ne conduit pas à frapper une case que tomber sur 5 frapperait. Il faut donc simplement laisser tomber 2 sur 5 (et 6 en bas à gauche 1 ...)

Après cela, il n'y a qu'un seul moyen de nettoyer le coin (en haut à gauche) de ce qui était à l'origine 1 (maintenant 0), et c'est de supprimer 0 sur B3 (exceler comme la notation). Etc.

Ce n'est qu'après avoir effacé des colonnes A et E entières et 1 et 7 lignes, commencer à effacer une couche plus profondément.

Considérez effacé uniquement ceux effacés intentionnellement, effacer les coins de valeur 0 ne coûte rien et simplifie la réflexion.

Parce que toutes les bombes larguées de cette façon doivent être larguées et que cela conduit à des champs dégagés, c'est la solution optimale.

Après un bon sommeil, j'ai réalisé que ce n'était pas vrai. Considérer

  ABCDE    
1 01000
2 10000
3 00000
4 00000

Mon approche laisserait tomber des bombes sur B3 et C2, alors que tomber sur B2 serait suffisant

Voici ma solution. Je ne l'écrirai pas encore dans le code car je n'ai pas le temps, mais je pense que cela devrait produire un nombre optimal de mouvements à chaque fois - bien que je ne sois pas sûr de son efficacité à trouver les points à bombarder.

Tout d'abord, comme @Luka Rahne l'a déclaré dans l'un des commentaires, l'ordre dans lequel vous bombardez n'est pas important, seulement la combinaison.

Deuxièmement, comme beaucoup d'autres l'ont déclaré, bombarder 1-off la diagonale des coins est optimal car il touche plus de points que les coins.

Cela génère la base de ma version de l'algorithme: nous pouvons bombarder le `` 1-off from the corners '' en premier ou en dernier, cela n'a pas d'importance (en théorie) Nous bombardons ces premiers parce que cela rend les décisions ultérieures plus faciles (en pratique) Nous bombardons le point qui affecte le plus de points, tout en bombardant simultanément ces coins.

Définissons les points de résistance comme étant les points du plateau avec le plus de points non bombardables + le plus grand nombre de 0 autour d'eux

les points non bombardables peuvent être définis comme des points qui n'existent pas dans la portée actuelle du tableau que nous examinons.

Je définirai également 4 bornes qui géreront notre portée: Haut = 0, Gauche = 0, Bas = k, droite = j. (valeurs pour commencer)

Enfin, je définirai les bombes optimales comme des bombes larguées sur des points adjacents à des points de résistance et touchant (1) le point de résistance le plus élevé et (2) le plus grand nombre de points possible.

En ce qui concerne l'approche, il est évident que nous travaillons de l'extérieur vers l'intérieur. Nous pourrons travailler avec 4 «bombardiers» en même temps.

Les premiers points de résistance sont évidemment nos coins. Les points «hors limites» ne sont pas bombardables (il y a 5 points en dehors de la portée pour chaque coin). Nous bombardons donc les points en diagonale un des coins en premier.

Algorithme:

1. Trouvez les 4 points de bombe optimaux.
2. Si un point de bombe bombarde un point de résistance qui touche 2 limites (c'est-à-dire un coin), bombardez jusqu'à ce point est 0. Sinon, bombardez chacun jusqu'à ce que l'un des points de résistance touchant le point de bombe optimal soit 0.
3. pour chaque borne: if (sum (borne) == 0) avance borne

répéter jusqu'à ce que TOP = BOTTOM et LEFT = RIGHT

Je vais essayer d'écrire le code réel plus tard

Vous pouvez utiliser la planification de l'espace d'état. Par exemple, en utilisant A * (ou l'une de ses variantes) couplé à une heuristique f = g + hcomme celle-ci:

• g: nombre de bombes larguées jusqu'à présent
• h: somme de toutes les valeurs de la grille divisée par 9 (ce qui est le meilleur résultat, ce qui signifie que nous avons une heuristique admissible)

J'ai aussi eu 28 coups. J'ai utilisé deux tests pour le meilleur coup suivant: d'abord le coup produisant la somme minimale pour le plateau. Deuxièmement, pour des sommes égales, le mouvement produisant la densité maximale, définie comme:

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

Voici Haskell. "résoudre la carte" montre la solution du moteur. Vous pouvez jouer au jeu en tapant «principal», puis entrez un point cible, «meilleur» pour une recommandation ou «quitter» pour quitter.

SORTIE:
* Principal> tableau de résolution
[(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)

Il semble y avoir une sous-structure correspondante non bipartite ici. Prenons l'exemple suivant:

0010000
1000100
0000001
1000000
0000001
1000100
0010000

La solution optimale à ce cas a la taille 5 car c'est la taille d'une couverture minimale des sommets d'un cycle 9 par ses bords.

Ce cas, en particulier, montre que la relaxation de programmation linéaire que quelques personnes ont postée n'est pas exacte, ne fonctionne pas, et toutes ces autres mauvaises choses. Je suis presque sûr que je peux réduire "couvrir les sommets de mon graphique cubique planaire par le moins d'arêtes possible" à votre problème, ce qui me fait douter que l'une des solutions gourmandes / d'escalade va fonctionner.

Je ne vois pas de moyen de résoudre ce problème en temps polynomial dans le pire des cas. Il pourrait y avoir une solution de recherche binaire et de DP très intelligente que je ne vois pas.

EDIT : Je vois que le concours ( http://deadline24.pl ) est indépendant de la langue; ils vous envoient un tas de fichiers d'entrée et vous leur envoyez des sorties. Vous n'avez donc pas besoin de quelque chose qui s'exécute dans le pire des temps polynomiaux. En particulier, vous pouvez regarder l'entrée !

Il y a un tas de petits cas dans l'entrée. Ensuite, il y a un boîtier 10x1000, un boîtier 100x100 et un boîtier 1000x1000. Les trois grands cas sont tous très bien comportés. Les entrées adjacentes horizontalement ont généralement la même valeur. Sur une machine relativement costaud, je suis en mesure de résoudre tous les cas en forçant brutalement à l'aide de CPLEX en seulement quelques minutes. J'ai eu de la chance sur le 1000x1000; la relaxation LP se trouve avoir une solution optimale intégrale. Mes solutions sont en accord avec les .ansfichiers fournis dans le bundle de données de test.

Je parie que vous pouvez utiliser la structure de l'entrée d'une manière beaucoup plus directe que moi si vous y jetiez un coup d'œil; semble que vous pouvez simplement couper la première ligne, ou deux ou trois à plusieurs reprises jusqu'à ce que vous n'ayez plus rien. (On dirait que dans le 1000x1000, toutes les lignes ne sont pas en augmentation? Je suppose que c'est de là que vient votre "partie B"?)

Je ne peux pas penser à un moyen de calculer le nombre réel sans simplement calculer la campagne de bombardement en utilisant ma meilleure heuristique et j'espère obtenir un résultat raisonnable.

Donc, ma méthode consiste à calculer une métrique d'efficacité de bombardement pour chaque cellule, bombarder la cellule avec la valeur la plus élevée, .... itérer le processus jusqu'à ce que j'ai tout aplati. Certains ont préconisé d'utiliser des dommages potentiels simples (c.-à-d. Un score de 0 à 9) comme métrique, mais cela échoue en pilant les cellules de grande valeur et en ne faisant pas usage du chevauchement des dommages. Je calculerais cell value - sum of all neighbouring cells, redéfinirais tout positif à 0 et utiliserais la valeur absolue de tout négatif. Intuitivement, cette métrique devrait faire une sélection qui aide à maximiser le chevauchement des dommages sur les cellules avec un nombre élevé au lieu de les piler directement.

Le code ci-dessous atteint la destruction totale du champ de test dans 28 bombes (notez que l'utilisation de dommages potentiels comme métrique donne 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();
    }           
  }
}

Le schéma de bombardement résultant est émis comme suit (valeurs de champ à gauche, métrique à droite)

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

Cela peut être résolu en utilisant un arbre de profondeur O (3 ^ (n)). Où n est la somme de tous les carrés.

Considérez d'abord qu'il est trivial de résoudre le problème avec un arbre de O (9 ^ n), considérez simplement tous les emplacements de bombardement possibles. Pour un exemple, voir la mise en œuvre d'Alfe .

Réalisez ensuite que nous pouvons travailler pour bombarder de bas en haut tout en obtenant un schéma de bombardement minimum.

1. Commencez par le coin inférieur gauche.
2. Bombardez-le à l'oubli avec les seuls jeux qui ont du sens (en haut et à droite).
3. Déplacez un carré vers la droite.
4. Alors que la cible a une valeur supérieure à zéro, considérez chacun des 2 jeux qui ont du sens (directement vers le haut ou vers la droite), réduisez la valeur de la cible d'une unité et créez une nouvelle branche pour chaque possibilité.
5. Déplacez un autre vers la droite.
6. Alors que la cible a une valeur supérieure à zéro, considérez chacun des 3 jeux qui ont du sens (en haut à gauche, en haut et à droite), réduisez la valeur de la cible d'une unité et créez une nouvelle branche pour chaque possibilité.
7. Répétez les étapes 5 et 6 jusqu'à ce que la ligne soit supprimée.
8. Montez une rangée et répétez les étapes 1 à 7 jusqu'à ce que le puzzle soit résolu.

Cet algorithme est correct car

1. Il est nécessaire de compléter chaque ligne à un moment donné.
2. Terminer une ligne nécessite toujours un jeu soit au-dessus, soit en dessous, soit à l'intérieur de cette ligne.
3. Il est toujours aussi bon ou préférable de choisir un jeu au-dessus de la ligne non effacée la plus basse qu'un jeu sur la ligne ou en dessous de la ligne.

En pratique, cet algorithme fera régulièrement mieux que son maximum théorique car il bombardera régulièrement les voisins et réduira la taille de la recherche. Si nous supposons que chaque bombardement diminue la valeur de 4 cibles supplémentaires, alors notre algorithme fonctionnera en O (3 ^ (n / 4)) ou approximativement O (1,3 ^ n).

Cet algorithme étant toujours exponentiel, il serait judicieux de limiter la profondeur de la recherche. Nous pourrions limiter le nombre de branches autorisées à un certain nombre, X, et une fois que nous sommes aussi profonds, nous forcons l'algorithme à choisir le meilleur chemin qu'il a identifié jusqu'à présent (celui qui a la somme totale minimale de carte dans l'une de ses feuilles terminales ). Ensuite, notre algorithme est garanti pour fonctionner en temps O (3 ^ X), mais il n'est pas garanti d'obtenir la bonne réponse. Cependant, nous pouvons toujours augmenter X et tester empiriquement si le compromis entre un calcul accru et de meilleures réponses en vaut la peine.

fonction d'évaluation, somme totale:

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

fonction objectif:

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

fonction de destruction:

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

fonction objectif:

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

fonction de maximisation linéaire:

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

Ce n'est pas optimal, mais peut être optimisé en trouvant une meilleure fonction d'évaluation.

.. mais en pensant à ce problème, je pensais que l'un des principaux problèmes était d'obtenir des chiffres abandonnés au milieu des zéros à un moment donné, alors je prendrais une autre approche .. qui est de dominer les valeurs minimales en zéro, puis d'essayer de échapper autant que possible aux zéros, ce qui conduit à une minimisation générale de la ou des valeurs minimales existantes

Tout ce problème se résume à calculer une distance d'édition. Calculez simplement une variante de la distance de Levenshtein entre la matrice donnée et la matrice zéro, où les modifications sont remplacées par des bombardements, en utilisant une programmation dynamique pour stocker les distances entre les tableaux intermédiaires. Je suggère d'utiliser un hachage des matrices comme clé. 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

C'était une réponse à la première question posée. Je n'avais pas remarqué qu'il avait changé les paramètres.

Créez une liste de toutes les cibles. Attribuez une valeur à la cible en fonction du nombre de valeurs positives impactées par une baisse (elle-même et tous les voisins). La valeur la plus élevée serait un neuf.

Triez les cibles par le nombre de cibles impactées (Décroissant), avec un tri décroissant secondaire sur la somme de chaque cible impactée.

Lâchez une bombe sur la cible la mieux classée, puis recalculez les cibles et répétez jusqu'à ce que toutes les valeurs cibles soient nulles.

D'accord, ce n'est pas toujours le plus optimal. Par exemple,

100011
011100
011100
011100
000000
100011

Cette approche nécessiterait 5 bombes à éliminer. De manière optimale, cependant, vous pourriez le faire en 4. Pourtant, sacrément proche et il n'y a pas de retour en arrière. Pour la plupart des situations, il sera optimal ou très proche.

En utilisant les numéros de problème d'origine, cette approche résout 28 bombes.

Ajout de code pour illustrer cette approche (en utilisant un formulaire avec un bouton):

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

                    }
                }
            }
        }

    }

Un cours dont vous aurez besoin:

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