Programme du problème du pont.

[invite6abbb010]

Bonjour,

Je cherche à écrire un programme ou un algorithme(mais je n'y arrive pas) pour résoudre le problème dit de la traversée du pont dont voici l'énoncé:

Quatre voyageurs V1, V2, V3 et V4 sont sur la rive gauche d'une rivière à côté d'un pont fragile qui ne peut pas supporter le poids de plus de deux voyageurs à la fois. Ils souhaitent se rendre sur la rive droite de la rivière. Il fait nuit et ils ne disposent que d'une torche lumineuse indispensable à la traversée du pont. Il n'est pas possible de lancer la torche et donc celle-ci doit faire des allers et retours pour permettre le passage des voyageurs en plusieurs fois, des voyageurs traversant la rivière de droite à gauche pour ramener la torche.

Les voyageurs ont des capacités physiques différentes : le premier traverse en une minute (t1 = 1), le second a besoin de deux minutes (t2 = 2), le troisième de cinq minutes (t3 = 5) et le quatrième de dix minutes (t4 = 10). Bien sûr, quand deux voyageurs traversent ensemble, le plus lent impose sa vitesse. Comment les voyageurs doivent-ils organiser leurs traversées pour faire au plus vite et ainsi économiser l'énergie de leur torche ?


Merci de votre aide.
-----

[invite896757ff]

Logiquement, le plus rapide tiendra la torche et donc accompagnera les trois autres.
Le problème c'est de faire un paramètre de la traversée du pont.

[invite6c250b59]

Non, la solution optimale n'implique pas nécessairement que ce soit toujours le plus rapide qui revienne avec la torche:
1&2 traversent, 1 revient avec la torche
5&10 traversent, 2 revient avec la torche
1&2 traversent

Pour le trouver avec un programme, la stratégie la plus simple me semble de tester toutes les possibilités, soit de façon systématique soit de façon aléatoire.

[raymolk]

Je connais mal ces problèmes personnellement, car ma formation est plus continue que discrète, mais il s'agit d'un problème de plus court chemin dans un graphe (https://fr.wikipedia.org/wiki/Probl%...s_court_chemin), dont les poids sont tous positifs, donc l'algorithme indiqué semble être Dijkstra : https://fr.wikipedia.org/wiki/Algorithme_de_Dijkstra
L'article est mal écrit par endroits, mais la figure intitulée « Animation d'un algorithme de Dijkstra » permet de vite comprendre le principe, et la section « Implémentation de l'algorithme » est bien détaillée.

[A voir en vidéo sur Futura]

[invite896757ff]

Non, la solution optimale n'implique pas nécessairement que ce soit toujours le plus rapide qui revienne avec la torche:
1&2 traversent, 1 revient avec la torche
5&10 traversent, 2 revient avec la torche
1&2 traversent

Pour le trouver avec un programme, la stratégie la plus simple me semble de tester toutes les possibilités, soit de façon systématique soit de façon aléatoire.

Comme la contrainte est le temps, il n'y a qu'une seule solution: Le 1 tient et garde la torche.
Ne reste qu'à le prouver.

[invite896757ff]

Comme la contrainte est le temps, il n'y a qu'une seule solution: Le 1 tient et garde la torche.
Ne reste qu'à le prouver.

Et pour le prouver il suffit de faire des additions.
Un algo qui fait des additions ça doit pas être trop compliqué.

[invite6c250b59]

Ne reste qu'à le prouver.

...au cas où tu ne l'ai pas remarqué, je viens juste de te prouver qu'on peut faire mieux (10+1+5+1+2 pour ta suggestion, 2+1+10+2+2 pour la mienne).

[raymolk]

@goaoute : je crois que tu sous-estimes grandement la difficulté de ce genre de problèmes (et leur complexité algorithmique).

[pm42]

Comme la contrainte est le temps, il n'y a qu'une seule solution: Le 1 tient et garde la torche.
Ne reste qu'à le prouver.

Comme d'autres l'ont fait remarquer, lire les réponses des autres éviterait d'affirmer des choses fausses. D'autant qu'on trouve facilement des analyses détaillées qui montrent que le problème est vraiment très loin d'être aussi simple : https://pdfs.semanticscholar.org/3ea...aa379bc0ae.pdf

A programmer, c'est intéressant et d'après la page Wikipedia anglaise, ce problème a servi à essayer de montrer la supériorité d'Haskell sur Prolog dans ce genre de cas.
Si quelqu'un a envie de creuser, là je fais une crise de flemme (et je suis rouillé en Prolog et à peine débutant en Haskell ce qui explique la flemme).

[invite896757ff]

Traversée de V2: t2+t1 (retour de la torche)=3
Traversée de V3: t3+t1=6
Traversée de V4: t4+t1=11
Traversée de V1: 1
Temps total: 21
Toute autre combinaison donnera un temps total supérieur.

[invite896757ff]

Traversée de V2: t2+t1 (retour de la torche)=3
Traversée de V3: t3+t1=6
Traversée de V4: t4+t1=11
Traversée de V1: 1
Temps total: 21
Toute autre combinaison donnera un temps total supérieur.

Emporté par l'élan V1 fait une traversée de trop puisque avec la traversée de V4 il est déjà de l'autre côté
Et donc, temps total=20
Je mets au défi quiconque de faire mieux, à savoir plus rapide.

[Antoane]

Bonjour,

La réponse t'a déjà été donnée en message 3, puis encore en message 7, montrant que tu te trompes.

[invite44510b00]

Et pour le prouver il suffit de faire des additions..

Ce qui semble vous poser des problèmes, vu vos affirmations aussi péremptoires que fausses ......

[invite896757ff]

Bonjour,

La réponse t'a déjà été donnée en message 3, puis encore en message 7, montrant que tu te trompes.

Jiav du msg 3 qui dit: "5&10 traversent, 2 revient avec la torche"; n'a pas bien lu l'énoncé qui dit que le pont ne peut supporter que deux personnes. => Jiav-->Out.
Quand à ça-->: "je viens juste de te prouver qu'on peut faire mieux (10+1+5+1+2 pour ta suggestion, 2+1+10+2+2 pour la mienne)" c'est juste n'importe quoi.
Alors présentez vos solutions en termes de traversées dûment explicitées comme je l'ai fait.

[Antoane]

Bonjour,

On est donc 4 ou 5 à affirmer que les explications de Jiav sont bonnes et tu ne cherches pas à te remettre en question ?

Jiav du msg 3 qui dit: "5&10 traversent, 2 revient avec la torche"; n'a pas bien lu l'énoncé qui dit que le pont ne peut supporter que deux personnes.

Le n°2 a traversé le pont à l'étape précédente. Il peut donc revenir, seul, de l'autre côté.

Quand à ça-->: "je viens juste de te prouver qu'on peut faire mieux (10+1+5+1+2 pour ta suggestion, 2+1+10+2+2 pour la mienne)" c'est juste n'importe quoi.

Tu n'as pas compris : il s'agit de sommer les temps de parcours des différentes étapes - je ne vois pas ce que tu ne comprends pas :
1&2 traversent : demande un temps égal à 2
1 revient avec la torche : demande un temps égal à 1
5&10 traversent : demande un temps égal à 10
2 revient avec la torche : demande un temps égal à 2
1&2 traversent : demande un temps égal à 2

Sachant que "x&y traversent" signifie que "les voyageurs associés aux temps de trajet x et y traversent"

[invite9dc7b526]

quand goaoute prendra le temps de réfléchir il comprendra n'en doutons pas.

ce qui n'est pas si facile c'est de démontrer que la solution de Jiav est optimale (sans lister toutes les possibilités).

[invite896757ff]

Bonjour,

On est donc 4 ou 5 à affirmer que les explications de Jiav sont bonnes et tu ne cherches pas à te remettre en question ?


Le n°2 a traversé le pont à l'étape précédente. Il peut donc revenir, seul, de l'autre côté.


Tu n'as pas compris : il s'agit de sommer les temps de parcours des différentes étapes - je ne vois pas ce que tu ne comprends pas :
1&2 traversent : demande un temps égal à 2
1 revient avec la torche : demande un temps égal à 1
5&10 traversent : demande un temps égal à 10
2 revient avec la torche : demande un temps égal à 2
1&2 traversent : demande un temps égal à 2

Sachant que "x&y traversent" signifie que "les voyageurs associés aux temps de trajet x et y traversent"

Voilà, expliqué comme ça, ça me va. Jiav est pour moi réhabilité.

[invite51d17075]

ce qui n'est pas si facile c'est de démontrer que la solution de Jiav est optimale (sans lister toutes les possibilités).

non, mais
on peut s'appuyer sur deux principes qui semblent objectifs.
1) ceux qui reviennent doivent être les plus rapides
2) que 5 et 10 fassent la traversée ensemble

