DM

Devoir 1 :

́ ###Sujet 7: generation aleatoire de labyrinthe:

set.seed(42);

Mon optinion :

Je pense que la probabilite de rejet sera proportion de p. Plus p sera grand plus la probabilite de rejet sera grande. De plus je pense que la probabilite de rejet augmentera aussi avec la taille du labyrinthe.

Question 1 : Algorithme de generation de labyrinthe:

Le zero represente des cases libre et les zero des cases occupes. Le labyrinthe sera donc represente par une matrice de taille N*N. On commence par generer aleatoirement des labyrinthe:

#Fonction generation: Elle permet de generer un labyrinthe avec des obstacle mais qui ne contient pas forcement un chemin possible.
#Taille: La taille en largeur et en hauteur du labyrinthe.
#Proba: La probabilite d'avoir un obstacle sur une cse données.
generation = function (taille, proba){

  M = matrix(data = 0, nrow = taille, ncol = taille);
  
  for (i in (1:taille)){
    for (j in (1:taille)){
      if (runif (n=1, min=0, max =1)<= proba){
        # Génération d'un obstacle
        M[i,j]=1;
      }
    }
  }
  return (M);
}

On crée ensuite une fonction qui permet de tester si il existe un chemin dans un labyrinthe donée.Elle renvoie un booléen, et fonctionne de maniere recursive. Elle rend en parametre les coordonées du point de depart, les coordonées du point d’arrives, la taille du labyrinthe, et le labyrinthe.

#Fonction chemin: teste s'il existe un chemin dans le labyrinthe donné

chemin = function (i=1,j=1,i_a=N,j_a=N, taille=N, chemin_parcouru=c_par, M=L){
  
  #si on est sur un obstacle il n'y a pas de chemin par ici
  if (M[i,j]==1) return (FALSE); 
  # si on est a l'arrivée c'est qu'on a trouvé un chemin 
  if (i==i_a && j==j_a) return (TRUE);
  
  #sinon on regarde si il y a un chemin 
  chemin_parcouru[i,j]=1;
  res=FALSE;
   if ((j<taille) && ((chemin_parcouru [i,j+1])==0)) {
    if (chemin (i, j+1,i_a,j_a,taille, chemin_parcouru,M)){
      return (TRUE); #a droite
    }
  }
  
   if (i<taille&& chemin_parcouru [i+1,j]==0) {
    res= chemin (i+1,j,i_a,j_a,taille, chemin_parcouru,M);
    if (res==TRUE){
      return (TRUE)
    }
  }#en bas
 
   
  if ( (i>2) && ((chemin_parcouru [i-1,j]) == 0)){
    res=chemin(i-1,j,i_a,j_a,taille, chemin_parcouru, M);
    if (res==TRUE){
      return (TRUE)
      }
  }
   # en haut
  
  if (j>2&& chemin_parcouru [i,j-1]==0) {
    if (chemin (i,j-1,i_a,j_a,taille, chemin_parcouru,M)){
      return  (TRUE);# a gauche  
    }
  }
  return (res);
}

Enfin on cré une fonctionne qui genere uniformement un labyrinthe comportant un chemin vers l’arrivée depuis le depart en utilisant la methode du rejet.

generation_finale = function (taille, proba){
  valide=FALSE;
  lab=matrix(data =0, nrow = taille, ncol = taille);
  while (! valide){
    lab= generation(taille = taille, proba = proba);
    c_par=matrix(data =0, nrow = taille, ncol = taille);
    valide= chemin(i=1,j=1,i_a=taille,j_a=taille, taille=taille, chemin_parcouru=c_par, M=lab);
  }
  return (lab)
}

On represente graphiquement quelque labyrinthe: Avec une petite probabilite:

generation_finale(10,0.1)

##       [,1] [,2] [,3] [,4] [,5] [,6] [,7] [,8] [,9] [,10]
##  [1,]    0    0    0    0    0    0    0    0    0     0
##  [2,]    0    0    0    0    0    0    0    0    0     0
##  [3,]    0    0    0    0    1    0    0    0    0     0
##  [4,]    0    0    0    0    1    0    1    0    0     0
##  [5,]    0    0    1    0    0    0    0    0    0     0
##  [6,]    0    0    0    0    1    0    0    0    0     0
##  [7,]    0    0    0    0    0    0    0    0    0     0
##  [8,]    1    0    0    0    0    0    1    0    0     1
##  [9,]    0    0    0    0    0    0    0    1    1     0
## [10,]    0    1    0    0    0    0    0    0    0     0

Avec une grande probabilite:

generation_finale(5,7/10)

##      [,1] [,2] [,3] [,4] [,5]
## [1,]    0    0    0    1    1
## [2,]    1    0    1    0    1
## [3,]    1    0    0    1    0
## [4,]    1    1    0    0    0
## [5,]    0    1    1    1    0

Question 2: Complexite de l’algoryithme:

Nous alons estimer la probabilite de rejet. pour cela nous allons modifier le programme de generation pour savoir combien de labyrinthe sont rejeter.

generation_finale_rej= function (taille, proba){
  valide=FALSE;
  nb_rejet=-1;
  lab=matrix(data =0, nrow = taille, ncol = taille);
  while (! valide){
    nb_rejet=nb_rejet+1;
    lab= generation(taille = taille, proba = proba);
    c_par=matrix(data =0, nrow = taille, ncol = taille);
    valide= chemin(i=1,j=1,i_a=taille,j_a=taille, taille=taille, chemin_parcouru=c_par, M=lab);
  }
  return (nb_rejet)
}

On essaye d’estimer la probabilite de rejet en fonction de la probabilite (avec une taille fixe)

nb_rejet_moy=function(nb_rep, taille,proba){
v=c()
for (i in 1:(nb_rep+1)){
  v[i]=generation_finale_rej (taille, proba)
}
v
moy=0
for (i in 1:nb_rep){
  moy=moy+v[i]
}
moy= moy/nb_rep

return (moy)
}

affichage = function(taille ){
proba_max=8
v=c()
for (i in 0:proba_max){
  print (i)
  v[i+1] =nb_rejet_moy(100,taille,i/10)
}
print (v)



plot(x=NULL,y=NULL,xlab= "Probabilité d'apparition",ylab= "Nombre de rejet", xlim= c(0,proba_max), ylim=c(0,700))

lines(x = c(0:proba_max),y=v,type="l", col= "blue")
}

Je n’arrive pas a generer des resultat pour un labyrinthe de taille 10 et 20 car les calculs prenne trop de temps.Je vous mets tout de meme les calculs que je pense qu’il faudrait effectuer. Je le fait pour un labirynthe de taille 3:

affichage(3)

## [1] 0
## [1] 1
## [1] 2
## [1] 3
## [1] 4
## [1] 5
## [1] 6
## [1] 7
## [1] 8
## [1]   0.00   0.23   0.68   1.34   3.42   9.71  26.91  98.49 821.77

et pour un de taille 5:

affichage (5)

## [1] 0
## [1] 1
## [1] 2
## [1] 3
## [1] 4
## [1] 5
## [1] 6
## [1] 7
## [1] 8
## [1]     0.00     0.39     0.89     2.32     7.71    29.69   167.40  1442.48
## [9] 39839.46

On observe que le nombre de rejets semble etre une fonction exponentielle de la probabilite d’appartion d’un obstacle. Je me suis donc arreter a une probabilite de 80% par ceque apres les calcul prenais trop de temps. Le nombre de rejet augmente aussi avec la taille du terrain.