---
# System prepended metadata

title: TP Statistique

---

---
title: "TP Statistique"
author: "Titi & Kiki"
date: "06 avril 2021"
output: pdf_document
---

```{r setup, include=FALSE}
knitr::opts_chunk$set(echo = TRUE)

## il est possible qu'avant d'installer le package TSPpackage vous deviez installer ou ré-installer Rcpp
#install.packages('Rcpp')

# install.packages('./TSPpackage_1.0.tar.gz',repos=NULL,type='bin') ## pour linux
#install.packages('./TSPpackage_1.0.zip',repos=NULL,type='bin')    ## pour windows
## je ne peux pas fournir de package pour mac...

## Appels aux packages, après les avoir installés !
library(sp)
library(maps)
library(microbenchmark)
library(TSP)
library(TSPpackage)
library(Rcpp)
library(MASS)
library(multcomp)
library(purrr)

set.seed(69963)
```
Voici le plan de ce qui sera fait dans le TP.

# Test Package
```{r, echo=TRUE}
#test package irene
villes <- read.csv('./DonneesGPSvilles.csv',header=TRUE,dec='.',sep=';',quote="\"")
coord <- cbind(villes$longitude,villes$latitude)
dist <- distanceGPS(coord)
voisins <- TSPnearest(dist)
print(voisins)
```

# 0. Visualisation de chemins

Lecture du fichier des villes :

```{r, echo=TRUE}
villes <- read.csv('DonneesGPSvilles.csv',header=TRUE,dec='.',sep=';',quote="\"")
str(villes)
```
Représentation des chemins par plus proches voisins et du chemin optimal :
```{r, echo=TRUE}
coord <- cbind(villes$longitude,villes$latitude)
dist <- distanceGPS(coord)
voisins <- TSPnearest(dist)

pathOpt <- c(1,8,9,4,21,13,7,10,3,17,16,20,6,19,15,18,11,5,22,14,12,2)

par(mfrow=c(1,2),mar=c(1,1,2,1))
plotTrace(coord[voisins$chemin,], title='Plus proches voisins')
plotTrace(coord[pathOpt,], title='Chemin optimal')
```


