Besoin d'aide sur un problème de graphe
Bonjour à tous
Je suis face à un problème de la vie réelle qui peut être pensé de la manière suivante.
- Disons que l'on veut parcourir toutes les villes d'une région donnée pour y livrer des sacs de sable.
- Chaque ville doit être visitée une seule fois.
- Nous sommes obligés de partir d'une certaine ville de départ.
- Lorsque l'on commence sur cette ville de départ, nous disposons de x sacs de sable.
- Toutes les villes sont connectées les unes aux autres par des routes (tous les nœuds sont liés aux autres dans les deux sens sauf le premier nœud duquel on ne peut que partir).
- Lorsque l'on arrive dans une ville on livre certains clients (on perd des sacs de sable) mais on récupère d'autres sacs de sable par du ravitaillement.
Le problème est le suivant : quel est le meilleur chemin tel que à n'importe quel moment pendant le parcours je porte sur moi le moins de sacs de sable possible (pour ne pas que ce soit trop compliqué à transporter) ?
Auriez-vous des pistes/idées/algorithmes que vous connaissez qui se rapprochent de ce problème pour m'aider à le résoudre ?
Merci pour votre aide.
Je suis face à un problème de la vie réelle qui peut être pensé de la manière suivante.
- Disons que l'on veut parcourir toutes les villes d'une région donnée pour y livrer des sacs de sable.
- Chaque ville doit être visitée une seule fois.
- Nous sommes obligés de partir d'une certaine ville de départ.
- Lorsque l'on commence sur cette ville de départ, nous disposons de x sacs de sable.
- Toutes les villes sont connectées les unes aux autres par des routes (tous les nœuds sont liés aux autres dans les deux sens sauf le premier nœud duquel on ne peut que partir).
- Lorsque l'on arrive dans une ville on livre certains clients (on perd des sacs de sable) mais on récupère d'autres sacs de sable par du ravitaillement.
Le problème est le suivant : quel est le meilleur chemin tel que à n'importe quel moment pendant le parcours je porte sur moi le moins de sacs de sable possible (pour ne pas que ce soit trop compliqué à transporter) ?
Auriez-vous des pistes/idées/algorithmes que vous connaissez qui se rapprochent de ce problème pour m'aider à le résoudre ?
Merci pour votre aide.
Connectez-vous ou Inscrivez-vous pour répondre.
Réponses
Avant d'espérer de l'aide, il faut que tu définisses mieux le problème. Là, il y a des choses importantes que tu n'as pas dites. Tu parles de plus court chemin dans le second message, alors que tu ne parles pas de distance dans le premier, ça pose un problème. En plus tu n'as pas dit si il fallait faire une boucle ou si tu t'arrêtes dés que tu es arrivé sur la dernière ville où tu n'étais pas allé.
Par ailleurs, on ne sait pas exactement qu'est-ce que tu cherches à minimiser, est-ce:
- Le stock maximal que tu auras a transporter sur une arête du chemin? (j'en doute).
- La somme des stocks à transporter sur chaque arête du chemin?
- La somme des produits stock $\times$ distance sur chaque arête du chemin?
- Un autre truc qu'on n'a pas défini?
Si c'est le deuxième, je crois que l'idée de base à adopter est de chercher à se garder autant que possible les villes apportant le plus de stock pour la fin (en définissant l'apport de stock comme la différence entre le nombre de sacs récupérés et le prix d'entrée).
Si c'est le troisième, ça doit être aussi galère que le voyageur de commerce, avec des subtilités supplémentaires (cela dit elles apportent aussi des contraintes, je ne saurai donc dire si ça augmente ou diminue le temps de calcul), par exemple, le plus court chemin sera très mauvais si il t'oblige à passer en premier lieu par une ville qui rapporte beaucoup trop (tu devras alors te taper un excès de stock tout le long).
Merci pour ton aide.
Alors c'est bien le problème numéro 1: je veux minimiser le nombre de sacs maximal que j'ai sur mon chariot en gros. J'ai utilisé la métaphore du sac mais en réalité il s'agit d'un problème d'informatique je cherche à utiliser le moins de RAM possible pendant mon traitement.
Sinon pour le chemin en lui-même je veux passer par toutes les villes une seule fois, sans boucle, donc oui je m'arrête sur la dernière ville.
Pour le moment mon idée serait de chercher à minimiser la différence de chargement entre deux étapes. Je veux décharger et charger au minimum à chaque étape. Si on défini le delta de chargement comme le poids sur les routes, alors on peut faire un plus court chemin.
Pourquoi ne pas avoir défini directement ton problème ? Tu as obscurci la question avec ton image. Tu aurais pu dire que tu as un certain nombre de tâches à exécuter, indépendantes (*), qui ont un effet sur l'occupation de la RAM (vidage partiel et/ou remplissage), et que tu cherches un algorithme d'exécution séquentielle qui minimise l'occupation de la RAM. C'était tout aussi compréhensible.
Et si ce n'est pas ça, à toi de définir clairement.
Cordialement.
(*) sinon, le parcours ne sera plus libre
Option 1 : un trajet où le voyageur devrait faire 1000km, avec en permanence une charge de 200kg
Option 2 : un autre trajet où le voyajeur devrait faire 500km, avec en permanence une charge de 100kg, mais avec une portion de 10km avec une charge de 201kg
Si pour une configuration donnée, on doit choisir entre ces 2 options, tu vas préférer l'option 1. C'est bien ça ?
Merci pour vos commentaires.
J'ai avancé un peu dans le problème et je pense avoir trouvé la solution, cependant peut-être peut-on formuler le problème d'une autre manière ce qui permettrait l'usage d'un meilleur algorithme (plus rapide à éxecuter at least).
Je vous réponds dès que possible.
A bientôt,
PS: gerard0 effectivement c'est un problème d'informatique mais ce forum est un forum de maths, c'est pourquoi je n'ai pas voulu présenter directement ma problématique; pour que l'on se concentre sur le problème de maths en lui-même. Si je dois expliquer le background et tout le contexte on n'est pas sortis et je risque de perdre des gens c'est pourquoi je me suis dis que pour poser ma question c'était mieux de modéliser le problème pour mieux le résoudre. De plus le problème sur lequel je planche est plus complexe que ça c'est juste "une partie" du problème, mais c'est cette partie qui m'intéresse.
Cordialement.
Note aux modérateurs:
Je pense que ça ne sert à rien de garder the thread actif. Vous pouvez clore la discussion et la marquer comme `résolue` si c'est comme cela que vous fonctionnez.
2) On ne ferme pas les sujets ici, même quand l'auteur a été irrespectueux.
Dans ton dernier message, ce que je comprends, c'est qu'à chaque NOEUD, la charge doit varier le moins possible ; ce qui n'a rien à voir avec la première version.
Et je t'ai posé il y a 2 jours une question que je pensais claire et précise, mais tu n'as pas répondu à cette question.
Après, tu t'étonnes de ne pas avoir de solution.