n*m est la taille de la matrice n : ligne m : colonne
Pour faire la question 1, on procède de la manière suivante : on prend de manière aléatoire les positions x et y d'une case de la map et on dit que c'est une case du chemin possible. On réitère le processus tant qu'on a pas de chemin entre A et B. Pour savoir si on a un chemin , on part de la case de départ(coordonnée n,1) puis on avance par de case en case jusqu'à atteindre la sortie (coordonnée 1,m). Lorsqu'on se retrouve bloquer (car il n'y a plus de case chemin), on fait demi tour jusqu'à trouver une case chemin qu'on a pas déjà visité. Si à force de reculer on se retrouve sur la case départ et qu'il n'y a plus de case chemin non visité immédiatement adjacente à la case départ, alors c'est qu'il n'existe pas de chemin possible. Il est vrai que le code si dessous peut paraître un peu “barbare” mais il est en réalité un peu simplex c'est juste qu'il y a beaucoup de cas à traiter
Si on a atteind la sortie c'est qu'il existe un chemin admissible. Exemple de construction avec au final 2 chemins possibles : matrice 3x3 221 222 122
puis 211 222 122 puis 211 221 122
puis 211 211 122 puis
211 211 112
—> deux chemins possibles
Fonction qui créer une matrice de taille n,m :
creation_matrice <- function(n, m) {
mat <- matrix(nrow = n, ncol = m)
mat
}
# mat<-creation_matrice(3,3)
Fonction qui initialise la matrice : on met la sortie et l'entrée à 1, le reste à 2 :
init <- function(matrice, n, m) {
# on remplie de 2
for (i in 1:n) {
for (j in 1:m) {
matrice[i, j] = 2
j = j + 1
}
i = i + 1
}
# on test si la matrice existe : on place l'entrée et la sortie
if (is.matrix(matrice)) {
matrice[1, m] = 1
matrice[n, 1] = 1
}
matrice
}
# mat<-init(mat,3,3) mat[2,1]<-1; mat[1,1]<-1;
# k,l position courante
comeback <- function(mat2, k, l, n, m) {
i <- k
j <- l
current <- matrix(nrow = 1, ncol = 2)
if (i + 1 <= n) {
if (mat2[i + 1, j] == 1) {
i <- i + 1
mat2[i, j] <- 2
} else {
if (i - 1 > 0) {
if (mat2[i - 1, j] == 1) {
i <- i - 1
mat2[i, j] <- 2
} else {
if (j - 1 > 0) {
if (mat2[i, j - 1] == 1) {
j <- j - 1
mat2[i, j] <- 2
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
}
} else {
if (j - 1 > 0) {
if (mat2[i, j - 1] == 1) {
j <- j - 1
mat2[i, j] <- 2
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
}
}
} else {
if (i - 1 > 0) {
if (mat2[i - 1, j] == 1) {
i <- i - 1
mat2[i, j] <- 2
} else {
if (j - 1 > 0) {
if (mat2[i, j - 1] == 1) {
j <- j - 1
mat2[i, j] <- 2
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
}
} else {
if (j - 1 > 0) {
if (mat2[i, j - 1] == 1) {
j <- j - 1
mat2[i, j] <- 2
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
} else {
if (j + 1 <= m) {
if (mat2[i, j + 1] == 1) {
j <- j + 1
mat2[i, j] <- 2
}
}
}
}
}
current[1, 1] <- i
current[1, 2] <- j
current
}
trouveChemin <- function(mat, n, m) {
mat2 <- creation_matrice(n, m)
i <- 1
j <- 1
while (i <= n) {
j <- 1
while (j <= m) {
mat2[i, j] <- 0
j <- j + 1
}
i <- i + 1
}
i <- n
j <- 1
test <- 0
while (test == 0) {
if (i == 1) {
if (j == 1) {
if ((mat[i + 1, j] == 1) && (mat2[i + 1, j] == 0)) {
i <- i + 1
if (i != n) {
#on ne dit jamais qu'on est passé sur la case départ sinon pb pour y retouner
mat2[i, j] <- 1
}
} else if ((mat[i, j + 1] == 1) && (mat2[i, j + 1] == 0)) {
j <- j + 1
mat2[i, j] <- 1
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
} else if (j == m) {
print("Sortie trouvée ==>>> chemin existant")
test <- 1
break
} else {
if ((mat[i, j + 1] == 1) && (mat2[i, j + 1] == 0)) {
j <- j + 1
mat2[i, j] <- 1
} else if ((mat[i + 1, j] == 1) && (mat2[i + 1, j] == 0)) {
i <- i + 1
mat2[i, j] <- 1
} else if ((mat[i, j - 1] == 1) && (mat2[i, j - 1] == 0)) {
j <- j - 1
mat2[i, j] <- 1
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
}
} else if (i == n) {
if (j == 1) {
#on est à l'entrée
if ((mat[i - 1, j] == 1) && (mat2[i - 1, j] == 0)) {
i <- i - 1
mat2[i, j] <- 1
} else if ((mat[i, j + 1] == 1) && (mat2[i, j + 1] == 0)) {
j <- j + 1
mat2[i, j] <- 1
} else {
print("il n'y a pas de chemin possible")
test <- 1
break
}
} else if (j == m) {
if ((mat[i - 1, j] == 1) && (mat2[i - 1, j] == 0)) {
i <- i - 1
mat2[i, j] <- 1
} else if ((mat[i, j - 1] == 1) && (mat2[i, j - 1] == 0)) {
j <- j - 1
if (j != 1) {
mat2[i, j] <- 1
}
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
} else {
if ((mat[i - 1, j] == 1) && (mat2[i - 1, j] == 0)) {
i <- i - 1
mat2[i, j] <- 1
} else if ((mat[i, j + 1] == 1) && (mat2[i, j + 1] == 0)) {
j <- j + 1
mat2[i, j] <- 1
} else if ((mat[i, j - 1] == 1) && (mat2[i, j - 1] == 0)) {
if (j != 1) {
j <- j - 1
}
mat2[i, j] <- 1
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
}
} else {
if (j == 1) {
if ((mat[i - 1, j] == 1) && (mat2[i - 1, j] == 0)) {
i <- i - 1
mat2[i, j] <- 1
} else if ((mat[i, j + 1] == 1) && (mat2[i, j + 1] == 0)) {
j <- j + 1
mat2[i, j] <- 1
} else if ((mat[i + 1, j] == 1) && (mat2[i + 1, j] == 0)) {
i <- i + 1
mat2[i, j] <- 1
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
} else if (j == m) {
if ((mat[i - 1, j] == 1) && (mat2[i - 1, j] == 0)) {
i <- i - 1
mat2[i, j] <- 1
} else if ((mat[i, j - 1] == 1) && (mat2[i, j - 1] == 0)) {
j <- j - 1
mat2[i, j] <- 1
} else if ((mat[i + 1, j] == 1) && (mat2[i + 1, j] == 0)) {
i <- i + 1
mat2[i, j] <- 1
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
} else {
if ((mat[i - 1, j] == 1) && (mat2[i - 1, j] == 0)) {
i <- i - 1
mat2[i, j] <- 1
} else if ((mat[i, j + 1] == 1) && (mat[i, j + 1] == 1)) {
j <- j + 1
mat2[i, j] <- 1
} else if ((mat[i + 1, j] == 1) && (mat2[i + 1, j] == 0)) {
i <- i + 1
mat2[i, j] <- 1
} else if ((mat[i, j - 1] == 1) && (mat2[i, j - 1] == 0)) {
j <- j - 1
mat2[i, j] <- 1
} else {
mat2[i, j] <- 2
current = comeback(mat2, i, j, n, m)
i <- current[1, 1]
j <- current[1, 2]
}
}
}
}
if ((i == 1) && (j == m)) {
1
} else {
0
}
}
genere_chemin <- function(n, m, p) {
map <- creation_matrice(n, m)
map <- init(map, n, m)
test <- 0
i <- n
j <- 1
while (test == 0) {
i <- floor(n * runif(n = 1)) + 1
j <- floor(m * runif(n = 1)) + 1
if (map[i, j] != 1) {
map[i, j] <- 1
test <- trouveChemin(map, n, m)
}
}
# on place les obstacles
for (i in 1:n) {
for (j in 1:m) {
if (map[i, j] == 2) {
if (runif(1) < p)
map[i, j] = 0 else map[i, j] = 1
}
j = j + 1
}
i = i + 1
}
map
}
main <- function() {
print("-----------------> QUESTION 1 <-----------------")
n = 3
m = 3
p = 0.5
print("-----------------> MATRICE AVEC CHEMIN UNIFORME <-----------------")
matrice = genere_chemin(n, m, p)
print(matrice)
}
main()
## [1] "-----------------> QUESTION 1 <-----------------"
## [1] "-----------------> MATRICE AVEC CHEMIN UNIFORME <-----------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [,1] [,2] [,3]
## [1,] 1 1 1
## [2,] 1 0 1
## [3,] 1 1 1
Pour cela, nous allons commencé par compté le nombre de voisin car celui-ci sera très important pour la suite. En effet, afin que ce soit uniforme, il ne faut donner aucune forme de direction pour les actions effectué. c'est à dire que nous devons traité un sommet en premier avec la meme probabilité que c'est autre voisin(afin de ne pas toujours traité les voisins du haut, puis, droit, puis bas, puis gauche par exemple) mais obtenir un acces à ces sommets de manière uniforme.
# on compte le nb de voisin
compteNbVoisin <- function(matrice, n, m, pSn, pSm) {
nbvoisin = 0
if (pSn + 1 <= n) {
if (matrice[pSn + 1, pSm] == 1 || matrice[pSn + 1, pSm] == 4) {
nbvoisin = nbvoisin + 1
}
}
if (pSn - 1 >= 1) {
if (matrice[pSn - 1, pSm] == 1 || matrice[pSn - 1, pSm] == 4) {
nbvoisin = nbvoisin + 1
}
}
if (pSm + 1 <= m) {
if (matrice[pSn, pSm + 1] == 1 || matrice[pSn, pSm + 1] == 4) {
nbvoisin = nbvoisin + 1
}
}
if (pSm - 1 >= 1) {
if (matrice[pSn, pSm - 1] == 1 || matrice[pSn, pSm - 1] == 4) {
nbvoisin = nbvoisin + 1
}
}
nbvoisin
}
Pour déplacer la puce cela est relativement simple : Nous allons marqué le passage de la puce par le chiffre 4 (uniquement esthétique, c'est simplement pour savoir par où elle est passée). On commence donc par marqué la case de départ, puis si la puce n'à toujours pas bougé avec de manière uniforme nous déterminons où la souris va décider de regarder pour se déplacer. Ensuite, nous allons tester si la case qu'elle regarde fait partie d'un chemin de sortie, où si elle est déjà passé par la (une puce peut revenir en arrière). Si c'est le cas, alors elle a une probabilité uniforme de se déplacer sur cette case. Si ce n'est pas le cas, nous réitérons cette action pour tout les voisins jusqu'à que la puce se soit déplacé. Nous nous arretons lorsque la souris est sur la case de sortie.
deplacement_puce <- function(matrice, m, n, pAn, pAm, pBn, pBm) {
# on place la souris sur le point d'entrée
pSn = pAn
pSm = pAm
matrice[pSn, pSm] = 4
b <- TRUE
while (b) {
nbvoisin = compteNbVoisin(matrice, n, m, pSn, pSm)
abouge = FALSE
nbv = 1/nbvoisin
if (runif(1) < nbv) {
if ((pSm + 1 <= m) && (abouge == FALSE)) {
if (matrice[pSn, pSm + 1] == 1 || matrice[pSn, pSm + 1] == 4) {
nbv = 1/nbvoisin
if (runif(1) < nbv) {
pSm = pSm + 1
matrice[pSn, pSm] = 4
abouge = TRUE
}
}
}
}
if (runif(1) < nbv) {
if ((pSm - 1 >= 1) && (abouge == FALSE)) {
if (matrice[pSn, pSm - 1] == 1 || matrice[pSn, pSm - 1] == 4) {
nbv = 1/nbvoisin
if (runif(1) < nbv) {
pSm = pSm - 1
matrice[pSn, pSm] = 4
abouge = TRUE
}
}
}
}
if (runif(1) < nbv) {
if ((pSn - 1 >= 1) && (abouge == FALSE)) {
if (matrice[pSn - 1, pSm] == 1 || matrice[pSn - 1, pSm] == 4) {
nbv = 1/nbvoisin
if (runif(1) < nbv) {
pSn = pSn - 1
matrice[pSn, pSm] = 4
abouge = TRUE
}
}
}
}
if (runif(1) < nbv) {
if ((pSn + 1 <= n) && (abouge == FALSE)) {
if (matrice[pSn + 1, pSm] == 1 || matrice[pSn + 1, pSm] == 4) {
nbv = 1/nbvoisin
if (runif(1) < nbv) {
pSn = pSn + 1
matrice[pSn, pSm] = 4
abouge = TRUE
}
}
}
}
if ((pSn == pBn) && (pSm == pBm)) {
b <- FALSE
}
}
matrice
}
main <- function() {
print("###########---------> QUESTION 2 : POUR P = 0.5 / m = 3 / n = 3 <---------###########")
m = 3
n = 3
p = 0.5
print("------------> MATRICE AVEC CHEMIN <------------")
my_matrice = genere_chemin(n, m, p)
print(my_matrice)
print("------------> DEPLACEMENT DE LA PUCE <------------")
matricePuce = deplacement_puce(my_matrice, m, n, n, 1, 1, m)
print(matricePuce)
}
main()
## [1] "###########---------> QUESTION 2 : POUR P = 0.5 / m = 3 / n = 3 <---------###########"
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [,1] [,2] [,3]
## [1,] 1 1 1
## [2,] 1 1 1
## [3,] 1 1 1
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 4 1
## [3,] 4 4 4
Notre première intuition serait de dire que sur des petites matrices, la différence serait anodione. Mais sur des grandes matrices, nous devrions constater une réduction du temps de parcours pour les matrices avec les obstacles. En effet, si la matrice à beaucoup l'obstacle, elle a plus de chance de “bouclé” ou alors de s'éloigner de la sortie.
Cela à été confirmé lors de nos tests :
mainQ3 <- function() {
print("###########---------> QUESTION 3 : POUR P = 1 <---------###########")
Tdiff = 0
t1 <- Sys.time()
m = 3
n = 3
p = 1
print("------------> MATRICE AVEC CHEMIN <------------")
my_matrice = genere_chemin(n, m, p)
# print(my_matrice)
print("------------> DEPLACEMENT DE LA PUCE <------------")
for (i in 1:100) {
matricePuce = deplacement_puce(my_matrice, m, n, n, 1, 1, m)
t2 <- Sys.time()
# print(matricePuce)
Tdiff = Tdiff + difftime(t2, t1)
}
print(matricePuce)
print(Tdiff/100)
}
mainQ3()
## [1] "###########---------> QUESTION 3 : POUR P = 1 <---------###########"
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [,1] [,2] [,3]
## [1,] 0 4 4
## [2,] 4 4 0
## [3,] 4 4 4
## Time difference of 0.329 secs
Refaisons le même test pour P = 0
mainQ3 <- function() {
print("###########---------> QUESTION 3 : POUR P = 0<---------###########")
Tdiff = 0
t1 <- Sys.time()
m = 3
n = 3
p = 0
print("------------> MATRICE AVEC CHEMIN <------------")
my_matrice = genere_chemin(n, m, p)
# print(my_matrice)
print("------------> DEPLACEMENT DE LA PUCE <------------")
for (i in 1:500) {
matricePuce = deplacement_puce(my_matrice, m, n, n, 1, 1, m)
t2 <- Sys.time()
# print(matricePuce)
Tdiff = Tdiff + difftime(t2, t1)
}
print(matricePuce)
print(Tdiff/500)
}
mainQ3()
## [1] "###########---------> QUESTION 3 : POUR P = 0<---------###########"
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 4 4
## [3,] 4 1 1
## Time difference of 1.147 secs
Nous pouvons bien voir que la différence entre les deux temps (bien que faible) est bien présente et que notre hypothèse de départ est confirmé. Bien entendu, plus la matrice est grande, plus cette différence de temps augmente
main <- function() {
print("###########---------> QUESTION 4 : POUR P = 0 / m = 10 / n = 10 <---------###########")
m = 10
n = 10
p = 0
print("------------> MATRICE AVEC CHEMIN <------------")
my_matrice = genere_chemin(n, m, p)
print(my_matrice)
print("------------> DEPLACEMENT DE LA PUCE <------------")
for (i in 1:100) {
t1 <- Sys.time()
matricePuce = deplacement_puce(my_matrice, m, n, n, 1, 1, m)
t2 <- Sys.time()
Tdiff = difftime(t2, t1)
print(Tdiff)
}
print(matricePuce)
}
main()
## [1] "###########---------> QUESTION 4 : POUR P = 0 / m = 10 / n = 10 <---------###########"
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,] 1 1 1 1 1 1 1 1 1 1
## [2,] 1 1 1 1 1 1 1 1 1 1
## [3,] 1 1 1 1 1 1 1 1 1 1
## [4,] 1 1 1 1 1 1 1 1 1 1
## [5,] 1 1 1 1 1 1 1 1 1 1
## [6,] 1 1 1 1 1 1 1 1 1 1
## [7,] 1 1 1 1 1 1 1 1 1 1
## [8,] 1 1 1 1 1 1 1 1 1 1
## [9,] 1 1 1 1 1 1 1 1 1 1
## [10,] 1 1 1 1 1 1 1 1 1 1
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## Time difference of 0.2128 secs
## Time difference of 0.1492 secs
## Time difference of 0.0419 secs
## Time difference of 0.2037 secs
## Time difference of 0.3149 secs
## Time difference of 0.1285 secs
## Time difference of 0.008144 secs
## Time difference of 0.2716 secs
## Time difference of 0.1341 secs
## Time difference of 0.0538 secs
## Time difference of 0.2595 secs
## Time difference of 0.0299 secs
## Time difference of 0.3155 secs
## Time difference of 0.03747 secs
## Time difference of 0.3201 secs
## Time difference of 0.07103 secs
## Time difference of 0.1689 secs
## Time difference of 0.2264 secs
## Time difference of 0.08778 secs
## Time difference of 0.04361 secs
## Time difference of 0.08711 secs
## Time difference of 0.1623 secs
## Time difference of 0.0967 secs
## Time difference of 0.02096 secs
## Time difference of 0.2023 secs
## Time difference of 0.04522 secs
## Time difference of 0.07655 secs
## Time difference of 0.04103 secs
## Time difference of 0.05928 secs
## Time difference of 0.09468 secs
## Time difference of 0.1724 secs
## Time difference of 0.05793 secs
## Time difference of 0.03212 secs
## Time difference of 0.5515 secs
## Time difference of 0.02421 secs
## Time difference of 0.1202 secs
## Time difference of 0.1024 secs
## Time difference of 0.05219 secs
## Time difference of 0.06975 secs
## Time difference of 0.08959 secs
## Time difference of 0.09653 secs
## Time difference of 0.1264 secs
## Time difference of 0.1423 secs
## Time difference of 0.04765 secs
## Time difference of 0.1003 secs
## Time difference of 0.08589 secs
## Time difference of 0.7697 secs
## Time difference of 0.1752 secs
## Time difference of 0.0278 secs
## Time difference of 0.1454 secs
## Time difference of 0.102 secs
## Time difference of 0.2353 secs
## Time difference of 0.2649 secs
## Time difference of 0.05292 secs
## Time difference of 0.0433 secs
## Time difference of 0.1144 secs
## Time difference of 0.03517 secs
## Time difference of 0.08154 secs
## Time difference of 0.06485 secs
## Time difference of 0.1188 secs
## Time difference of 0.03288 secs
## Time difference of 0.1576 secs
## Time difference of 0.07957 secs
## Time difference of 0.03935 secs
## Time difference of 0.2099 secs
## Time difference of 0.2742 secs
## Time difference of 0.0245 secs
## Time difference of 0.04082 secs
## Time difference of 0.03365 secs
## Time difference of 0.06497 secs
## Time difference of 0.03141 secs
## Time difference of 0.1258 secs
## Time difference of 0.1589 secs
## Time difference of 0.1358 secs
## Time difference of 0.1465 secs
## Time difference of 0.08836 secs
## Time difference of 0.179 secs
## Time difference of 0.1118 secs
## Time difference of 0.06144 secs
## Time difference of 0.05408 secs
## Time difference of 0.03898 secs
## Time difference of 0.1341 secs
## Time difference of 0.0942 secs
## Time difference of 0.08374 secs
## Time difference of 0.117 secs
## Time difference of 0.02065 secs
## Time difference of 0.1034 secs
## Time difference of 0.1704 secs
## Time difference of 0.217 secs
## Time difference of 0.4612 secs
## Time difference of 0.02097 secs
## Time difference of 0.02079 secs
## Time difference of 0.1354 secs
## Time difference of 0.1325 secs
## Time difference of 0.1194 secs
## Time difference of 0.06442 secs
## Time difference of 0.1709 secs
## Time difference of 0.05198 secs
## Time difference of 0.1042 secs
## Time difference of 0.0336 secs
## [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
## [1,] 1 1 1 1 1 1 1 1 1 4
## [2,] 1 1 1 1 4 4 4 1 1 4
## [3,] 1 1 1 1 4 4 4 1 1 4
## [4,] 1 4 4 4 4 4 4 4 4 4
## [5,] 4 4 1 4 4 4 4 4 1 4
## [6,] 4 4 4 4 4 4 1 1 1 1
## [7,] 4 4 4 4 4 4 1 1 1 1
## [8,] 4 4 4 4 4 4 4 1 1 1
## [9,] 4 4 1 1 1 4 4 1 1 1
## [10,] 4 1 1 1 1 1 1 1 1 1
Nous pouvons voir que le temps mis par programme est TRES différents alors qu'il s'applique sur la même matrice. Cela s'explique car si nous sommes “chanceux” notre puce va se déplacer de manière a minimiser le trajet (en diagonal). Mais si nous ne le sommes pas, elle va allez se cacher dans un coin, tourner sur elle même pendant un moment, avant de repartir etc… jusq'uà trouver la sortie. Dans ce cas là, le temps d'execution sera plus grand. Cette différence de temps s'explique car tout la matrice est un chemin pour atteindre la sortie, la puce peut donc laisser libre court a son imagniation et voyager au grès du vent avant de se diriger vers la sortie. Ce temps varie entre quelques centièmes de secondes à quelques dixièmes de secondes (10x plus long)
main <- function() {
print("###########---------> QUESTION 5: pour p [0,1] avec un pas de 0.1 <---------###########")
m = 3
n = 3
p = 0
Tdiff = 0
while (p <= 1) {
print("------------> MATRICE AVEC CHEMIN <------------")
my_matrice = genere_chemin(n, m, p)
# print(my_matrice)
print("------------> DEPLACEMENT DE LA PUCE <------------")
print("############### VALEUR DE P")
print(p)
for (i in 1:100) {
t1 <- Sys.time()
matricePuce = deplacement_puce(my_matrice, m, n, n, 1, 1, m)
t2 <- Sys.time()
Tdiff = Tdiff + difftime(t2, t1)
}
p = p + 0.1
print(Tdiff/100)
print(matricePuce)
}
}
main()
## [1] "###########---------> QUESTION 5: pour p [0,1] avec un pas de 0.1 <---------###########"
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0
## Time difference of 0.00408 secs
## [,1] [,2] [,3]
## [1,] 1 1 4
## [2,] 1 1 4
## [3,] 4 4 4
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.1
## Time difference of 0.008483 secs
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 4 4
## [3,] 4 4 0
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.2
## Time difference of 0.0132 secs
## [,1] [,2] [,3]
## [1,] 1 4 4
## [2,] 1 4 4
## [3,] 4 4 4
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.3
## Time difference of 0.01731 secs
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 4 1
## [3,] 4 1 1
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.4
## Time difference of 0.02211 secs
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 4 4
## [3,] 4 4 4
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.5
## Time difference of 0.02521 secs
## [,1] [,2] [,3]
## [1,] 1 4 4
## [2,] 0 4 4
## [3,] 4 4 1
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.6
## Time difference of 0.029 secs
## [,1] [,2] [,3]
## [1,] 1 4 4
## [2,] 4 4 4
## [3,] 4 4 0
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.7
## Time difference of 0.0329 secs
## [,1] [,2] [,3]
## [1,] 0 1 4
## [2,] 4 4 4
## [3,] 4 4 4
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.8
## Time difference of 0.03685 secs
## [,1] [,2] [,3]
## [1,] 4 0 4
## [2,] 4 4 4
## [3,] 4 0 1
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 0.9
## Time difference of 0.04026 secs
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 1 0
## [3,] 4 0 1
## [1] "------------> MATRICE AVEC CHEMIN <------------"
## [1] "il n'y a pas de chemin possible"
## [1] "il n'y a pas de chemin possible"
## [1] "Sortie trouvée ==>>> chemin existant"
## [1] "------------> DEPLACEMENT DE LA PUCE <------------"
## [1] "############### VALEUR DE P"
## [1] 1
## Time difference of 0.04227 secs
## [,1] [,2] [,3]
## [1,] 4 4 4
## [2,] 4 0 0
## [3,] 4 0 0
On remarque clairement que plus le nombre d'obstacle augmente, plus la moyenne du temps de déplacement de la puce augmente également. Nous pouvons donc en conclure que la probabilité p de poser des obstacles infuence directement le temps de parcours du labyrinthe par la puce.