Patrick Perea - Paul Mariage
Le but de ce devoir est d'étudier les déplacements d'une puce dans un labyrinthe. Nous allons mettre un place un labyrinthe de taille m x n avec l'entrée en position [n,1] , et la sortie en position [1,m]. Commençons par écrire les fonctions afin de définir le labyrinthe :
set.seed(2)
# Fonction de génération du labyrinthe Paramètres : m : nombre de ligne n :
# nombre de colonne p : probabilité return : un labyrinthe correcte
Generer_Lab <- function(m, n, p) {
repeat {
lab = matrix(data = 0, nrow = m, ncol = n)
copie = lab
for (i in 1:m) {
for (j in 1:n) {
rand = runif(1, min = 0, max = 1)
if (rand <= p)
(lab[i, j] = 1)
}
}
copie = Est_acceptable(lab, copie, 1, n)
if (copie[m, 1] == 1) {
break
}
}
lab[1, m] = 2
lab[n, 1] = 3
return(lab)
}
# Fonction de validation d'un labyrinthe Paramètres : lab : un labyrinthe
# mat : une matrice posx : la position en x posy : la position en y return :
# un labyrinthe correcte
Est_acceptable <- function(lab, mat, posx, posy) {
m <- nrow(lab)
n <- ncol(lab)
mat[posx, posy] <- 1
MatSuiv = matrix(data = 0, m, n)
for (i in 1:m) {
for (j in 1:n) {
MatSuiv[i, j] = mat[i, j]
}
}
if (posx < n) {
if (mat[posx + 1, posy] != 1 & lab[posx + 1, posy] != 1) {
MatSuiv = Est_acceptable(lab, MatSuiv, posx + 1, posy)
}
}
if (posx > 1) {
if (mat[posx - 1, posy] != 1 & lab[posx - 1, posy] != 1) {
MatSuiv = Est_acceptable(lab, MatSuiv, posx - 1, posy)
}
}
if (posy < m) {
if (mat[posx, posy + 1] != 1 & lab[posx, posy + 1] != 1) {
MatSuiv = Est_acceptable(lab, MatSuiv, posx, posy + 1)
}
}
if (posy > 1) {
if (mat[posx, posy - 1] != 1 & lab[posx, posy - 1] != 1) {
MatSuiv = Est_acceptable(lab, MatSuiv, posx, posy - 1)
}
}
MatSuiv
}
lab = Generer_Lab(5, 5, 0.5)
print(lab)
## [,1] [,2] [,3] [,4] [,5]
## [1,] 0 1 1 1 2
## [2,] 1 1 1 1 0
## [3,] 0 1 0 1 0
## [4,] 0 1 0 0 0
## [5,] 3 0 0 1 0
On a donc ici un exemple de labyrinthe valide, c'est à dire qui dispose d'un terrain acceptable, tel qu'il existe un chemin entre A et B.
Nous allons maintenant simuler le déplacement d'une puce dans le labyrinthe grâce à l'algorithme suivant :
# Fonction de mouvement de la puce Paramètres : lab : un labyrinthe m :
# nombre de ligne n : nombre de colonne i : la position en x j : la position
# en y return : la position de la puce
bouger_puce <- function(lab, m, n, i, j) {
maliste = c()
value = 0
if (j - 1 > 0) {
if (lab[i, j - 1] != 1) {
maliste = c(maliste, c(i, j - 1))
}
}
if (i + 1 <= n) {
if (lab[i + 1, j] != 1) {
maliste = c(maliste, c(i + 1, j))
}
}
if (j + 1 <= m) {
if (lab[i, j + 1] != 1) {
maliste = c(maliste, c(i, j + 1))
}
}
if (i - 1 > 0) {
if (lab[i - 1, j] != 1) {
maliste = c(maliste, c(i - 1, j))
}
}
nbelem = length(maliste)/2
mavaleur = floor(runif(1, min = 0, max = 1) * nbelem)
if (mavaleur == 0) {
return(c(maliste[1], maliste[2]))
}
if (mavaleur == 1) {
return(c(maliste[3], maliste[4]))
}
if (mavaleur == 2) {
return(c(maliste[5], maliste[6]))
}
if (mavaleur == 3) {
return(c(maliste[7], maliste[8]))
}
}
On va donc tester si cette fonction marche correctement de la façon suivante : nous allons positionner notre puce à l'entrée du labyrinthe, et elle est censé arrivé à la sortie du labyrinthe.
pospuce = c(5, 1)
while (!identical(pospuce, c(1, 5))) {
pospuce = bouger_puce(lab, 5, 5, pospuce[1], pospuce[2])
}
print(pospuce)
## [1] 1 5
On voit donc bien que la puce est arrivé à la sortie grâce à notre algorithme.
Passons maintenant à l'étude expérimentale. Nous allons donc fixer le p à 0, c'est à dire que nous n'avons aucun mur dans notre labyrinthe. Nous allons faire varier la taille de notre matrice et voir quel est le temps moyen d'atteinte de B en partant de A. Nous allons donc faire varier n et m de 5 à 25, récupérer le temps moyen d'atteinte de B partant de A et répéter cette expérience 20 fois afin d'avoir une idée précise sur ce temps moyen.
moyenne = c()
n = 5
m = 5
for (j in 1:20) {
duree = 0
compteur = 0
for (i in 1:20) {
ptm = Sys.time()
lab = Generer_Lab(m, n, 0)
pos = c(n, 1)
while (!identical(pos, c(1, m))) {
pos = bouger_puce(lab, m, n, pos[1], pos[2])
}
temps <- Sys.time() - ptm
duree = duree + temps
m = m + 1
n = n + 1
compteur = compteur + 1
}
m = 5
n = 5
moyenne = c(moyenne, c(duree/compteur))
compteur = 0
}
moyenne <- as.numeric(moyenne)
Nous allons maintenant observer le vecteur moyenne afin d'en apprendre un peu plus sur l'expérience réalisée.
print(summary(moyenne))
## Min. 1st Qu. Median Mean 3rd Qu. Max.
## 0.553 0.568 0.575 0.579 0.595 0.640
On peut voir grâce au summary le temps moyen d'atteinte de B en partant de A. Cependant cela n'est pas suffisant pour déterminer la distribution. Nous pourrons alors l'observer grâce à l'histogramme:
hist(moyenne, breaks = 20)
On peut ainsi observer graphiquement que la distribution se situe autour de la moyenne, et elle n'est pas uniforme.
Passons maintenant à l'étude d'un cas particulier, ou m = n = 10 et pour p = 0. Nous allons maintenant voir la distribution du temps d'atteinte de B partant de A grâce au code suivant :
moyen = c()
m = 10
n = 10
lab = Generer_Lab(m, n, 0)
for (j in 1:50) {
pos = c(n, 1)
ptm = Sys.time()
while (!identical(pos, c(1, m))) {
pos = bouger_puce(lab, m, n, pos[1], pos[2])
}
temps <- Sys.time() - ptm
moyen = c(moyen, c(temps))
}
hist(moyen, breaks = 10)
Cet histogramme nous montre bien que le temps d'atteinte de B à A est le plus souvent très faible, entre 0 et 0.02 secondes, mais il est possible que ce temps augmente selon la complexité de la matrice, c'est à dire si la puce doit rebrousser chemin dans certains cas.
Nous allons maintenant nous intéresser à l'impact de p sur le temps d'atteinte de B partant de A. Pour cela, nous allons faire varier p de 0.05 en 0.05 et recueillir à chaque fois le temps d'attente de B en partant de A.
impactP = data.frame()
p = c()
temps = c()
i = 0
while (i <= 0.85) {
pos = c(5, 1)
moyenne = 0
p = c(p, c(i))
for (j in 1:10) {
pos = c(5, 1)
lab = Generer_Lab(5, 5, i)
ptm = Sys.time()
while (!identical(pos, c(1, 5))) {
pos = bouger_puce(lab, 5, 5, pos[1], pos[2])
}
ptm <- Sys.time() - ptm
moyenne = moyenne + ptm
}
moyenne = moyenne/10
temps <- c(temps, c(moyenne))
i = i + 0.05
moyenne = 0
}
impactP = cbind(p, temps)
plot(impactP)
On peut noter grâce à ce graphique que le temps d'atteinte de B en partant de A est plus important pour certaines valeurs de p. Cependant,les valeurs restent très petites. Cela parait cohérent. En effet, la valeur de P a un impact sur la structure du labyrinthe, c'est à dire le temps pour trouver un labyrinthe valable. Ainsi, pour certaines valeurs de p, le labyrinthe va offrir beaucoup de possibilités à la puce. D'où le résultat indiqué par le graphique.
Note : nous n'avons pas prix en compte les valeurs de p entre 0.9 et 1, car le temps de génération d'une matrice acceptable est très très grand (et impossible pour p = 1)
Pourtant, un doute s'installe quant à la cohérence de ce résultat. En effet, on peut considérer que le temps d'atteinte est très faible car la machine sur laquelle nous travaillons est très performante. Nous allons essayer une nouvelle approche pour l'impact de P en étudiant non pas le temps d'atteinte de B en partant de A mais plutôt le nombre de déplacement à effectuer pour rejoindre B.
impactP = data.frame()
p = c()
nbdep = c()
i = 0
while (i <= 0.85) {
compteurdeptotal = 0
compteurdep = 0
pos = c(5, 1)
p = c(p, c(i))
for (j in 1:20) {
compteurdep = 0
pos = c(5, 1)
lab = Generer_Lab(5, 5, i)
while (!identical(pos, c(1, 5))) {
pos = bouger_puce(lab, 5, 5, pos[1], pos[2])
compteurdep = compteurdep + 1
}
compteurdeptotal = compteurdeptotal + compteurdep
}
nbdep <- c(nbdep, c(compteurdeptotal/20))
i = i + 0.05
}
impactP = cbind(p, nbdep)
plot(impactP)
Notre doute est confirmé, le résultat est différent de celui donné par l'histogramme précédent, mais certaines valeurs de p se démarquent en donnant un nombre de déplacement plus important que les autres