Comment puis-je optimiser ma solution de force brute à ce problème ?

Aug 17 2020

Je travaille sur une solution au problème expliqué ci-dessous. J'utilise la force brute, j'ai atteint le point où les solutions sont prohibitives, j'ai donc besoin d'optimiser davantage (si possible). Bien sûr, ce sera encore mieux s'il existe une meilleure façon de résoudre le problème (pas la force brute).

Y a-t-il quelque chose que je puisse faire pour améliorer ma solution, ou une référence que je peux examiner (problèmes similaires, etc.) ?

Le problème

Nous commençons avec une planche rectangulaire. Chaque cellule peut être dans N états, et l'état initial de chaque cellule est aléatoire (0 <= état < N) pour chaque cellule. Nous avons également un certain nombre de formes, toutes adaptées à l'intérieur de la planche. Chaque forme est continue.

Chaque forme doit être placée une (et une seule) dans le plateau. Lorsqu'une forme est placée, chaque cellule qui appartient à la forme verra sa valeur augmentée de 1. Si la valeur du tableau dans une cellule atteint N, elle est remplacée par 0.

Le but est de trouver les positions où chaque forme doit être placée pour que le tableau final ait toutes les cellules avec la valeur 0. Il y a toujours au moins une solution. Supposons que le problème soit généré en partant du tableau fini et en appliquant des formes aléatoires dans des positions aléatoires.

La taille du plateau, le nombre d'états N et le nombre de formes sont la configuration du jeu et continuent d'augmenter (à des rythmes différents) pour chaque «niveau».

Ce que je fais actuellement

Je suis capable de résoudre le problème jusqu'à une certaine taille en utilisant simplement la force brute. J'ai quelques optimisations en place. J'ai atteint un point où la solution est prohibitive, alors j'aimerais améliorer ma logique.

La première chose que je fais est de commander la forme du plus grand au plus petit, le plus petit sera déplacé dans les itérations internes. L'hypothèse (que je n'ai pas prouvée, mais testée pour être plus rapide) est qu'il est préférable de déplacer davantage les formes plus petites, car elles ont plus de chances de générer une solution.

Deuxièmement, pour les formes répétées, j'évite de vérifier toutes les permutations, car elles donnent le même résultat. Je ne vérifie également qu'un seul ensemble de positions lorsqu'une paire de mêmes formes se chevauchent (puisque tous les chevauchements donnent le même résultat).

Une dernière optimisation qui, je pense, aidera beaucoup, mais que je suis toujours en train d'implémenter est la suivante : à chaque forme de la séquence, comptez le nombre total de cellules dans les formes qui restent à déplacer. Ce nombre, moins le nombre total de retournements de cellules nécessaires pour obtenir une carte finie, doit être un multiple de N. Sinon, il est inutile de forcer brutalement les positions de formes restantes, et nous devons repositionner une forme dans une boucle externe.

Détails supplémentaires

Je suis intéressé par d'autres conseils sur la façon d'optimiser cela. Des algorithmes connus, même une bonne dénomination pour cet ensemble de problèmes, que je peux utiliser pour rechercher davantage seraient formidables.

Réponses

2 D.W. Aug 18 2020 at 15:50

Programmation linéaire en entier

Votre problème peut être formulé de la manière suivante : on nous donne des vecteurs$v_{i,j} \in (\mathbb{Z}/N\mathbb{Z})^d$, où le conseil a$d$cellules, et le but est, étant donné un vecteur$c \in (\mathbb{Z}/N\mathbb{Z})^d$, trouver une fonction$f$pour que$\sum_i v_{i,f(j)}=c$. Ce problème pourrait alors être résolu par la programmation linéaire en nombres entiers. Ceci est lié à une$d$-problème de somme de sous-ensembles dimensionnels, vous pourrez donc également trouver d'autres algorithmes pour la somme de sous-ensembles multidimensionnels et les essayer également.

Comment le formule-t-on ainsi ? Si la grille a$d$cellules, nous pouvons considérer une forme comme un$d$-vecteur de 0 et de 1, avec des 1 dans les cellules couvertes par la forme. Chaque forme peut être placée dans un certain nombre de positions différentes, produisant différents vecteurs.$v_{i,j}$correspond à la$j$ème endroit où la forme$i$Peut être placé.$c$correspond aux nombres à l'origine dans la grille (enfin, la négation de ces nombres, modulo$N$). Tout le calcul est fait modulo$N$.

Force brute légèrement plus intelligente

Alternativement, voici un moyen d'améliorer un peu la force brute, en échangeant de la mémoire contre du temps. Supposons que vous ayez$k$formes. Commencez par énumérer toutes les façons de placer le premier$k/2$formes sur un tableau vide de tous les zéros et stockez toutes les positions résultantes dans une table de hachage ou une liste triée. Ensuite, énumérez toutes les façons de placer le dernier$k/2$formes sur la position de départ et recherchez chacune des positions résultantes dans la table de hachage ou la liste triée. Si vous trouvez une correspondance, cela donne une solution. Cela vous permettra de pousser la force brute un peu plus loin - potentiellement jusqu'à environ deux fois plus de formes - si vous disposez d'une quantité de mémoire illimitée. Il y a beaucoup de détails impliqués dans l'optimisation au maximum, mais c'est une idée que vous pourriez envisager si votre force brute vous rapproche mais tombe un peu court. Il s'agit toujours d'un algorithme à temps exponentiel, il atteindra donc toujours une limite.