Recherche de formes dans un tableau 2D, puis optimisation

Je viens de recevoir une image ... L'image ci-dessous de mon jeu montre des blocs sombres, qui ont été reconnus comme faisant partie d'une forme en "T". Comme on peut le voir, le code a assombri les blocs avec les taches rouges, et pas vu les formes en "T" avec les contours verts.

Mon code parcourt x / y, marque les blocs comme utilisés, fait pivoter la forme, se répète, change de couleur, se répète.

J'ai commencé à essayer de corriger cette vérification avec une grande appréhension. L'idée actuelle est de:

• faire une boucle à travers la grille et noter toutes les occurrences de motif (NE PAS marquer les blocs comme utilisés), et les mettre dans un tableau
• boucle à nouveau à travers la grille, cette fois en notant quels blocs sont occupés par quels modèles, et donc qui sont occupés par plusieurs modèles.
• boucle à nouveau à travers la grille, cette fois en notant quels modèles entravent quels modèles

Cela me semble bien ... Que dois-je faire maintenant?

Je pense que je devrais

• essayez différentes combinaisons de formes conflictuelles, en commençant par celles qui obstruent le plus les autres motifs en premier. Comment aborder celui-ci?
• utilisez le rationnel qui dit que j'ai 3 formes conflictuelles occupant 8 blocs, et les formes sont 4 blocs chacune, donc je ne peux avoir qu'un maximum de deux formes.

(J'ai également l'intention d'incorporer d'autres formes, et il y aura probablement une pondération du score qui devra être prise en compte lors du passage des formes en conflit, mais cela peut être un autre jour)

Je ne pense pas que ce soit un problème d'emballage de bacs, mais je ne sais pas quoi rechercher. J'espère que cela a du sens, merci pour votre aide

EDIT Malgré la clarté de la question, tout le monde semble avoir compris, oui,

Je veux trouver le maximum de formes en "T" dans chaque couleur

(parce que si je vous donnais des points pour deux et que vous en aviez fait trois, vous seriez un peu ennuyé)

Voyons si j'ai bien compris, les blocs marqués en rouge étaient bleus et l'algorithme a trouvé une forme en T et les a marqués en rouge, est-ce correct? Votre objectif est de trouver autant de formes en T que possible avec les mêmes blocs de couleur, corrigez jusqu'à présent j'espère. Actuellement, vous les marquez une fois que vous les avez trouvées et cela diminue l'utilité de l'algorithme (car vous pourriez manquer la solution optimale). Vous prévoyez de rechercher toutes les formes, puis de choisir celles à utiliser et celle à ne pas utiliser. Suis-je correct jusqu'à présent? Parce que vous souhaitez maximiser la quantité de blocs contenus dans les formes T lorsque l'algorithme est terminé.

Si je me trompe, ce qui suit est à mon avis la solution optimale pour votre situation.

Nous utiliserons la programmation linéaire entière.

Je crois que j'ai utilisé celui-ci dans le passé:

http://sourceforge.net/projects/lpsolve/

http://lpsolve.sourceforge.net/5.5/Java/README.html