le point 1) implique qu'ils partent les premiers pour pouvoir revenir ensuite chacun leur tour.
la suite découle du 2)

[invite9dc7b526]

oui mais tu te bases sur des principes heuristiques, ça n'est pas exactement une démonstration (dont je ne sais pas si elle existe, hors listage de toutes les possibilités).

[raymolk]

L'algorithme de Dijkstra dont je parle en #4 fourni une solution optimale (pas unique en général, et en particulier pas unique pour ce problème), car il minimise le chemin parcouru (ici le temps de parcours) à chaque itération, sans lister tous les chemins.

[invite51d17075]

Edit:croisement.
Tout à fait, malheureusement
Une démo propre doit pouvoir se construire sur la base de la suggestion de Raymolk ( post #4).
la (les) théorie(s) des graphes , ça date vraiment pour moi !!!

[pm42]

Voilà, expliqué comme ça, ça me va. Jiav est pour moi réhabilité.

On peut noter qu'il n'en avait nul besoin et que tu avais tort depuis le début. 6 messages à répéter un truc faux et à ne pas faire attention à ce que tous les autres te disent et à ne pas chercher sur Internet où on trouve très vite confirmation de ton erreur est une attitude qui revient à pourrir le fil.

Une démo propre doit pouvoir se construire sur la base de la suggestion de Raymolk ( post #4).
la (les) théorie(s) des graphes , ça date vraiment pour moi !!!

Outre l'article que j'ai donné qui propose des choses intéressantes, on trouve aussi quelque chose ici : https://en.wikipedia.org/wiki/Bridge_and_torch_problem

[invite51d17075]

bien vu le lien....
pile sur la problématique !

[invite51d17075]

à noter que les deux principes que j'avance sont exactement les mêmes que dans la rubrique : "semi formal approach"

[invite896757ff]

On peut noter qu'il n'en avait nul besoin et que tu avais tort depuis le début. 6 messages à répéter un truc faux et à ne pas faire attention à ce que tous les autres te disent et à ne pas chercher sur Internet où on trouve très vite confirmation de ton erreur est une attitude qui revient à pourrir le fil.

Oui bon, je doit pas être seul à ne pas avoir capté la subtilité du "5+10=10".

[pm42]

Oui bon, je doit pas être seul à ne pas avoir capté la subtilité du "5+10=10".

Jiav avait donné dès le message #3 une description en toutes lettres qui permettait à n'importe qui de comprendre et de faire le calcul.
Tu as répété 6 fois un truc faux sans la lire ni les objections et les liens donnés, tu n'as jamais précisé ton "raisonnement", il a fallu que tu sois signalé à la modération pour t'en rendre compte...

Est ce que tu vois le problème ou vraiment pas ? Voici une image pour l'expliquer :