Dott a dit le 13 mai 2008
J’aurai aimé savoir si le remplissage en diagonale ne serait pas plus judicieux, la promiscuité me semblant plus élevée.
Choix du chemin optimisé pour un backtracking d’Eternity II
Vous êtes ici : Accueil / Articles / Formations en Algorithmique
Les enjeux du choix du chemin
Même en implémentant les contraintes, il existe trop de combinaisons possibles pour que l’ordinateur puisse toutes les tester en un temps raisonnable. Il est donc nécessaire d’avoir recours aux probabilités.
En situation d’équiprobabilité, moins le nombre de possibilités est grand, plus la probabilité de tomber sur un élément est grande. Cette approche intuitive est formalisée par l’assertion suivante :
Plus les contraintes sont restrictives, plus le nombre de possibilités va être restreint, donc plus la probabilité de trouver la solution est grande.
Comme le nombre de combinaisons est trop grand, l’ordinateur ne reviendra probablement pas jusqu’aux premières pièces. Il est donc essentiel de se diriger dès le départ vers la ou une des bonnes branches, et cela grâce aux probabilités. Nous devons donc placer les pièces possédant le plus de contraintes en premier.
Le complexe contraintes/proximité
L’algorithme de backtracking présente cependant des limites : lorsqu’il s’aperçoit qu’une des pièces qu’il a posé antérieurement est invalide, il devra faire le chemin inverse pour la modifier. Le problème est que le temps pris en fonction de la distance des pièces n’est pas linéaire, mais dérivé de la factorielle :
étant le temps mis pour tester toutes les possibilités de n positions, et $k_n+1 étant le nombre de pièces à tester pour la n+1ième position.
Il est donc important que l’on teste le plus rapidement possible la validité des pièces pour éviter d’avoir à reparcourir un chemin trop long, or la validité des pièces se fait par la correspondance des motifs, donc par le test des pièces voisines. Ainsi, pour une optimisation de l’algorithme, il est nécessaire que si une pièce est incertaine, alors la position suivante à tester soit une pièce voisine.
Prenons un exemple pour être plus parlant : si nous commençons par positionner les 4 coins, puis nous commençons à remplir du haut vers le bas. En arrivant en bas, l’algorithme s’aperçoit que le coin en bas n’est pas le bon. Il lui faut tout remonter pour revenir à cette pièce, effectuant ainsi des milliards de tests inutiles.
La proximité des pièces n’est importante que si la pièce posée est incertaine. Elle ne s’applique donc pas à la pièce fixe. Ainsi, la seconde pièce posée pourra être en tout point du plateau.
Une fois la pièce fixe posée, nous en revenons à la première considération qui consiste à se demander quelle est la seconde position qui a le plus de contraintes. Nous voyons tout de suite que les coins sont les secondes positions ayant le plus de contraintes, car elles n’ont chacune que 4 pièces possibles. Une fois un coin posé, celui-ci étant incertain, l’obligation de proximité entre en jeu et oblige à poser une pièce parmi celles qui entoure le coin.
Ensuite, les contraintes que nous allons voir correspondent à un couple de 2 motifs. Prenons un exemple : si nous posons en seconde position le coin en haut à gauche, les positions voisines sont (2,1) et (1,2). Dans les 2 cas, des contraintes sur les motifs en haut et à gauche s’imposent. Ensuite, pour garder cette double contrainte, nous allons être obligés de longer les bords, puis revenir suivant le mouvement d’un serpent.
Est-il nécessaire de poser la pièce fixe en premier ?
Imaginons que nous ne posons pas la pièce fixe en premier. Nous commençons par un coin, suivons le mouvement d’un serpent. Au bout d’un certain nombre de pièces, nous arriverons à la position de la pièce fixe. Les règles d’eternity imposant la pièce 139 à cette position, il est nécessaire de rajouter une condition dans la fonction de backtracking pour forcer l’utilisation de la pièce imposée.
Les problèmes d’optimisation se font voir à 2 niveaux : une condition est testée très rapidement par un ordinateur, mais une condition effectuée des milliards de fois a un impact au niveau du temps global d’exécution de l’algorithme.
Le second problème d’optimisation se situe lors du choix de la pièce se positionnant au-dessus de la pièce fixe. Il est clair que celle-ci devrait avoir 3 contraintes : le motif supérieur, le motif à gauche ou à droite suivant le sens du mouvement, et le motif inférieur qui correspond au motif supérieur de la pièce fixe. Si la pièce fixe n’est pas déjà posée, cette troisième contrainte ne sera pas prise en compte, donc trop de pièces seront considérées comme valables et de nombreux tests inutiles seront effectués.
Revient-il au même de suivre un chemin en escargot autour de la pièce fixe ?
Appliquons les principes énoncés plus hauts : une fois posé la pièce fixe, comme celle-ci n’est pas incertaine, la règle de la proximité de s’applique pas. Nous avons donc totalement le choix quand au positionnement. En revanche, d’après la règle des contraintes les plus fortes en priorité, nous devons placer la seconde pièce au lieu où les contraintes seront les plus grandes. Quel que soit la position autour de la pièce fixe, la seule contrainte sera 1 motif de celle-ci. Les seuls endroits où les contraintes sont les plus fortes sont les coins, car ils appliquent des contraintes sur 2 motifs. Il est donc nécessaire de choisir un coin comme 2e position pour optimiser l’algorithme, or ensuite, la loi de proximité s’applique, donc le chemin en escargot n’est pas optimisé. Choisir le chemin en escargot est donc une erreur d’optimisation.
Conclusion
En conclusion, voici le chemin le plus optimisé pour l’algorithme de backtracking de résolution d’eternity II est le suivant :
Commentaires
Ludovic PATEY a dit le 13 mai 2008
Au niveau des contraintes de motifs, le remplissage en diagonale est identique.
La question de la promiscuité en diagonale est une bonne question : La promiscuité sera en effet meilleure au niveau du coin de départ et de celui d’arrivée. En revanche, elle aura tendance à décroître en se rapprochant de la diagonale et deviendra alors inférieure à la méthode de l’escargot. La moyenne de promiscuité sera exactement la même d’un point de vue global.
Ainsi, pour voir quel algorithme sera le plus optimisé, il faut se demander à quel niveau est effectué le plus grand nombre de tests : au centre où aux extrémités.
jean-françois a dit le 10 juillet 2008
bonjour,
voila j’ai acheter se jeux je ne suis pas ingenieur je n’est meme pas fini mes etude donc sans diplome et aime se genre de jeux de strategi mes je ne comprend pas bien le but quand il parle de carrée de 16 X 16 donc avec les symbole on doit faire un carrée de 16 piece sur 16 esque vous ariez une image montrent se que veut 16 X 16 ?
mon email : diabolo2003@ibelgique.com
jesper que quelqun poura m’edai a avoir une idée du jeux que je poséde.
merçi d’avance a tous.
Ludovic PATEY a dit le 12 juillet 2008
Bonjour,
Un carré 16 x 16 signifie qu’il faut former avec les pièces un grand carré de 16 lignes et 16 colonnes, donc utilisant 256 pièces.
La contrainte est de faire correspondre les motifs entre 2 pièces juxtaposées. Les règles du jeu sont disponibles à l’adresse suivante :
http://fr.eternityii.com/regles-du-jeu/
Guillaume a dit le 23 juillet 2008
http://puzzles.ao.free.Fr !!!
Guyom38 a dit le 30 août 2008
Le probleme que je constate a chaque fois dans les algos pour Eternity2, c’est qu’il n’y a pas de controle sur les possibilités antérieures...
J’explique, du moins je tente ... Le serpent fait son chemin, aller, puis retour ligne du dessous, puis aller ligne suivante, et ainsi de suite. Une pièce est mise, ses possibilités voisines analysées, et si blocage on recule d’un pas et on teste autre chose... La question est : Quand est il si une pièce necessaire 4 pas avant, et utilisée ? L’algo s’en rendra compte qu’une fois la ligne suivante, sur la position a probleme ?
oooooooooo
oooxooooo0
ooo ?
plus de solution, car la seule pièce possible a été utilisé pour "O".
Vous comprenez ?
Du coup, il faut s’en arret tester les possibilités necessaires, un controle trés lourds, mais qui au final fait gagner des milliards de milliards de mouvements pour rien ...
Ludovic PATEY a dit le 30 août 2008
Bonjour Guyom38,
Avec votre exemple, vous mettez en relief une limitation de l’algorithme de backtracking et prônez ainsi implicitement l’utilisation d’un algorithme de backjumping :
http://en.wikipedia.org/wiki/Backjumping
Bien que très utile dans de nombreuses situations, le backjumping ne semble pas le plus adapté à la situation d’eternity. En effet, prenons votre exemple : la seule pièce possible à la place de l’interrogation est le 0. Vous en concluez qu’il faut revenir jusqu’au 0, le substituer par une autre pièce et mettre le 0 à la place de l’interrogation, ce qui n’est pas forcément nécessaire : si vous disposez de plusieurs pièces au choix pour la pièce précédant l’interrogation, vous pouvez placer une autre pièce, et ainsi ne plus vous retrouver avec les mêmes contraintes de motifs. Il y aura alors peut-être une pièce libre qui pourra se placer. Ainsi, il faut tester toutes les combinaisons avant de revenir à la pièce 0.
Avez-vous compris mes explications ?
Guyom38 a dit le 31 août 2008
"Vous en concluez qu’il faut revenir jusqu’au 0", non pas forcement, j’en sais rien quelle piece mettre, je dis plutot :
On étudie l’ensemble des possibilités sur toutes la zone.
les contours 56pieces, les bords 4pieces... ensuite, on place une piece, et on étudies les possibilités des pieces voisines, sachant que plus on avance, plus le chiffre chute sur les possibilités du plateau... ainsi si une des possibilités est a 0, on sait que cela ne sert a rien de continuer, car plutard, on sera stoppé par cette absence...
1° ) Analyse, indexage, et comptage des pièces possibles sur les zones utilisables.
2° ) Algo, je place, ou je retire ...
Est ce plus clair ?
Je pense que je mettais pas assez expliqué. On regarde bien plus loin, et si ca bloque on reviens mainteannt. On ne se contente pas de regarder uniquement les pieces voisines de celle en cours.
xx.xx.xx.xx.xx.xx.xx... -> xx pieces placees
xx.xx.xx.xx.xx.xx.xx... ->
xx.xx.xx.04.12.00.05... -> 04 ... 12 ... 00... 05 nombre de pieces possibles a cet endroit
15.13.11.—.--.—.--... -> 00 plus haut est apparu une lors du dernier mouvement, et non avant
45.—.--.—.--.—.--... -> 45 nombre de pieces de bord disponibles
Voila en gros le schema, on controle tout le temps, la disponibilité, car il serait dommage de continuer alors que quelques part il n’y a plus de pièces dispos.
J’espère que c’est plus clair.
Guyom38@free.Fr
Ludovic PATEY a dit le 31 août 2008
Merci pour vos précisions. Je comprends mieux votre intervention. Il faut maintenant se poser la question suivante : est-ce que le gain de temps occasionné par un blocage plus à la racine compense l’excédent de temps mis à effectuer les tests en plus ?
En effet, sans les tests, nous n’irons pas plus loin que 30 cases après la case posant problème, et sachant que l’algorithme de backtracking n’essaye que des pièces correspondant aux contraintes et n’essaye pas les pièces déjà placées, il n’y aura pas beaucoup de combinaisons testées sur ces 30 cases. Le gain de temps ne sera donc pas énorme. En outre, les tests supplémentaires étant effectués à chaque position, le rapport entre le nombre de fois où ils seront utiles et le nombre de fois ils seront exécutés est trop petit pour que cela en vaille la peine.
Cordialement,
Ludovic PATEY
Guyom38 a dit le 1er septembre 2008
Effectivement sur une resolution en "serpent" cela ne vaut pas le coup, par contre sur une resolution en escargot, (contour, puis contour -1, puis contour -2, ...) ou (centre, centre+1, centre+2...) l’utilisation d’un tel dispositif est incontournable, du moins pour moi ...
Guyom38 a dit le 1er septembre 2008
Je rajouterai que 30cases meme en "serpent" peu représenter du chemin ! du temps ? et donc ... !
Ludovic PATEY a dit le 1er septembre 2008
Effectivement, pour une résolution en escargot, cette vérification supplémentaire est nécessaire. J’ai personnellement été confronté au problème avec des bloquages prenant beaucoup de temps car il fallait refaire tout en sens inverse. Cependant, plus on se rapproche du centre, moins cela est nécessaire. Une solution optimisée consisterait donc à l’appliquer jusqu’à une certaine distance des bords.
les BEP a dit le 26 décembre 2008
vou cassé pas trop , on a trouvé la soluce ...alor que la plupart d’entre nous n’a rien compris a votre dialecte !!!
tchao les nazes ............
Ludovic PATEY a dit le 27 décembre 2008
Bonjour,
Vous prétendez avoir trouvé la solution, félicitations. Cependant, étant donné les performances des machines actuelles, la probabilité de trouver est tellement faible qu’il n’y a que 2 types de personnes capables de trouver la solution : les génies mathématiques et les extraordinaires chanceux. Le premier cas ne semble pas vous concerner car vous ne semblez même pas comprendre le français. Le second cas vous concernerait donc, mais alors, il n’y a pas lieu de tirer fierté du résultat car cela relève de la chance.