\begin{exercice}[Titre={De ville en ville},TitreSolution={De ville en ville}]



\begin{definition}
\textbf{Le problème du voyageur :} soit $n$ un nombre entier, supérieur ou égal à 3.

Un voyageur doit visiter une et une seule fois $n$ villes et revenir à son point d'origine. 

Le problème est de trouver l'ordre de visite des villes qui \textbf{minimise la distance totale parcourue} par le voyageur. 
Le trajet obtenu sera alors appelé \textbf{trajet optimal}.
\end{definition}

L'objectif de cet exercice est d'étudier deux stratégies pour résoudre ce problème.
\section*{Partie 1 : premier exemple avec 3 villes à visiter.}

On suppose, dans cette partie, que $n=3$.

Le voyageur de commerce doit, à partir de $S$ (siège de son entreprise) visiter les 3 villes suivantes $A$, $B$ et $C$ dont on connaît les coordonnées, dans un repère orthonormé d'unité 1~km, puis revenir en $S$. 

Voici les coordonnées des villes $A$, $B$ et $C$ et du siège $S$ de son entreprise : $A(7;3)$, $B(3;1)$, $C(4,6)$ et $S(4,7)$.

\begin{center}
\begin{tikzpicture}[scale=.8]
    % Grille
    \draw[very thin, gray] (0,0) grid (8,8);

    % Axes
    \draw[->] (0,0) -- (8.5,0) node[right] {};
    \draw[->] (0,0) -- (0,8.5) node[above] {};

    % Points
    \fill[blue] (7,3) circle (2pt) node[above right] {$A$};
    \fill[blue] (3,1) circle (2pt) node[below left] {$B$};
    \fill[blue] (4,6) circle (2pt) node[above right] {$C$};
    \fill[blue] (4,7) circle (2pt) node[above left] {$S$};

    % Étiquettes des axes
    \foreach \x in {0,1,2,3,4,5,6,7,8}
        \draw (\x,0.1) -- (\x,-0.1) node[below] {\x};
    \foreach \y in {0,1,2,3,4,5,6,7,8}
        \draw (0.1,\y) -- (-0.1,\y) node[left] {\y};
\end{tikzpicture}
\end{center}

\begin{rappel}
On rappelle les deux résultats suivants :
\begin{itemize}
\item[$\bullet$] Dans un repère orthonormé, si $A(x_A;y_A)$ et $B(x_B;y_B)$ alors $AB=\sqrt{(x_B-x_A)^2+(y_B-y_A)^2}$.
\item[$\bullet$] Pour tout entier naturel $n$ non nul, on a $1+2+\dots+(n-1)+n=\dfrac{n(n+1)}{2}$. 	
\end{itemize}
\end{rappel}
Un exemple de trajet est $S$ puis $A$, puis $B$, puis $C$ et enfin retour à $S$, que l'on notera $SABCS$.

 On remarquera que les trajets  $SABCS$ et  $SCBAS$ ont la même longueur.

\begin{enumerate}
\item Citer tous les trajets de longueurs différentes.
\item On considère le trajet $SABCS$. Déterminer sa longueur et donner une valeur approchée au mètre près.
\end{enumerate}
%\newpage
\section*{Partie 2 : cas de 4 villes et plus}
\begin{enumerate}\setcounter{enumi}2
\item Supposons maintenant qu'il y a 4 villes à visiter au lieu de 3. 

Combien y a-t-il alors, au maximum, de trajets de longueurs différentes ?
\item On admet le résultat suivant : s'il y a $n$ villes à visiter ($n\geqslant 2$) alors il y a : $\dfrac{n\times(n-1)\times\dots\times2}{2}$ calculs de distance entre deux points à effectuer.  

Supposons qu'on ait un ordinateur assez rapide pour calculer la distance entre deux points en $10^{-8}$~secondes. 

Si le voyageur avait 15 villes à visiter, combien de temps (en heures-minutes) faudrait-il à cet ordinateur pour déterminer le trajet le plus court ? (On suppose que seul le temps correspondant au calcul de distance est significatif pour obtenir la réponse).

