Algorithmes efficaces pour un automate cellulaire

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 !

Bonjour, :D

Une information complète sur chaque élément de la matrice demande la connaissance
a) de l'état actuel (inactif = 0 , actif = 1) - soit 1 bit;
b) du nombre (n) de voisins actifs, allant de 0 à 4: - soit 1 bit (0 pour n<2, 1 au delà).
Une matrice de doublets de bits devrait donc suffire, et correspondrait à une compression maximale de la variable.
Deux matrices de bits occuperaient le même espace, mais leur utilisation serait plus souple.

Ne disposes-tu pas de fonctions performantes sur les matrices ? La sommation de tous les éléments, par exemple, le produit terme à terme et la comparaison terme à terme (à l'aide des opérateurs XOR et NXOR) devraient s'effectuer rapidement.

Bonjour,

Merci beaucoup pour cette réponse !

J'ai alors deux questions suite à votre message :

1) Donc je devrais plutôt fonctionner sur un matrice de doublets de 0 et 1 si je comprend bien ?
Deux matrices ne serait-il pas plus efficaces, en considérant pour la seconde matrice une matrice à "trous" stockant les bits (j'en ai entendu parlé, mais je sais ne connais pas ce genre de structure de données à vrai dire...) car, lors du passage de l'état T à l'état T+1, on a plus qu'à parcourir les éléments qui sont toujours inactifs ? (on supprime alors les éléments dès lors qu'ils sont actifs ?)

2) Ensuite, deuxième question : pour changer l'état du "bit de voisinage", je vois à peut prêt comment faire ; mais je vois pas comment gérer le stockage sur un seul bit ... Ce que j'imagine faire:
- lorsque j’initialise ma matrice, si je met un 1 pour une case, j'ajoute à tout les voisins +1 sur leur nombre respectif de voisin.
- lorsque j'utilise l'algorithme pour faire la transition, je vais regarder ceux qui ne sont pas actifs et qui ont déjà assez de voisins, je le rend actif et je fais pareil qu'au dessus.
Ce système fonctionne sur 3 entier : 0 si aucun voisin, 1 si un seul voisin, 2 si plus de deux voisins.

Qu'aviez-vous en tête comme système pour effectuer la transition ente un instant T et un instant T+1 ?

(Merci pour ces opérations : c'est vrai que sommer tout les éléments suffit, j'ai juste à vérifier que c'est différent de la matrice pleine de 1, i.e. de n^2)

1) J'ai exprimé les idées comme elles me sont venues, prioritairement préoccupé par la recherche du moindre encombrement.
Deux matrices carrées à éléments booléens, l'une réservée aux états (E), l'autre au voisinages correspondant (V), devraient se prêter à des calculs plus rapides.

La première serait de dimension (N+2), et présenterait sur ses bords (i = 0 ou N+1 , j = 0 ou N+1) des valeurs constamment nulles; l'initialisation (E[i, j] = 0 ou 1) ne concernerait que la partie interne ((1 <= i <= N) et (1 <= j <= N));
La seconde, de dimension (N) seulement, pourrait être initialisée à zéro.
Supprimer les cases actives fait perdre de l'information essentielle concernant la disposition mutuelle des éléments, quel que soit leur état.

2) Le passage de (E) à (V) relève d'instructions classiques (naïves :D); il devrait être cependant plus rapide en procédant comme suit, pour les (N²) éléments intérieurs:
a) Extraction depuis la matrice des états (E) de la sous-matrice carrée (X) d'ordre (3) et de centre (i, j);
b) Produit scalaire généralisé de (X) par une autre matrice (3x3) constante (Y), jouant le rôle de filtre, soit: p = X│Y ;

Code:

---

1 2 3 4

<< 0 , 1 , 0 > y = < 1 , 0 , 1 > < 0 , 1 , 0 >>

---

