Hybridation de la programmation par contraintes et d'un voisinage à très grande taille pour Eternity II

Résumé : Eternity II est un puzzle avec compatibilité entre côtés des pièces créé par Christopher Monkton pour l'éditeur de jeu Tomy (TM). Étant donné 256 pièces carrées dont chaque côté est colorié et un tableau de 16*16, le but est de placer toutes les pièces sur le plateau de sorte que deux pièces adjacentes ont leur côté commun de même couleur. Ce problème est NP-complet, il possède très peu de structure et est fortement combinatoire (256! .4256 combinaisons possibles). Christopher Monkton est tellement confient du fait de la difficulté de trouver une solution à son problème qu'il promet un prix de $2 millions à la première personne qui trouvera une solution. Nous n'avons (désormais) plus grand espoir de trouver une solution à ce problème, mais nous avons néanmoins décidé d'expliquer notre stratégie pouvant être utile à quelqu'un croyant toujours en ses chances de succès. Notre procédure consiste en une initialisation par programmation par contrainte en relâchant le problème. Ensuite, nous améliorons la solution avec une recherche locale stochastique utilisant un voisinage de très grande taille. Notre voisinage est de très grande taille (exponentielle) mais peut néanmoins être exploré en temps polynomial en solutionnant un problème d'appariement avec poids dans un graphe biparti. Notre procédure nous permet d'obtenir rapidement de bonnes solutions avec des scores jusqu'à 458/480 jonctions satisfaites. Notre grand voisinage peut également être utilisé dans une approche bruteforce pour tester 256!/128! . 4128 combinaisons au lieu de 256! . 4256. Cette article est également un exemple de VLNS (Very Large Neighborhood Search) pouvant être appliqué à d'autres types de problèmes de placement avec compatibilité entre les objets.
Type de document :
Communication dans un congrès
Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.115-122, 2008
Liste complète des métadonnées

Littérature citée [8 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00291137
Contributeur : Service Ist Inria Sophia Antipolis-Méditerranée / I3s <>
Soumis le : jeudi 26 juin 2008 - 17:44:51
Dernière modification le : jeudi 10 juillet 2008 - 16:47:39
Document(s) archivé(s) le : vendredi 28 mai 2010 - 22:53:52

Fichier

pages-115-122-article31.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : inria-00291137, version 1

Collections

Citation

Pierre Schauss, Yves Deville. Hybridation de la programmation par contraintes et d'un voisinage à très grande taille pour Eternity II. Gilles Trombettoni. JFPC 2008- Quatrièmes Journées Francophones de Programmation par Contraintes, Jun 2008, Nantes, France. pp.115-122, 2008. 〈inria-00291137〉

Partager

Métriques

Consultations de la notice

100

Téléchargements de fichiers

137