\item Que doit-on penser de cette stratégie consistant à calculer tous les trajets possibles ?
\end{enumerate}
\section*{Partie 3 : étude d'une autre stratégie}

\begin{definition}
Stratégie  : le voyageur décide,  à chaque étape, de choisir la ville qui lui est la plus proche. 
\end{definition}

L'objectif de cette partie est d'étudier cette nouvelle stratégie.

%\begin{minipage}{.7\linewidth}
%	Exemple : en partant du point $E$ quel est \textbf{le chemin le plus court} passant par $F$, $G$, $H$ une et une seule fois puis qui revient à $E$ ? 
%
%Voici la stratégie expliquée sur cet exemple. 
%
%Le tableau ci-contre, on donne la distance entre les différents points.
%
%À chaque étape, on choisit le point le plus proche du point (par lequel il n'est pas encore passé) où l'on se trouve ce qui donne :
%\end{minipage}\hfil\begin{minipage}{.3\linewidth}
%\begin{center}
%$\begin{array}{|c|c|}
%\hline
%EF &  4,7\\
%\hline
%EG &  1,3\\
%\hline
%EH &  5,5\\
%\hline
%FG &  5,5\\
%\hline
%FH &  10\\
%\hline
%GH &  4.5\\
%\hline
%\end{array}$
%\end{center}
%\end{minipage}
%
%
%\begin{enumerate}
%\item [Étape 1 :] Partant de  $E$, le point le plus proche de $E$ (parmi les points $F$, $G$ et $H$ non encore atteints ) est $G$. 
%
%La 1\iere{} étape du trajet correspond donc au déplacement de $E$ à $G$.
%\item [Étape 2 :] Repartant de $G$, le point le plus proche de $G$ (parmi les points $G$ et $H$ non encore atteints) est $H$. 
%
%La 2\ieme{}  étape du trajet correspond donc au déplacement de $G$ à $H$.
%\item [Étape 3 :] Repartant de $H$, le point le plus proche de $H$ (il ne reste plus que $F$ qui n'a pas encore été atteint) est donc $F$. 
%
%La 3\ieme{}  étape du trajet correspond donc au trajet de $H$ à $F$.
%\item [Étape 4 :] Les points $F$,$G$ et $H$ ayant été atteints, repartant de $F$ on revient donc à $E$. 
%
%La 4\ieme{}  étape du trajet correspond donc au trajet de $F$ à $E$.
%\end{enumerate}
%Conclusion : Le trajet donné par cette nouvelle stratégie est : $EGHFE$.
\bigskip

\begin{enumerate}\setcounter{enumi}5
\item Revenons maintenant à notre problème initial (partie 1) avec l'entreprise $S$ et les trois villes $A$, $B$ et $C$.
\begin{enumerate}
\item Calculer la distance entre $S$ et chacune des trois autres villes, afin de déterminer le point le plus proche de $S$. On donnera une valeur approchée au mètre près.
\item Poursuivre alors les différentes étapes de la stratégie afin de déterminer le trajet obtenu.
\item Combien de calculs de distance entre deux points doit-on effectuer afin d'obtenir ce trajet à l'aide de cette stratégie ? On note ce nombre $D_3$.
\item \begin{enumerate}
\item Donner alors la longueur de ce trajet au mètre près (ne pas oublier qu'on revient à $S$). 
\item A-t-on obtenu le trajet optimal ?
\end{enumerate}
\end{enumerate}


\item On considère maintenant qu'il y a 4 villes à visiter. On note alors $D_4$ le nombre de calculs de distance nécessaires afin de déterminer le trajet obtenu par cette stratégie. Justifier que $D_4=9$. 
\item Soit $n$ un entier supérieur ou égal à 2. On suppose qu'il y a $n$  villes à visiter. 

Montrer  alors que $D_n=\dfrac{n(n+1)}{2}-1$.
\item En reprenant l'ordinateur de la partie 2, s'il y avait 15 villes à visiter, calculer le temps mis par l'ordinateur pour déterminer le trajet donné par cette stratégie.
\item Au vu des résultats obtenus dans cette partie, donner un avantage et un inconvénient à l'utilisation de cette stratégie par le voyageur.
\end{enumerate}

\end{exercice}

\begin{Solution}
\section*{Partie 1 : premier exemple avec 3 villes à visiter}

\begin{enumerate}
    \item Les trajets de longueurs différentes sont : 
    \[ S-A-B-C-S,\quad S-A-C-B-S,\quad S-B-A-C-S. \]
    
    \item La longueur du trajet $SABCS$ est :
    \[ SA + AB + BC + CS = 6 + \sqrt{20} + \sqrt{26} \approx 15,571 \text{ km}. \]
\end{enumerate}

\section*{Partie 2 : cas de 4 villes et plus}

\begin{enumerate}[resume]
    \item Pour 4 villes, le nombre maximal de trajets de longueurs différentes est : 12.
    
    \item Pour 15 villes, il y a 
    \[ \frac{16 \times 15 \times \dots \times 3 \times 2}{2} \]
    calculs de distance à effectuer. 
    Le temps de calcul serait alors d’environ $104\,614$ secondes, soit environ 29 heures et 4 minutes.
    
    \item Cette stratégie (énumération complète) donne le trajet optimal, mais le temps de calcul devient prohibitif dès que le nombre de villes augmente.
\end{enumerate}

\section*{Partie 3 : étude d’une autre stratégie}

\begin{enumerate}[resume]
    \item \begin{enumerate}
        \item 
        \[ SA = 5\ \text{km}, \quad SB \approx 6,083\ \text{km}, \quad SC = 1\ \text{km}. \]
        Le voyageur ira donc de $S$ à $C$.
        
        \item 
        \[ CA \approx 4,243\ \text{km}, \quad CB \approx 5,099\ \text{km}. \]
        Le voyageur ira de $C$ à $A$, puis de $A$ à $B$, puis retour à $S$.
        Le trajet sera donc : $S-C-A-B-S$.
        
        \item On a dû calculer 5 distances : $D_3 = 5$.
        
        \item La longueur de $S-C-A-B-S$ est :
        \[ 1 + \sqrt{18} + \sqrt{20} + \sqrt{37} \approx 15,798\ \text{km}. \]
        Ce n’est pas le trajet optimal.
    \end{enumerate}
    
    \item Pour 4 villes :
    \[ D_4 = 4 + 3 + 2 = 9. \]
    
    \item Pour $n$ villes ($n \geq 2$) :
    \[ D_n = n + (n-1) + (n-2) + \dots + 2 = \frac{n(n+1)}{2} - 1. \]
    
    \item Pour 15 villes, il y a $119$ calculs de distance, soit un temps de calcul d’environ $1,19 \times 10^{-6}$ seconde.
    
    \item Avantage : le temps de calcul est très faible.  
    Inconvénient : le trajet obtenu n’est pas forcément le trajet optimal.
\end{enumerate}
	

\end{Solution}