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 \in S}{ &p[s_i] \leftarrow 0 \textcolor{grey}{\texttt{ // Pire probabilité}} \\ &\pi[s_i] \leftarrow \texttt{null} \\ &\texttt{Colorier } s_i \text{ en } \texttt{blanc} } \\ &p[s_0] \leftarrow 1 \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{)}}{ &p[s_j] \leftarrow p[s_i] \times \texttt{p(}s_i,s_j\texttt{)} \\ &\pi[s_j] \leftarrow s_i } } $$
Le tri des noeuds se fera par ordre décroissant.
On sélectionne le noeud B.
$$F = [(B, 1.00)]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | None | None | None | None | None | None |
| $\delta(B, s_k)$ | $1.00$ | None | None | None | None | None | None |
Un chemin plus court a été découvert pour C.
$$F = [(B, 1.00), (C, 0.80)]$$
// 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.80$ | None | None | None | None | None |
Un chemin plus court a été découvert pour N.
$$F = [(B, 1.00), (C, 0.80), (N, 0.50)]$$
// 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.80$ | None | None | $0.50$ | None | None |
Le noeud B n’a plus de voisin, on le supprime de la file.
$$F = [(C, 0.80), (N, 0.50)]$$
// 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.80$ | None | None | $0.50$ | None | None |
On sélectionne le noeud C.
$$F = [(C, 0.80), (N, 0.50)]$$
// 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.80$ | None | None | $0.50$ | None | None |
Un chemin plus court a été découvert pour P.
$$F = [(C, 0.80), (N, 0.50), (P, 0.24)]$$
// 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.80$ | None | None | $0.50$ | $0.24$ | None |
Un chemin plus court a été découvert pour S.
$$F = [(C, 0.80), (S, 0.72), (N, 0.50), (P, 0.24)]$$
// 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.80$ | None | None | $0.50$ | $0.24$ | $0.72$ |
Le noeud C n’a plus de voisin, on le supprime de la file.
$$F = [(S, 0.72), (N, 0.50), (P, 0.24)]$$
// 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.80$ | None | None | $0.50$ | $0.24$ | $0.72$ |
On sélectionne le noeud S.
$$F = [(S, 0.72), (N, 0.50), (P, 0.24)]$$
// 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.80$ | None | None | $0.50$ | $0.24$ | $0.72$ |
Un chemin plus court a été découvert pour E.
$$F = [(S, 0.72), (N, 0.50), (E, 0.36), (P, 0.24)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.24$ | $0.72$ |
Un chemin plus court a été découvert pour P.
$$F = [(S, 0.72), (N, 0.50), (E, 0.36), (P, 0.36)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.36$ | $0.72$ |
Le noeud S n’a plus de voisin, on le supprime de la file.
$$F = [(N, 0.50), (P, 0.36), (E, 0.36)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.36$ | $0.72$ |
On sélectionne le noeud N.
$$F = [(N, 0.50), (P, 0.36), (E, 0.36)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.36$ | $0.72$ |
Un chemin plus court a été découvert pour P.
$$F = [(N, 0.50), (P, 0.40), (E, 0.36)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.40$ | $0.72$ |
Le noeud N n’a plus de voisin, on le supprime de la file.
$$F = [(P, 0.40), (E, 0.36)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.40$ | $0.72$ |
On sélectionne le noeud P.
$$F = [(P, 0.40), (E, 0.36)]$$
// 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.80$ | $0.36$ | None | $0.50$ | $0.40$ | $0.72$ |
Un chemin plus court a été découvert pour H.
$$F = [(P, 0.40), (E, 0.36), (H, 0.36)]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
Le noeud P n’a plus de voisin, on le supprime de la file.
$$F = [(H, 0.36), (E, 0.36)]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
On sélectionne le noeud H.
$$F = [(H, 0.36), (E, 0.36)]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
Le noeud H n’a plus de voisin, on le supprime de la file.
$$F = [(E, 0.36)]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
On sélectionne le noeud E.
$$F = [(E, 0.36)]$$
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
Le noeud E 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$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
// Loading
| $B$ | $C$ | $E$ | $H$ | $N$ | $P$ | $S$ | |
|---|---|---|---|---|---|---|---|
| $\pi[s_k]$ | $B$ | $B$ | $S$ | $P$ | $B$ | $N$ | $C$ |
| $\delta(B, s_k)$ | $1.00$ | $0.80$ | $0.36$ | $0.36$ | $0.50$ | $0.40$ | $0.72$ |
Le chemin avec le plus grand taux de réussite est Serres de Botanique, Salle de divinatioN, Tour de Poufsouffle et la cabane de Hagrid.