Commentaire sur l'article

• Septembre 2016, 2e défi

  le 9 septembre 2016 à 08:17, par Al_louarn

  Répartissons les salles en couches, selon la distance (Manhattan) à l’entrée :
  couche $1$ : $\{2\}$
  couche $2$ : $\{6,4\}$
  couche $3$ : $\{12,10,3\}$
  couche $4$ : $\{8,5,1\}$
  couche $5$ : $\{11,9\}$
  couche $6$ : $\{7\}$

  Louis doit passer par toutes les couches pour aller de l’entrée à la sortie. Mais comme il veut voir $6$ salles et qu’il y a $6$ couches, il doit visiter exactement une salle par couche.

  Par exemple il peut choisir le chemin $[2,6,12,8,9,7]$, donc le nombre maximal d’oeuvres qu’il peut voir vérifie $n \geq 2 + 6 + 12 + 8 + 9 + 7$, soit $n \geq 44$.

  On peut majorer $n$ en prenant la meilleure salle de chaque couche : $n \leq 2 + 6 + 12 + 8 + 11 + 7$, soit $n \leq 46$. Mais ça ne donne pas un chemin valide puisque les salles $8$ et $11$ ne sont pas connectées. On peut donc améliorer cette majoration en remplaçant, dans l’une des couches à plusieurs salles, la meilleure salle par la deuxième meilleure salle, de façon à minimiser le nombre d’oeuvres perdues :
  $n \leq 46 - min(6-4, 12-10, 8-5, 11-9)$, soit $n \leq 44$.

  Conclusion : $n=44$ et le chemin $[2,6,12,8,9,7]$ est optimal.

  Répondre à ce message
• Septembre 2016, 2e défi

  le 9 septembre 2016 à 08:54, par Al_louarn

  Précision : pour trouver ce chemin j’ai utilisé un algorithme glouton. A chaque étape on choisit la meilleure seule entre celle située au sud (si elle existe) et celle située à l’est (si elle existe) de la salle courante. Comme le musée est un rectangle $3 \times 4$ dont l’entrée et la sortie sont respectivement situés aux coins nord-ouest et sud-est, on obtient à coup sûr un chemin passant par exactement $3 + 4 - 1 = 6$ salles. L’algorithme ne trouve pas toujours un chemin optimal, mais donne déjà un bon minorant de $n$.

  Répondre à ce message
• Septembre 2016, 2e défi

  le 9 septembre 2016 à 18:50, par Daniate

  Bonsoir,

  Vous pouvez obtenir le chemin optimal avec l’algorithme de Dijsksta en remplaçant le nombre de salles par leur complément à 12 (par exemple). Mais n’est-ce pas écraser une mouche avec un marteau pilon ?

  Il n’y a que 10 chemins et sachant qu’un chemin peut être amélioré en remplaçant une salle par celle qui lui est contiguë en diagonale SO-NE, on supprime rapidement 1, puis 3, puis 4, puis 10. Il reste 2 chemins puisque 5-9 est inférieur à 5-11 et comme 8+9>5+11 il vient 2-6-12-8-9-7.

  Répondre à ce message
• Septembre 2016, 2e défi

  le 10 septembre 2016 à 12:48, par Niak

  Puisque vous parlez d’approches gloutonnes (c’est également le cas de Dijkstra), il me semble que l’approche algorithmique la plus appropriée pour ce problème reste la programmation dynamique. Dans la mesure où l’on ne peut visiter que 6 salles, il faut à chaque pas aller vers la droite ou le bas. Si l’on note $a_{i,j}$ les valeurs de la matrice de l’énoncé, remplissons (par exemple ligne après ligne) une nouvelle matrice dont les valeurs vérifient $b_{i,j} = a_{i,j} + \max(b_{i-1,j},b_{i,j-1})$ (prendre $0$ pour les valeurs dont les indices sortent du tableau). En décorant de plus ces valeurs d’une flèche indiquant la direction d’où provient le $\max$ de la formule, on obtient :

  $[2, \rightarrow 6, \rightarrow 9, \rightarrow10]\\ [\downarrow 8, \rightarrow 20, \rightarrow 25, \rightarrow 36]\\ [\downarrow 18, \downarrow 28, \rightarrow 37, \rightarrow 44]$

  Chaque case contient la somme maximale d’un chemin jusqu’à elle-même depuis l’entrée. Pour retrouver le chemin optimal (unique ici), il suffit de remonter les flèches depuis la case finale.

  Répondre à ce message
• Septembre 2016, 2e défi

  le 13 septembre 2016 à 09:38, par Daniate

  Bonjour,
  Merci pour votre remarque qui me permet de découvrir une technique que j’ignorais et qui est pleine de bon sens. L’algorithmique m’est tombé dessus dans mes dernières années d’enseignement sans que j’y trouve le moindre plaisir, le pensum Dijkstra étant au programme je l’ai assimilé mais sans aller plus loin.

  Répondre à ce message