Découvrir | Logiciels & programmation | Liens Web | Propriétés remarquables | Recherche automatisée | Documentation | Zoo |
Cet algorithme consiste à parcourir itérativement toutes les configurations satisfaisant les règles du jeu de la vie et des contraintes fixées par l'utilisateur.
L'algorithme procède de la façon suivante : On cherche une structure de période T s'inscrivant dans un rectangle de dimensions données.
Au départ, l'état de toutes les cases
est inconnu pour tous les instant de 0 à T.
Ensuite le programme cherche une case inconnue et
tente de choisir un état pour celle-ci.
Parfois, tel ou tel choix sur une case peut forcer une autre case (voisine, descendante ou ancêtre) à prendre un état donné, dans ce cas le programme met les cases concernées dans l'état nécessaire (c'est un choix forcé) puis examine les conséquences de ces nouveaux choix.
Lorsqu'on a aboutit a un état cohérent,
le programme cherche une autre case inconnue et réitère le
processus.
Ce type d'algorithme peut aussi très simplement être adapté pour rechercher des antécédents à une structure donnée. Il faut placer la structure dont on recherche des antécédents dans le rectangle correspondant à la période T et ne pas imposer de contraintes quand à la périodicité de la structure.
Il est possible d'utiliser un programme réalisé sur ce modèle selon deux approches :
Ce type de recherche n'est viable que pour des surfaces
et des périodes de recherche petites.
En effet augmenter la zone de recherche, outre le
fait que le coût est rapidement plus élevé amène
de plus, à retrouver des résultats concernant des zones plus
petites qui y sont incluses.
De plus plus on augmente la période plus on
augmente le temps mis par le programme pour détecter les contradictions
entre la première génération et la génération
T.
En effet dans sa recherche systématique le programme parcourt plusieurs fois des structures semblables (par exemple translatées) ou encore des structures inintéressantes (du point de vue de celui qui recherche).
En obligeant le programme à revenir en arrière sur des choix qu'il juge inintéressants, l'utilisateur peut arriver plus rapidement à obtenir des structures intéressantes satisfaisant les conditions qu'il a posées.
Dans un rectangle de n*m cases, il y a précisément 2^(n*m) structures différentes. Pour une recherche donnée il y a donc au maximum 2^(n*m) structures à essayer. Évidement seulement une petite partie d'entre elles satisfait réellement les conditions posées donc plus le programme détecte rapidement les contradictions moins de temps il va perdre sur des structures non-satisfaisantes.
En fait une contradiction due à un choix sur une case donnée est détectée d'autant plus tôt que le programme repasse au voisinage de cette case. La façon dont le programme choisit une case dont l'état est inconnue plutôt qu'une autre est donc déterminante.
Pour accélérer la recherche il faut donc soit guider le programme à la main, soit implémenter une routine chargée de faire des choix "judicieux" ; une quantité d'ordres de parcourt peu être imaginée...
J'en ai moi-même réalisé une
implémentation, en Turbo Pascal.
Elle manque de finition mais je pense qu'elle doit
être à peu près compréhensible. N'hésitez
pas à me poser des questions, me proposer des modifications,
me rapporter des bugs...