Forum Prepas.org

Dreamsnet a écrit :Enfin, je suis curieux de voir ton approche =)

J'ai maté la méthode rétroactive, et je m'en inspire par moment, mais sinon c'est surtout beaucoup de réflexion et de modélisation.
J'utilise un tableau à 10 colonnes et 2 lignes pour modéliser un jour de la manière suivante :

Jour X : Nb de personne au point de départ.
Case 1 = Nb de personne à 20km. // Cases 2 = Nb de personne à 40km. // ... // Case 9 = Nb de personne à 180km. // Cases 10 = Nb de personne arrivée.
Nb de litre restant.................. // Nb de litre restant................... // ... // Nb de litre restant................... // Nb de litre infini.

L'idée est simple, durant le voyage il faut minimiser le nombre de personne et maximiser le nombre de litre.
Après faut tester, et en permanence essayer d'améliorer, d'ailleurs j'y retourne.

Edit : Puis je marche aussi par séquence d'envoie.
On peut voir par exemple qu'il est impossible d'envoyer deux personnes à la fois dès le début.
On cherche donc à en envoyer 1, on trouve ce moyen ci (en remontant en fait de la fin).
5 partent du départ / 5 à 20km et 100L / 4 à 40km et 75L / 3 à 60km et 55L / 2 à 80 km et 40L / 2 à 100km et 30L / 1 à 120km et 20L / ...
Les autres partent plus tard pour récupérer ceux qui ont été abandonné avec juste 5L.

Ensuite on la peaufine, on se rend compte que ne pas utiliser les autres dès le début, c'est dommage (mais qu'il est très dur de les utiliser).
On remarque que le groupe de 4 et de 3 peuvent porter 5L supplémentaire. Donc on va initialement en envoyer 6 pour "gagner" 5L dans le raisonnement.

Etc... C'est long, c'est dur, c'est chiant.

Salut,
Pour ce genre d'exercice tres calculatoire il me semble qu'il faille programmer. Une methode tres bourrine est la suivante. On fait le graphe de tout les etats possibles. Ou plutot on demande a l'ordi de le faire. On considere alors si oui ou non il y a une arete entre deux etats donnes. Cela se fait en fonction des lois que l'on donne a l'ordinateur. On obtient alors une matrice symetrique. C'est notre matrice de passage: a chaque iteration du processus il suffit de multiplier le vecteur initial par cette matrice. On continue jusqu a obtenir notre vecteur final souhaite, il suffit alors de regarder quel chemin notre algorithme a parcouru. On le compare en duree a celui stocke. S il est plus court, on le garde.

Je ne suis pas sur qu il faille reflechir avec du papier et un crayon sur ce genre de probleme, on ne pourra jamais etre sur d'obtenir un resultat optimal, ni meme un resultat tout court.

supelecien a écrit : Je ne suis pas sur qu il faille reflechir avec du papier et un crayon sur ce genre de probleme, on ne pourra jamais etre sur d'obtenir un resultat optimal, ni meme un resultat tout court.

Pas d'accord, si c'est résoluble par un ordinateur, c'est résoluble par un humain avec du papier et un crayon. Suffit "au pire" à réfléchir comme un ordinateur.
Personnellement, ma résolution du problème avance, et je pense que mon début est le début idéal.

Effectivement, il s'agit d'un arbre des possibilités, parfois c'est très dur on ne peut choisir entre diverses branches avant un grand nombre d'étapes, mais pas là.
Lorsque l'on compare deux (débuts de) solutions, on se rend très vite compte laquelle est la meilleure.

