Bonjour,
Pour un certain automate cellulaire (bootstrap percolation pour ceux que ça intéresse), j'ai les règles suivantes : (j'appelle "case" tout élément de la matrice, on représente visuellement la matrice comme une grille avec des cases)
- On prend une matrice carrée de taille NxN, et chaque case est égale à 1 avec une probabilité p, 0 sinon. On dit qu'une case est active si le coefficient correspondant de la matrice est égal à 1, inactive sinon.
- Si à un instant T, une case C de la matrice est égale à 0, et si au moins 2 de ses voisins directs (c'est à dire, pas ceux qui sont sur les diagonales) sont actifs, alors C devient active à T+1.
Pour visualiser, cliquez ici
Je dois donc trouver des algorithmes efficaces pour pouvoir faire des simulations d'un grand nombre de ces situations. Je dois donc trouver des algorithmes permettant :
- De vérifier l'égalité entre deux matrices de manière optimale, pour vérifier si ma matrice de taille NxN finie remplie à la fin ou non.
- D'effectuer la transition entre l'état de la matrice de l'instant T à l'instant T+1.
J'ai besoin surtout de calculer le "temps" moyen, i.e. l'entier T du nombre d'étape avant que toute le carré soit rempli, mais ceci pour des matrices de taille 100 par 100 minimum, avec 10 000 calculs environs. J'ai fais pour le moment des algorithmes naïfs, qui consiste à parcourir la matrice, vérifier pour chaque case le nombre de voisin actifs, et ensuite passer à la suivante...
(J'utilise Python ou Caml, si vous avez des astuces pour ces langages je suis preneur).
Je vous remercie par avance !
Partager