(Vous pouvez le faire fonctionner avec de nombreux langages, je l'ai utilisé avec PHP, Java et C)

Ce que nous ferons, c'est d'enregistrer toutes les formes de T possibles sur la carte, puis d'utiliser l'ILP pour maximiser la quantité de blocs qui sont couverts. ILP est exponentiellement complexe. Compte tenu de la taille de votre planche, ce ne sera pas un problème. J'ai posé des questions min / max beaucoup plus compliquées sur les graphiques avec ILP et cela n'a pris qu'une fraction de seconde pour terminer et jusqu'à 30-90 secondes avec des centaines de sommets (dans votre cas, cela tombe en une fraction de seconde).

Ce que je recommanderais de faire:

1. Trouver toutes les formes de ligne possibles
2. Trouver toutes les intersections entre les formes de lignes de la même couleur
3. Trouvez toutes les formes de T possibles, en recherchant toutes les intersections.
4. Définissez une variable booléenne dans le problème linéaire pour chaque forme en T ( 0 <= Bi <= 1) Puisque les valeurs sont des entiers, cela laisse 0 ou 1.
5. Créez les conditions pour chaque couple de formes en T qui se croisent ( Bi + Bj <= 1)
6. La fonction objectif sera (somme des blocs en forme de "T" (i) * Bi)
7. Exécutez le solveur et assombrissez les formes en T où les booléens correspondants du solveur où 1 dans la solution optimale.

Ce sont des connaissances précieuses, j'ai souvent utilisé des solveurs linéaires pour des projets de travail.

ILP est fondamentalement un moyen de résoudre des problèmes de sélection où vous voulez atteindre un maximum ou un minimum pour une fonction linéaire.

Vous pouvez en savoir plus ici, en utilisant la programmation linéaire Integer et la programmation linéaire est la même pour le programmeur seulement que Integer est beaucoup plus complexe pour l'ordinateur, ce qui peut entraîner de longs temps de fonctionnement. Pas dans votre cas, c'est très simple et ne devrait prendre que moins de millisecondes dans le pire des cas.

Je suppose que vous pouvez en lire plus ici:

http://en.wikipedia.org/wiki/Integer_linear_programming#Integer_unknowns

Cela l'explique bien:

http://fisher.osu.edu/~croxton_4/tutorial/

C'est essentiellement un résolveur de problèmes de décision, comment prendre des décisions qui maximisent le résultat souhaité. Cela suppose que la fonction qui juge le résultat est linéaire, ce qui est le cas dans votre cas actuel. La fonction qui juge le résultat dans ce cas, résume les blocs pour toutes les formes en T que vous avez décidé d'assombrir.

Mathématiquement, comment définir les variables: dans notre cas actuel, les booléens (ai-je assombri la forme en T avec l'indice i ou non) aux valeurs optimales pour maximiser le résultat que nous voulons: assombrir autant de blocs que possible sans assombrir les formes en T entrecroisées. Tant que le résultat souhaité peut être calculé avec une fonction linéaire lorsque toutes les variables sont définies, il le résoudra. Dans notre cas, nous vérifions quelles formes en T nous avons assombries et additionnons les blocs qu'elles couvrent.

Je sais que ce n'est pas anodin, donc si vous choisissez de faire le saut, n'hésitez pas à commenter et je développerai.

Une fois que vous avez une liste de toutes les formes en T (qui peuvent se chevaucher) se produisant dans votre grille, ce qui vous reste est un problème d' emballage maximum défini .

En général, il s'agit d'un problème NP-complet. Cependant, votre grille est suffisamment petite (et se décompose généralement en sous-problèmes indépendants encore plus petits) qu'il peut être possible d'obtenir des solutions exactes.

Addendum: Voici un algorithme de recherche de retour en arrière de base qui pourrait faire l'affaire:

function max_packing_recursive ( set A, set S, set M ):
    if |M| < |S| then let M = S;
    for each shape X in A do:
        remove X from A;
        let B = A;
        remove all shapes that intersect with X from B;
        if |M| < |B| + |S| + 1 then:        // upper bound
            let M = max_packing_recursive( B, S + {X}, M );
        end if
        if |M| >= |A| + |S| then return M;  // shortcut
    end for
    return M;
end function

function max_packing( set A ):
    return max_packing_recursive( A, {}, {} );
end function

Ici, {X, Y, Z}dénote l'ensemble contenant les éléments X, Yet Z(avec {}étant l'ensemble vide), et |Q|dénote la taille de l'ensemble Q.

Dans la fonction récursive, l'ensemble Acontient les formes disponibles pour la solution restante, Scontient les formes dans le candidat de solution actuel et Mest jusqu'à présent la solution maximale (que vous souhaiterez peut-être stocker en tant que variable globale au lieu de la renvoyer chaîne d'appel). L'optimisation importante est sur la ligne marquée par // upper bound, qui élague les branches de l'arbre de recherche qui ne peuvent pas renvoyer une meilleure solution que M.

(En fait, comme nous savons que chaque forme en T contient exactement quatre sites, une limite supérieure bien meilleure pourrait être obtenue en remplaçant |B|par le nombre de sites distincts couverts par les formes dans B, divisé par quatre et arrondi (et de même pour |A|le ligne marquée avec // shortcut). L'algorithme comme indiqué ci-dessus, cependant, fonctionne pour les collections arbitraires de formes.)

Une optimisation supplémentaire possible, que je n'ai pas implémentée ci-dessus, serait de vérifier au début de la fonction récursive si les Adivisions en plusieurs sous-ensembles indépendants, dans le sens où aucune forme dans différents sous-ensembles ne se chevauchent, et si c'est le cas, appliquez le algorithme à chacun des sous-ensembles séparément. (Dans tous les cas, vous voudrez certainement le faire au moins une fois au niveau supérieur avant d' appeler l'algorithme récursif.) Trier les formes de Amanière appropriée avant de les boucler, par exemple en augmentant l'ordre par le nombre de formes qui se chevauchent, pourrait également aider .