Les longueurs des trajets (à vol d'oiseau) valent respectivement, pour la méthode des plus proches voisins :
```{r, echo=FALSE}
voisins$longueur
```
et pour la méthode optimale :
```{r, echo=FALSE}
calculeLongueur(dist,pathOpt)
```

Ceci illustre bien l'intérêt d'un algorithme de voyageur de commerce. Nous allons dans la suite étudier les performances de cet algorithme.


# 1. Comparaison d'algorithmes

Nombre de sommets fixes et graphes "identiques".

```{r, echo=TRUE}
      n <- 10
sommets <- data.frame(x = runif(n), y = runif(n))
  couts <- distance(sommets)
```

## 1.1. Longueur des chemins

Comparaison des longueurs de différentes méthodes : 

   * boxplots

   * test entre 'nearest' et 'branch'

   * tests 2 à 2 
   
```{r, echo=TRUE}
n <- 10
vectNear = rep(0,50)
vectBranch = rep(0,50)
vectRep = rep(0,50)
vectInsert = rep(0,50)
vectTwo = rep(0,50)

#boucle permettant de recupérer la longueur des chemins pour les 5 méthodes (50 itérations)
for(i in 1:50){
  sommets <- data.frame(x = runif(n), y = runif(n))
  couts <- distance(sommets)
  vectNear[i] = TSPsolve(couts, "nearest")
  vectBranch[i] = TSPsolve(couts, "branch")
  vectRep[i] = TSPsolve(couts, "repetitive_nn")
  vectInsert[i] = TSPsolve(couts, "nearest_insertion")
  vectTwo[i] = TSPsolve(couts, "two_opt")
}
```

```{r, echo =FALSE}
boxplot(vectNear,vectBranch,vectRep,vectInsert,vectTwo, names = c("nearest", "branch", "rep", "NI", "2opt"))
```
```{r mean, echo = FALSE}
#moyenne méthode nearest
mean(vectNear)
#moyenne méthode branch
mean(vectBranch)
```

Test de comparaisons d'échantillons appariés : --> Variable d'intérêt = longueur pour 2 algo différents
```{r}
t.test(vectNear, vectBranch, paired=TRUE, alternative = "greater");
```
Seconde possiblitée
```{r}
t.test(vectNear-vectBranch, mu=0, alternative = "greater");
```
==> P valeur << 0.05 ==> Rejet de (H0)
```{r}
results = c(vectNear, vectBranch, vectRep, vectInsert, vectTwo)
methods = c(rep("nearest",50),rep("branch",50),rep("repetitive_nn",50),rep("nearest_insertion",50),rep("two_opt",50))

pairwise.t.test(results,methods,adjust.method="bonferroni", paired=TRUE)
```
P Valeur proche de 1 ==> Aucun différence, P Valeur proche de 0 ==> Différence significative

## 1.2. Temps de calcul

Comparaison des temps à l'aide du package microbenchmark.

```{r}
n=10 #on a des graphes avec 10 sommets

microbenchmark( TSPsolve(cout, "nearest"),
                TSPsolve(cout, "branch"), 
                TSPsolve(cout, "repetitive_nn"),
                TSPsolve(cout, "nearest_insertion"),
                TSPsolve(cout, "two_opt"), 
                times=50, setup={cout = distance(data.frame(x = runif(n), y = runif(n)))})
```

# 2. Etude e la complexité de l'algorithme Branch and Bound

## 2.1. Comportement par rapport au nombre de sommets : premier modèle

Récupération du temps sur 10 graphes pour différentes valeurs de $n$.

Ajustement du modèle linéaire de $\log(temps)^2$ en fonction de $n$.

Analyse de la validité du modèle : 

  * pertinence des coefficients et du modèle, 
  
  * étude des hypothèses sur les résidus.
  
```{r eval=FALSE}
sommets <- data.frame(x = runif(n), y = runif(n))
couts <- distance(sommets)
```

```{r}
seqn <- seq(4,20,1)

temps = c()
for(i in 1:17){
  temps = rbind(temps, microbenchmark(TSPsolve(couts, method = "branch"),times = 50,setup = { n <- seqn[i]
  couts <- distance(cbind(x = runif(n), y = runif(n)))})$time)
}

```

```{r}
par(mfrow=c(1,2))# 2 graphiques sur 1 ligne
matplot(seqn, temps, xlab="n", ylab="temps")
matplot(log(seqn), log(temps), xlab="log(n)", ylab=expression(log(temps)))
```
```{r}
vect_temps <- log(as.vector(temps))
vect_dim <- rep(log(seqn),times=50)
temps.lm <- lm(vect_temps~vect_dim)
summary(temps.lm)
```

```{r}
par(mfrow=c(2,2))
plot(temps.lm)
```

```{r}
shapiro.test(residuals(temps.lm))
```

## 2.2. Comportement par rapport au nombre de sommets : étude du comportement moyen

Récupération du temps moyen.

Ajustement du modèle linéaire de $\log(temps.moy)^2$ en fonction de $n$.

Analyse de la validité du modèle : 

  * pertinence des coefficients et du modèle, 
  
  * étude des hypothèses sur les résidus.
  
```{r}
temps.moy <- rowMeans(temps)
```
  
```{r}
par(mfrow=c(1,2))
matplot(seqn, temps.moy, xlab='n', ylab='temps moyen')
matplot(seqn, log(temps.moy)^4, xlab='n', ylab=expression(log(temps_moyen)^4))
```

```{r}
vect_temps.moy <- log(as.vector(temps.moy))^4
temps.moy.lm <- lm(vect_temps.moy ~ seqn)
summary(temps.moy.lm)
```

```{r}
par(mfrow=c(2,2))
plot(temps.lm)
```

```{r}
shapiro.test(residuals(temps.lm))
```

## 2.3. Comportement par rapport à la structure du graphe

Lecture du fichier 'DonneesTSP.csv'.

Ajustement du modèle linéaire de $\log(temps.moy)^2$ en fonction de toutes les variables présentes. Modèle sans constante.

Mise en \oe uvre d'une sélection de variables pour ne garder que les variables pertinentes.

Analyse de la validité du modèle : 

  * pertinence des coefficients et du modèle, 
  
  * étude des hypothèses sur les résidus.


```{r}
data.graph <- read.csv('DonneesTSP.csv', header=TRUE, dec=".", sep=",", quote="\"")
```


```{r}
data.graph$dim <- log(data.graph$dim)
data.graph.lm <- lm(log(data.graph$tps)~.,data = data.graph)
```

```{r}
step(data.graph.lm)
```

```{r}
data.graph$mean.dist <- NULL
data.graph.lm<-lm(log(data.graph$tps)~.,data = data.graph)
summary(data.graph.lm)
```

```{r}
par(mfrow=c(2,2))# 4 graphiques, sur 2 lignes et 2 colonnes
plot(data.graph.lm)
```


```{r}
shapiro.test(residuals(data.graph.lm))
```