A la fin de son cours de botanique, Harry P. reçoit un message d’Hagrid lui disant :
Rejoins-moi dans ma cabane dès que possible, mais méfie-toi de Rusard : s’il te voit, Griffondor perdra des points !
Avec l’aide de Ron W. et Hermione G., il estime pour chaque zone du chateau, la probabilité qu’il ne rencontre pas Rusard ainsi que le temps nécessaire, en minutes (chiffre entre parenthèses).
Pour résoudre le problème il faut utiliser l’algorithme de Dijkstra. Les adaptations nécessaires à apporter à l’algorithme sont :
En effet l’algorithme de Dijstra fonctionne pour des fonctions coût monotone.
L’initialisation se fera: $$ \htmlStyle{margin-left: 1rem}{ \begin{aligned} &\foreach{s_i \in S}{ &p[s_i] \leftarrow 0 \textcolor{grey}{\texttt{ // Pire cas}} \\ &d[s_i] \leftarrow +\infty \textcolor{grey}{\texttt{ // Pire cas}} \\ &\pi[s_i] \leftarrow \texttt{null} \\ } \\ &p[s_i] \leftarrow 1 \\ &d[s_i] \leftarrow +\infty \end{aligned} } $$
La fonction de relachement sera : $$ \htmlStyle{margin-left: 1rem}{ \eif{ p[s_j] < p[s_i] \times \texttt{p(}s_i,s_j\texttt{)}~\lor \\ &\quad\quad ( p[s_j] = p[s_i] \times \texttt{p(}s_i,s_j\texttt{)} \land d[s_j] > d[s_i] + \texttt{d(}s_i,s_j\texttt{)} ) }{ &p[s_j] \leftarrow p[s_i] \times \texttt{p(}s_i,s_j\texttt{)} \\ &d[s_j] \leftarrow d[s_i] + \texttt{d(}s_i,s_j\texttt{)} \\ &\pi[s_j] \leftarrow s_i } } $$
On sélectionne le noeud B.
$$F =[(B, 1.00 (0))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | None | None | None | None | None | None |
| $\delta(B, s_k)$ | $1.00 (0)$ | None | None | None | None | None | None |
Un chemin plus court a été découvert pour C.
$$F =[(B, 1.00 (0)), (C, 0.80 (3))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | None | None | None |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | None | None | None |
Un chemin plus court a été découvert pour N.
$$F =[(B, 1.00 (0)), (C, 0.80 (3)), (N, 0.50 (2))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | None | None |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | None | None |
Le noeud B n’a plus de voisin, on le supprime de la file.
$$F =[(C, 0.80 (3)), (N, 0.50 (2))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | None | None |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | None | None |
On sélectionne le noeud C.
$$F =[(C, 0.80 (3)), (N, 0.50 (2))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | None | None |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | None | None |
Un chemin plus court a été découvert pour P.
$$F =[(C, 0.80 (3)), (N, 0.50 (2)), (P, 0.24 (4))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | $C$ | None |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | $0.24 (4)$ | None |
Un chemin plus court a été découvert pour S.
$$F =[(C, 0.80 (3)), (S, 0.72 (7)), (N, 0.50 (2)), (P, 0.24 (4))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | $C$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | $0.24 (4)$ | $0.72 (7)$ |
Le noeud C n’a plus de voisin, on le supprime de la file.
$$F =[(S, 0.72 (7)), (N, 0.50 (2)), (P, 0.24 (4))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | $C$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | $0.24 (4)$ | $0.72 (7)$ |
On sélectionne le noeud S.
$$F =[(S, 0.72 (7)), (N, 0.50 (2)), (P, 0.24 (4))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | None | None | $B$ | $C$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | None | None | $0.50 (2)$ | $0.24 (4)$ | $0.72 (7)$ |
Un chemin plus court a été découvert pour E.
$$F =[(S, 0.72 (7)), (N, 0.50 (2)), (E, 0.36 (10)), (P, 0.24 (4))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $C$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.24 (4)$ | $0.72 (7)$ |
Un chemin plus court a été découvert pour P.
$$F =[(S, 0.72 (7)), (N, 0.50 (2)), (P, 0.36 (8)), (E, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $S$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.36 (8)$ | $0.72 (7)$ |
Le noeud S n’a plus de voisin, on le supprime de la file.
$$F =[(N, 0.50 (2)), (P, 0.36 (8)), (E, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $S$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.36 (8)$ | $0.72 (7)$ |
On sélectionne le noeud N.
$$F =[(N, 0.50 (2)), (P, 0.36 (8)), (E, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $S$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.36 (8)$ | $0.72 (7)$ |
Un chemin plus court a été découvert pour P.
$$F =[(N, 0.50 (2)), (P, 0.40 (4)), (E, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Le noeud N n’a plus de voisin, on le supprime de la file.
$$F =[(P, 0.40 (4)), (E, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
On sélectionne le noeud P.
$$F =[(P, 0.40 (4)), (E, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | None | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (10)$ | None | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Un chemin plus court a été découvert pour E.
$$F =[(P, 0.40 (4)), (E, 0.36 (6))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | None | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | None | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Un chemin plus court a été découvert pour H.
$$F =[(P, 0.40 (4)), (E, 0.36 (6)), (H, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (10)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Le noeud P n’a plus de voisin, on le supprime de la file.
$$F =[(E, 0.36 (6)), (H, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (10)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
On sélectionne le noeud E.
$$F =[(E, 0.36 (6)), (H, 0.36 (10))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (10)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Un chemin plus court a été découvert pour H.
$$F =[(E, 0.36 (6)), (H, 0.36 (9))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $E$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (9)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Le noeud E n’a plus de voisin, on le supprime de la file.
$$F =[(H, 0.36 (9))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $E$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (9)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
On sélectionne le noeud H.
$$F =[(H, 0.36 (9))]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $E$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (9)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Le noeud H n’a plus de voisin, on le supprime de la file.
$$F =[]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $E$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (9)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $P$ | $E$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00 (0)$ | $0.80 (3)$ | $0.36 (6)$ | $0.36 (9)$ | $0.50 (2)$ | $0.40 (4)$ | $0.72 (7)$ |
Le chemin avec le plus grand taux de réussite et le plus court est Serres de Botanique, Salle de divinatioN, Tour de Poufsouffle, Grand Escalier et la cabane de Hagrid.