Quantité minimale de couleurs empêchant un sous-triangle équilatéral uniformément coloré

13

dans le Bundeswettberweb Infomatik 2010/2011, il y avait un problème intéressant:

Pour fixe , trouver un k minimal et une carte φ : { ( i , j ) | i j n } { 1 , , k } , de sorte qu'il n'y a pas de triple ( i , j ) , ( i + l , j ) , ( i + l , j + l ) avec φ ( inkφ:{(i,j)|ijn}{1,,k}(je,j),(je+l,j),(je+l,j+l) .φ(je,j)=φ(je+l,j)=φ(je+l,j+l)

À savoir, nous recherchons la quantité minimale de couleurs pour un triangle, de sorte qu'il n'y ait pas de sous-triangle équilatéral de couleur uniforme (l'image suivante montre une coloration invalide car les sommets en surbrillance forment un sous-triangle équilatéral de couleur uniforme):

                              Exemple

En fait, ils ont demandé un raisonnablement petit pour n = 1000 et dans la solution (écrite en allemand), ils ont noté qu'une approche gourmande donne une coloration à 27 couleurs pour n = 1000 , qui peut être réduite à 15kn=100027n=100015 en randomisant les couleurs jusqu'à ce qu'un une solution valide est trouvée.

Je m'intéresse aux solutions exactes (pour les petits ). La solution dit que le retour arrière donne 2 couleurs suffisantes pour n { 2 , 3 , 4 } et 3 sont suffisantes pour 5 n 17 , où le retour arrière est déjà très lent pour n = 17n2n{2,3,4}35n17n=17 .

J'ai d'abord essayé d'utiliser une formulation ILP et Gurobi pour obtenir des résultats pour , mais c'était trop lent (déjà pour n = 17 ). Ensuite, j'ai utilisé un solveur SAT , car j'ai remarqué qu'il existe une formulation simple en tant qu'instance SAT.n>17n=17

Avec cette approche, j'ai pu générer une solution avec couleurs pour n = 18 en 10 minutes:3n=18dix

                              Solution avec 3 couleurs pour 18 nœuds

Mais décider si couleurs suffisent pour n = 19 c'est déjà trop lent. Existe-t-il une approche différente qui donne des solutions exactes pour n 19 ? Nous ne pouvons certainement pas nous attendre à un algorithme polynomial.3n=19n19

Référencement
la source
question interessante. pourquoi dites-vous que nous ne pouvons pas nous attendre à un algorithme de temps polynomial?
Sasho Nikolov
@SashoNikolov c'est juste une hypothèse car cela semble être plus difficile que de trouver une coloration de sommet valide (plus difficile en termes de plus de contraintes), et la coloration de sommet est déjà un problème très difficile.
Listing

Réponses:

10

Juste un commentaire étendu:

Vous pouvez jeter un œil à l'approche utilisée par Steinbach et Posthoff pour trouver la quadri -coloration d'une grille 18x18 (et 12x21) sans rectangles monochromes :

Bernd Steinbach et Christian Posthoff, solution de la dernière grille quadrangulaire ouverte sans rectangle, un problème à valeurs multiples extrêmement complexe . Dans les actes du 43e Symposium international IEEE 2013 sur la logique à valeurs multiples (ISMVL '13)

cn×m

Juste une remarque: j'ai passé des semaines de cycles CPU sur le problème de coloration monochrome sans rectangle, mais je suis parti d'un mauvais résultat partiel (une mauvaise analyse précédente qui limitait le nombre de sous-configurations 1 couleur possibles) et j'ai utilisé le solveur de contraintes STP ; vous pouvez obtenir de grandes améliorations si vous ajoutez des contraintes qui cassent les symétries (par exemple un ordre sur la coloration d'un côté du triangle) et essayez de faire une analyse des configurations possibles en utilisant seulement 1 couleur.

EDIT: c'est le résultat d'un programme STP pour n = 19 (~ 1 min.)

entrez la description de l'image ici

Marzio De Biasi
la source
n=19
4

n22n=22n=23n=23n=23

n=19n=23

n=22

tri22-sol

Un grand merci à Marzio pour avoir généré l'image et pour m'avoir informé du problème! :-)

Juho
la source