Discussion :

[camelia136]

Bonjour,

je recherche un algorithme qui me permettra de passer de plusieurs nœuds à un seul nœuds final tout en respectant le fait que chaque segment reliant 2 nœuds possède une capacité ce qui empêche le segment d'être utiliser plusieurs fois

Par exemple pour passer des nœuds 1, 2, 3, 4,11 au nœud 17





On a les trajets

[1, 5, 9, 17]
[2, 6, 5, 9, 17]
[3, 7, 8, 10, 9, 17]
[4, 8, 10, 9, 17]
[11, 14, 9, 17]

Comme on peut voir le segment [9,17] est utilisé 5 fois si sa capacité est réduite à 5
Le segment [5,9] a une capacité égale à 3
Le segment [10,9] a une capacité égale à 4
Le segment [14,9] a une capacité égale à 5
la même chose pour le segment [5,9],[8,10] qui sont utilises plusieurs fois

J’ai choisi d'utiliser un recuit simulé et à chaque diminution de température je choisi un trajet selon quelques critères

Ma question est comment pourrais-je avoir les trajets les plus optimaux pour aller des nœuds 2, 3 ,4 11 au nœud 17 sachant que j’ai un code qui me permet de trouver différents trajets possible entre 2 nœuds.

[Acrim]

Ton problème semble être juste un problème de flot maximum, non ?
Ton nœud d'arrivée est ton nœud puits. Tu ajoutes un nœud source relié à tes nœuds de "départ" avec des arcs de capacité 1. Et voilà....

Si en plus tes graphes sont acycliques n ça devrait plutôt bien passer

[pseudocode]

Ton nœud d'arrivée est ton nœud puits. Tu ajoutes un nœud source relié à tes nœuds de "départ" avec des arcs de capacité 1. Et voilà....

Dans l'exemple donné ca marche bien, car on utilise les noeuds de départ au plus une seule fois. Mais s'il y a un "split" (par exemple en ajoutant l'arc 1-6), la capacité de départ va limiter les chemins.

[Acrim]

Bien vu mais ça va dépendre de ce qu'on appelle un nœud de départ. Si d'un nœud de départ commence un seul chemin alors je pense que ma démarche est bonne. Si d'un nœud de départ peuvent commencer plusieurs chemins alors l'exemple que tu donnes pose problème (et augmenter la capacité des arcs nœud puits/nœuds de départ n'arrange rien.)

Il faudrait un peu plus de précision sur la définition des différents éléments.

[camelia136]

Merci pour vos réponses

Mon but est de réutiliser un maximum les segments.
l'algorithme du flot maximum pourrait être bon , mais si tous les arcs sont saturés avec cet algorithme on est bloqué !? Donc on pourrait ne pas trouver de solution alors que dans les faits il est toujours possible de rajouter par exemple un lien entre deux sites ou d'augmenter la capacité existante

[pseudocode]

Merci pour vos réponses

Mon but est de réutiliser un maximum les segments.
l'algorithme du flot maximum pourrait être bon , mais si tous les arcs sont saturés avec cet algorithme on est bloqué !? Donc on pourrait ne pas trouver de solution alors que dans les faits il est toujours possible de rajouter par exemple un lien entre deux sites ou d'augmenter la capacité existante

On doit pouvoir utiliser l'algo du flot-max, mais je pense qu'il faut d'abord identiger les capacités manquantes sur les arcs. Par exemple un propagation inverse en partant du noeud d'arrivée pour trouver les sens de circulation (s'il n'y a pas de cycle) et les capacités max des arcs sources/départ.

[Acrim]

Merci pour vos réponses

Mon but est de réutiliser un maximum les segments.
l'algorithme du flot maximum pourrait être bon , mais si tous les arcs sont saturés avec cet algorithme on est bloqué !? Donc on pourrait ne pas trouver de solution alors que dans les faits il est toujours possible de rajouter par exemple un lien entre deux sites ou d'augmenter la capacité existante

Je n'ai pas du bien comprendre ton problème (tu peux modifier la capacité des arcs ?). Mais oui la résolution du problème du flot maximum ne te donnera qu'une réponse respectant les capacités des arcs (mais il te donnera une des solutions permettant de faire passer le plus de chemins - si je poursuis mon idée de départ).

La recherche des coupes minimales (lié au problème de flot max) peut peut-être te guider pour identifier les capacités bloquantes...