Salut !

J'ai un exercice à faire en Java, voilà un résumé de l'énoncé :
En gros, on a 4 personnes, qu'on appellera A,B,C,D qui doivent traverser un pont fragile et dans l'obscurité.
Comme il est fragile, seules 2 personnes au maximum peuvent passer en même temps, et comme il fait noir, l'un des deux doit porter une lanterne, pour ensuite revenir chercher les autres.
Chaque personne a son propre temps de passage : A=1 min ; B = 2 min ; C = 5 min ; D = 10 min.
Ils doivent passer le plus vite possible, et quand deux personnes vont en même temps, elles avancent au rithme du plus lent.
Je dois résoudre ce problème avec des structures comme les files (queues), piles (stacks), listes, arbres, arbres avec données (network) et d'autres.
J'ai déjà fait quelques calculs à la main et, normalement, le temps minimum est de 19 minutes, mais je ne sais pas trop comment représenter en code ce problème pour arriver au même résultat, voir même un algorithme qui prend en compte toute les possibilités, sachant que je sur à 99% que je devrais utiliser des arbres avec données ... Si vous avez quelques conseils sur comment calculer le temps minimum, je dis pas non merci beaucoup !

Ce n'est pas un probleme de java que tu as, c'est un probleme d'algo. Ce truc ressemble soi a un probleme de plus court chemin, soit a un probleme de programmation dynamique.

Merci de ta réponse
C'est que mettre toute les possibilités dans un seul arbre, ça peut être confus au final, donc j'avais pensé à faire 6 arbres avec au début les 6 premières possibilités ("A" qui part avec "B", A-C, A-D, B-C, B-D, C-D) , et calculer le chemin le plus court pour chaque arbre et comparer les résultats mais j'ai peur que ce soit considérer de la triche ...

Je fabriquerait un graphe ou chaque arc est un trajet, sachant que ce sera normalement le plus rapide des 2 qui fera le chemin inverse tu peux éliminer pas mal de possibilité en le construisant, ensuite un petit coup de djikstra et ça devrait le faire.

Enfin pour parler de la manière un peu jolie, avec seulement 4 éléments c'est peanuts en force brute.

Tu dois déjà déterminer le "passeur" (qui porte la lampe), qui est le (ou un ds plus rapides en cas d'égalité). Les autres sont les passagers.

Ensuite, tu peux calculer le temps nécessaire : sommeTempsPassagers + (NombreDePassagers-1)*TempsPasseur.
(sauf s'il y a qu'un seul type qui veut traverser, dans ce cas c'est simple...)

Mais apparemment ton prof doit s'attendre à ce que tu utilises des structures de données. Par ex une queue pour les passagers trié dans un ordre quelconque (vu que ca change absolument rien, sauf si tu veux trouver l'ensemble des solutions optimales et non une seule).
Et un stack pour mémoriser les ordres d'aller-retours.
Tu prends le prochain passager qui traverse avec le passeur, et tant qu'il reste des passagers, le passeur retourne le chercher.
Et pour avoir le temps total il suffit d'additionner les temps des allers (qui dépend du passager) et des retours (qui est toujours celui du passeur).

edit : et une autre queue pour mémoriser les aller-retours plutôt.