controle ensembles

[cours-maths-dis.git] / graphes / pbChemins.tex

\section{Algorithme de Dijkstra}

\subsection{Présentation}
Edgser Wybe Dijkstra (1930-2002) a proposé en 1959 un algorithme qui permet de calculer le plus court chemin entre un sommet particulier et tous les autres.


Le résultat est une arborescence.


\subsection{L'algorithme}

\begin{enumerate}
\item Numérotons les sommets du graphe $G = (V,E)$ de $1$ à $n$.

\item Supposons que l'on s'intéresse aux chemins partant du sommet 1.

\item On construit un vecteur $l = (l(1); l(2); ...; l(n))$ ayant $n$ composantes tel que $l(j)$ soit égal à la longueur du plus court chemin allant de 1 au sommet j.

On initialise ce vecteur à $c_{1,j}$, c'est-à-dire à la première ligne de la matrice des coûts du graphe, définie comme indiqué ci-dessous :

$$\left\{
\begin{array}{ll}
0 & \textrm{ si } i=j \\
+\infty & \textrm{ si } i \neq j \textrm{ et } (i,j) \notin E\\
\delta (i,j) & \textrm{ si } i \neq j \textrm{ et } (i,j) \in E\\
\end{array}
\right.$$

où $\delta (i,j)$ est le poids (la longueur) de l'arc $(i,j)$. Les $c_{i,j}$ doivent être strictement positifs.

\item On construit un autre vecteur $p$ pour mémoriser le chemin pour aller du sommet 1 au sommet voulu.

La valeur $p(i)$ donne le sommet qui précède $i$ dans le chemin.

\item On considère ensuite deux ensembles de sommets, $S$ initialisé à $\{1\}$ et $T$ initialisé à $\{2, 3, ..., n\}$.

À chaque pas de l'algorithme, on ajoute à $S$ un sommet jusqu'à ce que $S = V$ de telle sorte que le vecteur $l$ donne à chaque étape le coût minimal des chemins de 1 aux sommets de $S$.
\end{enumerate}

\subsection{Description de l'algorithme de Dijkstra}

On suppose ici que le sommet de départ (qui sera la racine de l'arborescence) est le sommet 1. Notons qu'on peut toujours renuméroter les sommets pour que ce soit le cas.

\begin{description}
 \item[Initialisations :]
\begin{itemize}
 \item $l(j) = c1,j et p(j) = NIL, pour 1\leqslant j \leqslant n$
\item Pour $2 \leqslant j \leqslant n$ faire : Si $c_{1,j} < +\infty$ alors $p(j) = 1$.
\item $S = \{1\}$ ; $T = \{2, 3, ..., n\}$.
\end{itemize}
\item[Itérations :] Tant que $T$ n'est pas vide faire :
\begin{itemize}
\item Choisir $i$ dans $T$ tel que $l(i)$ est minimum
\item Retirer $i$ de $T$ et l'ajouter à $S$
\item Pour chaque successeur $j$ de $i$, avec $j$ dans $T$, faire : Si $l(j) > l(i) + d(i,j)$ alors
\begin{itemize}
\item $l(j) = l(i) + d(i,j)$
\item $p(j) = i$
\end{itemize}
\end{itemize}
\end{description}




\subsection{Exemple}

\begin{center}
\includegraphics[scale=0.7]{graphes/graphe1dij}
\end{center}


\begin{description}
\item[Initialisations]
\begin{itemize}
\item $S = \{1\}$ ;
\item $T = \{2, 3, 4, 5\}$ ;
\item $l = (0, 15, \infty, \infty, 4)$;
\item $p = (NIL, 1, NIL, NIL, 1)$.
\end{itemize}

\item[Première itération]
\begin{itemize}
\item $i = 5$ car $l(5) = min(15, \infty, \infty, 4) = 4$;

\item $S = \{1, 5\}$; $T = \{2, 3, 4\}$;

\item les successeurs de 5 dans $T$ sont 3 et 4;

\item $l(3)$ prend la nouvelle valeur $min(\infty; l(5) + d(5; 3)) = min(\infty; 4 + 7) = 11$; $p(3) = 5$;

\item $l(4)$ prend la nouvelle valeur $min(\infty ; l(5) + d(5; 4)) = 9$ ; $p(4) = 5$;

\item d'où les nouveaux vecteurs $l = (0, 15, 11, 9, 4)$ et p = $(NIL, 1, 5, 5, 1)$
\end{itemize}

\item[Deuxième itération]

\begin{itemize}
\item $i = 4$; $l(4) = 9$;

\item $S = \{1, 5, 4\}$; $T = \{2, 3\}$;

\item le seul successeur de 4 dans $T$ est 2;

\item $l(2)$ prend la nouvelle valeur $min(\infty; l(4) + d(4; 2)) = min(15; 9 + 3) = 12$; $p(2) = 4$;

\item d'où les nouveaux vecteurs $l = (0, 12, 11, 9, 4)$ et $p = (NIL, 4, 5, 5, 1)$
\end{itemize}

\item[Troisième itération]

\begin{itemize}
\item $i = 3$; $l(3) = 11$;

\item $S = \{1, 5, 4, 3\}$; $T = \{2\}$;

\item le seul successeur de 3 dans $T$ est 2;

\item $l(2)$ garde sa valeur car $min(12; l(3) + d(3; 2)) = min(12; 11 + 3) = 12$;

\item d'où les vecteurs inchangés $l = (0, 12, 11, 9, 4)$ et $p = (NIL, 4, 5, 5, 1)$
\end{itemize}

\item[Quatrième itération]

\begin{itemize}
\item $i = 2$; $l(2) = 12$;

\item $S = \{1, 5, 4, 3, 2\}$; $T=\{\}$; FIN.

\item $l = (0, 12, 11, 9, 4)$;

\item $p = (NIL, 4, 5, 5, 1)$.
\end{itemize}

\end{description}

Le chemin minimal de 1 à 4 par exemple est de coût 9. C'est le chemin 1-5-4, car $p(4) = 5$ et $p(5) = 1$.

\begin{center}
\includegraphics[scale=0.7]{graphes/graphe2dij}
\end{center}

\subsection{Exercices}

\begin{Exo}
Appliquez l'algorithme de Dijkstra au graphe de l'exemple ci-dessus pour trouver tous les plus courts chemins en partant des sommets 2, 3, 4 et 5.
\end{Exo}


\begin{Exo}
Expliquez pourquoi des arcs avec des poids négatifs pourraient poser problème dans la recherche d'un plus court chemin dans un graphe. 
\end{Exo}


\section{Méthode PERT}

\subsection{Présentation de la méthode}

Le problème du plus long chemin dans les digraphes sans circuits trouve une application dans l'ordonnancement et la planification des tâches composant un projet complexe, par exemple la construction d'une maison.

On fait correspondre à chaque tâche un arc d'un digraphe, sa durée d'exécution étant égale au poids de cet arc.

Le digraphe reflète les précédences requises dans l'exécution du projet. Ainsi, la tâche correspondant à l'arc $(i, j)$ ne peut commencer que si toutes les tâches correspondant à des arcs $(k, i)$ ont été complétées. Le digraphe peut contenir des tâches fictives de durée nulle afin de forcer certaines précédences.


Les sommets du digraphe représentent des événements, début (fin) des activités correspondant aux arcs dont ils sont l'extrémité initiale (finale). Le fait que le digraphe est sans circuit est garant de la faisabilité du projet. En effet, l'existence d'un circuit impliquerait une contradiction dans les précédences : une tâche devant en même temps précéder et succéder une autre!


On supposera dorénavant que les sommets ont déjà été numérotés de 1 à $n$ de manière compatible avec leurs rangs, c'est-à-dire que $r(j)>r(i)$ implique $j>i$ (voir l'algorithme de calcul du rang). 

En plus, si le digraphe possède plusieurs sommets sans prédécesseurs, on supposera avoir introduit un sommet 1 relié par un arc de durée nulle à chacun de ces sommets. Ce sommet indique le début du projet.

De même, si le digraphe possède plusieurs sommets sans successeurs, ceux-ci seront reliés par un arc de durée nulle à un dernier sommet $n$ (fin du projet).

Enfin, on supposera éliminés les arcs parallèles par l'introduction de tâches fictives.

\subsection{Algorithme du chemin critique}
\begin{description}
\item[Données :] Digraphe $G = (V, E)$, sans circuits, des activités avec leur durée $d_{ik}$.
\item[Résultat :]
\begin{itemize}
\item $d_i$ début au plus tôt des activités correspondant aux arcs $(i, k)$ partant de $i$,
\item $j_i$ fin au plus tard des activités correspondant aux arcs $(k, i)$ arrivant à $i$,
\item durée du chemin critique. 
\end{itemize}
\item[Début :]
\begin{enumerate}
\item Calcul des dates de début au plus tôt (récurrence en avançant dans le projet)
\begin{itemize}
\item $d_1 := 0$
\item Pour $k := 2$ à $n$ faire $d_k := max\{d_j + d_{jk} | j \in P(k)\}$
\end{itemize}
\item Calcul des dates de fin au plus tard (récurrence en reculant dans le projet)
\begin{itemize}
\item $j_n := d_n$
\item Pour $k := n-1$ à 1 faire $j_k := min\{j_j - d_{kj} | j \in S(k)\}$
\end{itemize}
\end{enumerate}
\item[Fin.]
\end{description}

\begin{Notation}
$P(i) = \{k \in V | (k, i) \in E\}$ est l'ensemble des sommets prédécesseurs de $i$.
\end{Notation}

\begin{Notation}
$S(i) = \{k \in V | (i, k) \in E\}$ est l'ensemble des sommets successeurs de $i$.
\end{Notation}


\subsection{Définitions}

\begin{Def}[Sommet critique]
Un sommet $i$ est \emph{critique}\index{sommet!critique} si $d_i = j_i$.
\end{Def}

\begin{Def}[Arc critique]
Un arc $(i, j)$ est \emph{critique}\index{arc!critique} si ses extrémités sont des sommets critiques et $d_{ij} = d_j - d_i$.
\end{Def}

\begin{Def}[Chemin critique]
Un chemin \emph{critique}\index{chemin!critique} est un chemin de 1 à $n$ n'utilisant que des arcs critiques, c'est-à-dire des activités telles que tout retard dans leur exécution provoquerait un retard de la fin du projet.
\end{Def}

\begin{Def}[Durée du chemin critique]
La \emph{durée} du chemin critique est donnée par $d_n$ (ou par $j_n$, les deux valeurs étant toujours égales). Elle correspond à la durée minimale du projet étant données les durées des tâches le composant et les précédences respectives.
\end{Def}


\subsection{Exemple}

Ci-dessous le graphe des précédences obtenu avec l'algorithme du chemin critique. Les sommets et les arcs critiques sont en rouge.


\begin{center}
\includegraphics[scale=0.7]{graphes/pert1}
\end{center}

\begin{center}
\begin{tabular}{|c|c|c|}
\hline
Tâches & Précédences & Durée [jours] \\
\hline
A & - & 3 \\
\hline
B & - & 9 \\
\hline
C & - & 5\\
\hline
D & A & 8 \\
\hline
E & B & 4 \\
\hline
F & B & 7\\
\hline
G & B & 20\\
\hline
H & C, F & 6\\
\hline
I & D, E & 5\\
\hline
\end{tabular}
\end{center}



\subsection{Exercices}
\begin{Exo}
Refaites le graphe des précédences de l'exemple en utilisant l'algorithme du chemin critique.
\end{Exo}


\begin{Exo}
La rénovation du séjour d'un appartement se décompose en plusieurs tâches décrites dans le tableau ci-dessous. Ce dernier donne également les précédences à respecter lors de la planification des travaux ainsi qu'une estimation de la durée de chacune des tâches.

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
 & Tâches & Précédences & Durée [jours]\\
\hline
A & Enlèvement des portes & - & 1/2\\
\hline
B & Ponçage et peinture des portes & A & 3 \\
\hline
C & Pose des portes & B, J & 1/2 \\
\hline
D & Arrachage des papiers peints & - & 1\\
\hline
E & Tirage des fils électriques & D & 1 \\
\hline
F & Pose des prises & E, H, I & 1/2 \\
\hline
G & Ragréage des murs & E, A & 2\\
\hline
H & Peinture du plafond & G & 2\\
\hline
I & Pose des papiers peints & G & 3\\
\hline
J & Peinture des cadres & H, I & 1\\
\hline
K & Arrachage de la moquette & H, I, J & 1/2 \\
\hline
L & Ponçage du parquet & K & 1\\
\hline
M & Imprégnation et séchage du parquet & L, F & 4\\
\hline
N & Peinture du balcon & - & 2\\
\hline
O & Changement des protections solaires & N & 1\\
\hline
\end{tabular}
\end{center}

\begin{enumerate}
\item Représentez le graphe des précédences de ces travaux de rénovation.
\item Déterminez une durée totale minimale de rénovation en exhibant un chemin critique dans le graphe précédent. 
\end{enumerate}
\end{Exo}
\gsaut
\centerline{\x{Fin du Chapitre}}