Comment calculer le chemin critique d'un graphe acyclique directionnel?

Question

Quel est le meilleur moyen (en termes de performances) de calculer le chemin critique d’un graphe acyclique directionnel lorsque les nœuds du graphe ont un poids?

Par exemple, si ma structure est la suivante:

            Node A (weight 3)
               /            \
     Node B (weight 4)      Node D (weight 7)
     /               \
Node E (weight 2)   Node F (weight 3)

Le chemin critique doit être A - > B - > F (poids total: 10)

Answer 1

Je n'ai aucune idée des " chemins critiques " ;, mais je suppose que vous voulez dire this .

La recherche du plus long chemin dans un graphe acyclique avec des poids n’est possible qu’en parcourant l’arbre entier, puis en comparant les longueurs, car vous ne savez jamais vraiment comment le reste de l’arbre est pondéré. Pour en savoir plus sur la traversée des arbres, consultez Wikipedia . Je suggère que vous optiez pour le parcours en pré-commande, car il est facile et simple à mettre en œuvre.

Si vous allez interroger souvent, vous pouvez également augmenter les limites entre les nœuds en fournissant des informations sur le poids de leurs sous-arbres lors de l'insertion. Ceci est relativement peu coûteux, alors qu'une traversée répétée peut être extrêmement coûteuse.

Mais rien ne vous empêche vraiment de traverser un parcours complet si vous ne le faites pas. L'ordre n'a pas vraiment d'importance, tant que vous faites un parcours et ne suivez jamais le même chemin deux fois.

Answer 2

Je résoudrais ceci avec une programmation dynamique. Pour trouver le coût maximal de S à T:

• Triez topologiquement les nœuds du graphe de la manière suivante: S = x_0, x_1, ..., x_n = T. (Ignorez les nœuds pouvant atteindre S ou ceux de T.)
• Le coût maximal de S à S est le poids de S.
• En supposant que vous ayez calculé le coût maximum de S à x_i pour tous les i < k, le coût maximal de S à x_k est le coût de x_k plus le coût maximal pour tout nœud dont le bord est égal à x_k.

Answer 3

Un document prétend avoir un algorithme pour cela: & "Chemin critique dans un réseau d'activités avec des contraintes de temps &"; Malheureusement, je n'ai pas pu trouver de lien vers une copie gratuite. En dehors de cela, je ne peux que seconder l’idée de modifier http://en.wikipedia.org/ wiki / Dijkstra% 27s_algorithm ou http://en.wikipedia.org/wiki/A *

UPDATE: Je m'excuse pour la mise en forme de merde & # 8212; le moteur de démarque côté serveur est apparemment en panne.

Answer 4

Ma première réponse, veuillez donc nous excuser pour toute chose non standard basée sur la culture de stackoverflow.

Je pense que la solution est simple. Annulez simplement les poids et exécutez le chemin le plus court classique pour DAG (modifié pour les poids des sommets bien sûr). Il devrait courir assez vite. (Complexité temporelle de O (V + E) peut-être)

Je pense que cela devrait fonctionner comme si vous annuliez les poids, le plus gros deviendra le plus petit, le second le plus petit deviendra le deuxième plus petit et ainsi de suite, comme si a > b puis -a < -b. Ensuite, lancer DAG devrait suffire car il trouvera la solution pour le plus petit chemin de celui qui a été nié et trouvera ainsi le plus long chemin pour le chemin d'origine

Answer 5

Essayez la méthode A *.

Algorithme de recherche A *

À la fin, pour traiter les feuilles, il suffit de les amener toutes à un dernier point, à définir comme objectif.