Nombre de déplacements minimal

[invitecb85cdda]

Bonjour,
Je dois résoudre un exercice et je suis coincé :
Il s'agit d'un cercle dont la circonférence est divisée en N cases. Pour chacune des cases je devrais trouver le nombre de mouvements minimum pour aller de la case 1 à la case n (n allant de 1 à N).
Il y a trois types de déplacements :
- avancer un cran à droite
- reculer d'un cran vers la gauche
- emprunter un tuyaux qui se trouve sur la case

En effet, je possède un tableau qui à chaque case attribue le nombre de cases qu'elle me fait avancer vers l'avant si j'emprunte le tuyau qui se trouve sur celle ci.

Je pense que je me casse trop la tête à essayer de déterminer un chemin alors qu'il suffit de trouver le nombre de mouvements.
J'ai pensé a l'algo de Dijkstra, mais étant donné que lorsque je me trouve sur la dernière case numéroté je peut me déplacer vers la case 1 (on revient en arrière dans le graphe ?) je pense donc que cet algo n'est pas utilisable ici.

Auriez vous une idée quant a la façon de résoudre ce problème ?
-----

[invitef35ebd48]

Bonjour,

Pourtant l'algo de Dijkstra devrait marcher il m'a l'air de répondre complètement à ton problème.

mais étant donné que lorsque je me trouve sur la dernière case numéroté je peut me déplacer vers la case 1 (on revient en arrière dans le graphe ?) je pense donc que cet algo n'est pas utilisable ici.

Si tu pars de la case 1 et que tu reviens à la case 1 pendant une recherche de chemin...tu peux laisser tomber ce chemin et passer au suivant. Normalement l'algo ne te fais pas passer 2 fois par le même noeud.

[RiketRok]

Djikstra marche très bien ! En fait, revenir à la case départ en faisant le tour, ça revient à revenir sur une case déjà visitée, et donc à stopper l'algo (ou plutôt l'instance de l'algo qui serait tombée dessus.).

Tu as déjà ton nombre maximal de coups : n - 1 ou N - n + 1. Donc pas de soucis de se retrouver dans un labyrinthe sans issue.
Il te reste à effectuer tous les déplacements possibles, sans jamais retourner en arrière.

Tu commence sur la case 1 : premier tour : 1 instance de l'algo va à gauche. 1 autre instance va à droite. 1 dernière prend le tuyau si il y en a un.
deuxième tour : celui qui est allé à gauche ne peut aller à droite car il en vient. Il va créer deux nouvelles instances : gauche, et tuyau.
...

[Jack]

Il s'agit d'un cercle dont la circonférence est divisée en N cases.

La surface plutôt, non?

[A voir en vidéo sur Futura]