Edit : Ma résolution avance, au bout de 24 jours, il me reste 3 personne à faire passer (c'est la fin le plus dur !).
Edit² : Première résolution, sauf erreur, j'y arrive en 44 jours, il me reste à vérifier/améliorer.
Edit²² : Une superbe amélioration arrive, dans celle-ci, au bout de 24 jours, il n'en reste qu'un !
Edit²²² : La voilà, maintenant je le fais en 36 jours ! Je referais une vérification avant de la poster.

Voilà le fichier pdf avec ma solution : http://www.pdfhost.net/index.php?Action ... c19e7b8af2

Je suis d'accord, ta solution semble marcher,
Mais comment être sur que ta solution est optimale?
Y-a-t-il une méthode de raisonnement particulière?

C'est peut être là que l'ordinateur devient "indispensable" aux mathématiques...
Un grand débat philosophique que la valeur des démonstrations par ordinateur!

F0U a écrit :Je suis d'accord, ta solution semble marcher,
Mais comment être sur que ta solution est optimale?
Y-a-t-il une méthode de raisonnement particulière?

C'est peut être là que l'ordinateur devient "indispensable" aux mathématiques...
Un grand débat philosophique que la valeur des démonstrations par ordinateur!

J'ai fait tout mon possible pour qu'elle soit optimale, à coup de rétroaction et tout.

Typiquement, au début, on regarde si on peut en envoyer 2.
Pour cela on pars du 10ème jour :
- Si 2 arrivent le 10ème jour, le 9ème ils avaient fait 180km et ils leur restaient 10L.
- Si 2 étaient à 180km avec 10L le 9ème jour, le 8ème ils avaient fait 160km et ils leur restaient 20L.
- ...
- On remonte jusqu'à 100km avec 2 types et 50L => Impossible, ils ne peuvent arriver avec 50L
Donc à 100km, ils sont 3 avec 55L (le 3ème fera demi tour avec 5L pour rejoindre d'autres qui viendront le sauver).
- Donc 3 à 80km avec 70L => Impossible, de même ils sont alors 4 avec 75L.
- Donc 4 à 60km avec 95L => Impossible, de même ils sont alors 5 avec 100L.
- Donc 5 à 40km avec 125L => Impossible, de même ils sont alors 6 avec 130L => Impossible, de même ils sont 7 avec 135L.
- Donc 7 à 20km avec 170L => Impossible, de même ils sont alors 8 avec 175L => Impossible, de même ils sont 9 avec 180L.

Ensuite dans l'autre sens, on voit qu'on en utilise que 9 donc, si on pars avec les 10 au lieu de 9, on gagne 15L
(Le 10ème consomme 5L pour faire 20km et 5L pour revenir) au bout de 20km. Il reste à voir comment les optimiser (pour cela il ne faut pas changer le nombre de gens qui bougent, juste éventuellement augmenter la quantité d'eau transportée car plus quelqu'un va loin plus il consomme d'eau "inutilement" et plus de l'eau va loin et plus elle a de la valeur pour la raison qui précède justement).

Donc on part à 10 avec 200. Puis 7 à 40km avec le maximum = 7*20 = 140. On observe qu'on gagne 5L (en fait les 10 litres doivent être ramenés par les 3 autres qui vont au départ car ils ne servent à rien). Il faut ensuite déterminer si on peut emmener ces 5L encore plus loin, la réponse est non car à 40km, ils y a 5 gars avec 100L, leur maximum (En fait il faut différencier maximum de départ = 25L et maximum d'arrivée = 25 - 5 = 20L). Dont le seul intérêt de ces 5L c'est que les 2 gars qui font demi tour de 40km à 20km arriveront avec 5L au lieu de 0L. On vient d'optimiser le trajet.

Ensuite, il faut voir si ce trajet est viable, pour cela il faut récupérer tous les mecs isolés qui ont fais demi tour et qui sont à sec. On trouve normalement que c'est impossible. Voilà, on vient de montrer que l'on ne peut pas faire passer 2 type dès le début. Il suffit de refaire tout ça avec 1, on aura optimisé le premier envois.

Ensuite le deuxième envoi, ne pars pas le 2ème, ce n'est pas viable, mais le 3ème jour comme cela on récupérer les types abandonnés lors du premier trajet. On refait la même méthode (pas besoin de tester 2, comme on récupère des gens, on consomme plus, donc au mieux on en fait passer 1) sachant que là le type arrivé peut faire demi tour avec 20L donc on gagne 20km.

Etc, c'est ce que j'ai essayé de faire à chaque fois.
Après, l'erreur est humaine, surtout sur ce genre de problème.
Mais on va dire qu'au pire, je ne me suis pas trompé de beaucoup de jour.

Et si chaque personne se rationnait à 2 L d'eau/j au début sur les 4 premiers jours, puis 2.75/j sur les 4 suivants puis 3/j sur les deux derniers ?
On arrive à dix jours, et sans allers retours fastidieux. x)

@ napfy : 10 jours, 10 personnes, ça fait 50L d'eau par personne, et seulement 25 litres d'eau emportables, à moins que tu connaisses une méthode de déplacement extrême, le non stop ligne droite reste le plus rapide, et ces pauvres gens n'auront plus d'eau au bout de 5 jours...
Tu parles de demi tours, qui rallongent d'autant le temps d'épreuve.
Je pense qu'il faut au moins 25 jours pour faire le trajet.

@ Thaalos: J'avais mal lu l'ennoncé et m'en excuse. J'avais supposé comme en gestion de Projet plusieurs equipes se relayant pour rendre le projet au bout de 10j. Sinon, j'ai trouvé le probleme passionnant, la solution de Deviling interessante, que je vais reprendre (dès que j'aurai un peu de temps), pour voir si la solution pourra être améliorée.
Idée c'est de reprendre un système à 10 piles attachées à chaque personnage. Voir si en faisant partir tout le monde, faire arriver P10 au bout de 10 jours, chaque relayeur sera amené à effectuer des trajets (positif ou négatif), de manière à optimiser le temps total, c'est ce qui m'avait fait penser à PERT.
Si on arrive à modeliser, ça sera interessant de faire le lien avec les chemins hamiltoniens. D'ici là toutes les idées sont les bienvenues.
A+