c) affectation du résultat à l'élément correspondant de (V): si (p>1) alors V[i, j]=1 sinon V[i, j]=0 .
d) détermination des nouvelles valeurs des éléments de (E), restreinte aux éléments non actifs puisque la désactivation est exclue:
Si ((E[i, j]=0) et (V[i, j]=1)) alors E[i, j]=1 .
La variation de la somme des éléments de (E) aux deux instants successifs (S_E(t) , S_E(t+1)) représentera le nombre d'éléments activés.
On doit pouvoir jouer sur la correspondance (False/True , 0/1) pour écrire les instructions les plus simples.

Je ne suis pas suffisamment familier de Python pour fournir des informations plus précises; d'autres pourraient apporter des renseignements plus complets.
Le produit des matrices (3x3) intervient en traitement d'images.

Ces liens pourraient conduire à des informations intéressantes:

# Autres langages/Python & Zope/Calcul scientifique

# Filtres usuels en Traitement d'images

Merci pour votre réponse ! Ça va me servir pour mes concours :)
Je vous tiens au courant quand j'aurais implémenter tout ça !

Bonjour,

il existe une solution plus simple à implémenter que les matrices de calcul et plutôt performante. D'abord il te faut deux grilles d'entiers différentes pour faire les calculs correctement, une pour l'instant t et une pour l'instant t+1. Chaque tour tu intervertis les indices des deux grilles pour qu'elle servent à tour de rôle pour l'instant t. Ensuite tu as besoin d'un tableau qui enregistre le calcul de l'état d'une cellule en fonction du nombre de voisins à 1 et de son état actuel. Enfin tu utilise ce tableau pour faire le calcul suivant pour chaque cellule de la grille :

Code:

---

1 2 3

- additionner les valeurs de tous les voisins à l'instant t - appliquer le tableau de calcul pour obtenir la valeur de la cellule à l'instant t+1

---

Cette façon de faire est facile à implémenter et assez rapide dans ses calculs. Tu peux aussi te servir de tableaux linéaires pour obtenir les indices des voisins. Pour ton algorithme il te faudrait 4 tableaux : voisinDroite[x], voisinGauche[x], voisnHaut[y], voisinBas[y]. Ces tableaux que tu initialises avant de lancer le calcul sur la grille te permettront d'éviter des "if" inutiles et les grilles étendues par une bordure constante. Tu pourras simuler une bordure dynamique en attribuant aux limites des valeurs cohérentes. Par exemple voisinGauche[0] = 0 crée une bordure virtuelle sur le côté gauche dont les valeurs sont identiques aux valeurs des cellules de ta grille à la colonne 0. Un autre exemple, voisinGauche[0] = tailleX - 1 crée une topologie cyclique, c'est à dire que le voisin de gauche de la cellule la plus à gauche est la cellule la plus à droite. Cela donne comme algorithme de calcul pour une cellule (t indique l'indice de la grille à utiliser, tantôt à 0 et tantôt à 1) :

Code:

---

1 2 3

- valeurVoisinage = valeur[t][voisinGauche[x]][y] + valeur[t][voisinDroite[x]][y] + valeur[t][x][voisinHaut[y]] + valeur[t][x][voisinBas[y]] - valeur[1 - t] = tableauCalcul[valeur[t]][valeurVoisinage]

---

J'utilise cet algorithme à peu de choses près sur le logiciel que je développe pour implémenter le jeu de la vie et cela fonctionne très bien.

Pour vérifier si ta grille est remplie, tu peux ajouter une instruction qui fait la somme de toutes les cellules. Si la somme est égale à la taille du tableau c'est que ta grille est remplie. Cela donne au final, pour chaque cellule :

Code:

---

1 2 3 4

- valeurVoisinage = valeur[t][voisinGauche[x]][y] + valeur[t][voisinDroite[x]][y] + valeur[t][x][voisinHaut[y]] + valeur[t][x][voisinBas[y]] - valeur[1 - t] = tableauCalcul[valeur[t]][valeurVoisinage] - somme = somme + valeur[1 - t]

---