Discussion :

[mistify]

Bonjour,

Je dois consevoir un programme qui doit résoudre des problèmes de transport simple.
C'est pour un cours de recherche opérationnelle et aide à la décision.

Aprés avoir trouver une solution initiale, le tableau des potentiels et des coûts réduits de cette solution, on doit appliquer l'algorithme de "Stepping Stone".

Cette algorithme est trés simple à utiliser sur une feuille de papier.
En effet ce problème peut être modélisé par un arbre.
L'optimisation consiste à ajouter un arc à cet arbre, cet arc permet de former un cycle.
Je connais les noeuds où cet arc doit s'imbriquer mais je n'arrive pas par programme à trouver toutes les coordonnées des arcs qui forment mon cycle nouvellement créé.

Ma question est donc la suivante :
Quelqu'un connait il l'algorithme de stepping stone? si non est ce que vous auriez une idée sur un algorithme qui permettrait de trouver le cycle en connaissant le point d'origine?

Merci.

[mr_samurai]

Salut,

Un arbre est un graphe qui part du sommet vers les feuilles: bonc tes arcs dispose d'une orientation naturelle vers le feuilles. Ainsi si tu branche deux feuilles (arc entre deux noeuds), il te suffit de remonter les branche jusqu'a trouver un noeud commun (ou arriver au sommet qui est bien sur un noeud commun)

si tu considére tous les noeuds qui t'en permis de remonter depuis les deux noeuds les plus bas, tu tiens ton cercle.

++