Graphiques acycliques dirigés pondérés: algorithme pour trouver des poids de bord tels qu'ils définissent une fonction de distance?

Question

J'ai ce problème technique qui peut être formuated avec un Directed Acyclic Graph (DAG). Les nœuds représentent des événements (avec un timing inconnu), avec des bords orientés codant la relation: "Je suis plus jeune que vous/je suis arrivé avant vous".

J'ai besoin d'estimer les poids de bord (c'est-à-dire les "poids dynamiques") de telle sorte que le DAG pondéré (WDAG) implique une fonction de distance sur le DAG. En d'autres termes, la somme des poids pour les chemins entre les nœuds A et B doit être égale pour tous les chemins.

Ceci est un problème indéterminé, même si les poids sont des entiers (même raison sous-jacente que le tri topologique n'est pas unique, je suppose). En général, les poids de bord, qui représentent les intervalles de temps entre les noeuds/événements, sont des nombres réels. Par conséquent, j'introduis une fonction d'objectif prédéfinie C = J (WDAG) sur le DAG pondéré, ici non spécifié.

Ma question est: est-il un algorithme qui distribue des poids définis positifs sur le WDAG, sous réserve de la contrainte 1) que les poids forment une fonction de distance de la DAG et 2) en minimisant la fonction objectif coût C.

Cela semble sans rapport avec les problèmes d'arborescence de chemin le plus court ou d'arborescence minimale associés classiquement aux WDAG. Des idées à une solution formelle ou heuristique au problème ci-dessus?

Cordialement,

Stéphane

Answer 1

Je pense que tout ce que vous avez besoin est topological sorting.

1. Trier les noeuds selon un tri topologique.
2. Distribuez-les dans l'intervalle [0,1] dans l'ordre que vous avez.
3. Maintenant, la distance des paires de nœuds sur la ligne [0,1] vous donnera le poids du bord qui les relie.

Ceci est une solution possible. Si vous avez plus de contraintes sur les poids que ce que vous décrivez dans la question, le problème pourrait être plus difficile.