Bonjour,
Je n'ai pas vu tous les codes, mais il me semble que certains d'entre eux parcourent toute la carte à chaque itération (complexité en $O(nm)$, pour $n$ arbres brûlés en $m$ étapes). Algorithmiquement, on peut faire beaucoup mieux pour un peu de mémoire en plus (simulation en $O(n)$, c'est un peu ce que j'ai fait dans mon premier code en python, mais sans donner d'explications), et voici comment :
Remarquons tout d'abord que seuls les arbres qui brûlent à l'étape $i$ ont un impact à l'étape $i+1$. Par ailleurs, un arbre brûle en une seule étape. Il suffit donc de conserver une liste des arbres qui brûlent (le front de feu si vous voulez) pour réaliser la simulation. Une structure de type FIFO est donc tout indiquée ici.
S'il est souhaitable de réaliser l'affichage pas à pas, il faut encore ruser un peu afin de distinguer les différentes étapes, mais l'idée reste la même.
Démonstration en C (percolation de lien, 1024x1024 arbres, p = 0.55, approx. 10 simulations par seconde sur mon i3) :
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75 | #include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define WIDTH 1024
#define HEIGHT 1024
#define SZ (WIDTH * HEIGHT)
#define PROBA 0.55
enum {NONE=0, TREE=1, BURN=2, ASHE=3} State;
static char mat[SZ];
static int queue[SZ];
size_t I, J;
float random() {
return (float) rand() / RAND_MAX;
}
void step()
{
const size_t k = J;
while (I < k)
{
const int i = queue[I++];
mat[i] = ASHE;
if (i > 0 && mat[i-1] == TREE && random() < PROBA)
{
queue[J++] = i-1;
mat[i-1] = BURN;
}
if (i < SZ && mat[i+1] == TREE && random() < PROBA)
{
queue[J++] = i+1;
mat[i+1] = BURN;
}
if (i >= WIDTH && mat[i-WIDTH] == TREE && random() < PROBA)
{
queue[J++] = i-WIDTH;
mat[i-WIDTH] = BURN;
}
if (i + WIDTH < SZ && mat[i+WIDTH] == TREE && random() < PROBA)
{
queue[J++] = i+WIDTH;
mat[i+WIDTH] = BURN;
}
}
}
void init() {
memset(mat, TREE, SZ);
I = 0, J = 0;
const int k = rand() % SZ;
mat[k] = BURN;
queue[J++] = k;
}
int main()
{
srand(time(NULL));
for (int i=1; i<=10; ++i) {
init();
size_t steps;
for(steps=0; I < J; steps++) {
step();
}
printf("%d) %d sur %d arbres brules, en %u etapes\n", i, J, SZ, steps);
}
return 0;
}
|
je m y attele et peut on le faire en 3D?
.
Le programme affiche enfin le pourcentage de survivants.
