J'ai dû arrêter à seulement une solution partielle à ce problème depuis que j'ai été hors du temps, mais nous espérons encore cette solution partielle fournit quelques indications sur une approche possible pour résoudre ce problème.
Lorsqu'ils sont confrontés à un problème difficile, je tiens à venir avec le plus simple des problèmes pour développer une intuition sur le problème de l'espace. Ici, la première étape j'ai pris était de réduire ce 2-D problème dans un 1-D de problème. Considérons une droite:
0 4 2 1 3 0 1
D'une manière ou d'une autre, vous savez que vous aurez besoin de la bombe à ou près de l' 4 spot 4 fois à le faire descendre à 0. Depuis la gauche de la tache est un nombre inférieur, il n'y a aucun avantage à les bombardements de l' 0 ou 4 sur le bombardement de l' 2. En fait, je crois (mais il leur manque une preuve rigoureuse) que le bombardement de l' 2 jusqu'à ce que l' 4 spot descend à 0 est au moins aussi bonne qu'une autre stratégie pour obtenir que l' 4 jusqu'à 0. On peut continuer vers le bas de la ligne de la gauche vers la droite dans une stratégie comme ceci:
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 couple de l'échantillon bombardement de commandes:
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 départ avec un nombre qui doit aller vers le bas d'une manière ou d'une autre est un attrayant, car il devient tout à coup accessible pour trouver une solution qui, comme certains le prétendent d'ê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 sur le bord de la carte. Il est clair pour moi qu'il n'y a aucune stricte des prestations à la bombe contre le bord externe; vous êtes mieux de bombardement de la place d'en obtenir trois autres espaces de libre. Compte tenu de cela, nous pouvons dire que le bombardement de l'anneau à l'intérieur de la bordure est au moins aussi bon que le bombardement du bord. En outre, on peut combiner cela avec l'intuition que le bombardement de la droite à l'intérieur de la bordure est en fait la seule façon d'obtenir de bord espaces à 0. Même plus, il est carrément simple pour déterminer la stratégie optimale (en ce qu'elle est au moins aussi bonne que n'importe quelle autre stratégie) pour obtenir l'angle des nombres jusqu'à 0. Nous avons mis tous ensemble et que vous pouvez obtenir beaucoup plus près d'une solution dans la 2-D de l'espace.
Compte tenu de l'observation au sujet de pièces de coin, nous pouvons dire que nous savons que la stratégie optimale pour passer d'une planche de départ à un conseil d'administration avec des zéros sur tous les angles. Ceci est un exemple de ce type de conseil (j'ai emprunté les numéros à partir du linéaire de deux planches 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 du haut vraiment ressemble étroitement linéaires exemple que nous avons vu plus tôt. En rappelant que notre observation précédente selon laquelle la meilleure façon d'obtenir la rangée supérieure à 0 est de la bombe de la deuxième rangée (de l' x de la rangée). Il n'existe aucun moyen pour effacer la ligne d'en haut par les bombardements tout de l' y lignes et aucun avantage supplémentaire de bombardement de la ligne du haut, au cours de bombardements de l'espace correspondant sur l' x ligne.
On pourrait appliquer le linéaire de la stratégie à partir de ci-dessus (à bombarder les espaces correspondants sur l' x rangée), au sujet de nous-mêmes seulement avec le haut de la ligne et rien d'autre. Ce serait 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
Le défaut de cette approche est particulièrement évidente dans les deux derniers attentats à la bombe. Il est clair, étant donné que la seule bombe de sites qui permettent de réduire l' 4 figure dans la première colonne de la deuxième ligne sont le premier x et de la y. Les deux derniers attentats à la bombe sont nettement inférieures à juste bombardements de la première x, ce qui aurait fait exactement la même (en ce qui concerne la première place dans la rangée du haut, que nous n'avons pas d'autre moyen de compensation). Depuis, nous avons démontré que notre stratégie actuelle n'est pas optimale, une modification de la stratégie est clairement nécessaire.
À ce stade, je peux prendre un pas en arrière vers le bas dans la complexité et de se concentrer seulement un 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 des 4 vers le bas à zéro sont à la bombe contre une combinaison d' x, y, et z. Avec quelques acrobaties dans mon esprit, je suis assez sûr que la solution optimale est de la bombe x trois fois et ensuite, a alors b. Maintenant c'est une question de comprendre comment je suis arrivé à cette solution et si elle révèle toute l'intuition que nous pouvons utiliser à même de résoudre ce problème local. Je remarque qu'il n'y a pas de bombardements de l' y et z espaces. Essaye de trouver un coin où les bombardements de ces espaces de sens que donne un coin qui ressemble à ceci:
0 4 2 5 0
4 x y a .
2 z . . .
5 b . . .
0 . . . .
Pour cela, il est clair pour moi que la solution optimale est de la bombe y 5 fois et z 5 fois. Nous allons aller un peu 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 façon intuitive que la solution optimale est de la bombe a et b 6 fois et ensuite, x 4 fois.
Maintenant, il devient un jeu de la façon de transformer ces intuitions dans les principes que nous pouvons construire.
Espérons-le, d'être poursuivi!
