Aimez quelques conseils sur ce problème:
G est un graphe acyclique dirigé. Vous voulez passer du sommet c au sommet z. Certains bords réduisent vos profits et d'autres augmentent vos profits. Comment allez-vous de c à z tout en maximisant vos profits? Quelle est la complexité temporelle?
Merci!
Réponses:
1 pour la réponse № 1Le problème a une sous-structure optimale. Pour trouver le plus long chemin du sommet c au sommet z, nous devons d’abord trouver le chemin le plus long depuis c à tous les prédécesseurs de z. Chaque problème de ceux-ci est un autre sous-problème plus petit (le plus long chemin de c à un prédécesseur spécifique).
Notons les prédécesseurs de z comme u1,u2,...,uk et dist[z] être le plus long chemin de c à z puis dist[z]=max(dist[ui]+w(ui,z))..
Voici une illustration avec 3 prédécesseurs en omettant les poids des jeux d'arêtes:
Donc, pour trouver le plus long chemin vers z nous devons d’abord trouver le chemin le plus long vers ses prédécesseurs et en tirer le maximum (leurs valeurs plus leurs arêtes z).
Cela nécessite chaque fois que nous visitons un sommet u, tous u"Les prédécesseurs doivent avoir été analysés et calculés.
Donc la question est: pour tout sommet u, comment être sûr qu'une fois que nous avons défini dist[u], dist[u] ne sera jamais changé plus tard? En d'autres termes: comment s'assurer que nous avons pris en compte tous les chemins depuis c à u avant d'envisager un bord originaire de u?
Comme le graphique est acyclique, nous pouvons le garantircondition en trouvant un tri topologique sur le graphique. Le type topologique ressemble à une chaîne de sommets où toutes les arêtes sont orientées de gauche à droite. Donc, si nous sommes au sommet vi alors nous avons considéré tous les chemins menant à vi et ont la valeur finale de dist[vi].
La complexité temporelle: le tri topologique prend O(V+E). Dans le pire des cas où z est une feuille et tous les autres sommets pointent vers elle, nous visiterons toutes les arêtes du graphe qui donne O(V+E).
0 pour la réponse № 2
Laisser f (u) être le maximum de profit que vous pouvez obtenir à partir de c à vous dans votre DAG. Ensuite, vous voulez calculer f (z). Ceci peut être facilement calculé en temps linéaire à l'aide de la programmation dynamique / tri topologique.
Initialiser f (u) = -infinité pour chaque vous autre que c, et f (c) = 0. Ensuite, procédez au calcul des valeurs de F dans un ordre topologique de votre DAG. Ainsi, l'ordre étant topologique, pour chaque front entrant du nœud en cours de calcul, les autres extrémités sont calculées. Il suffit donc de choisir la valeur maximale possible pour ce nœud, c'est-à-dire. f (u) = max (f (v) + coût (v, u)) pour chaque front entrant (v, u).
0 pour la réponse № 3
Il vaut mieux utiliser Tri topologique au lieu de Bellman Ford depuis son DAG.
La source:- http://www.utdallas.edu/~sizheng/CS4349.d/l-notes.d/L17.pdf
MODIFIER:-
G est un DAG avec des bords négatifs.
Certains bords réduisent vos profits et d'autres augmentent vos profits
- Bords - augmentation du profit - valeur positive
- Bords - diminution du bénéfice - valeur négative
Après TS, pour chaque sommet U dans l’ordre TS, relâchez chaque bord sortant.
dist[] = {-INF, -INF, ….}
dist[c] = 0 // source
for every vertex u in topological order
if (u == z) break; // dest vertex
for every adjacent vertex v of u
if (dist[v] < (dist[u] + weight(u, v))) // < for longest path = max profit
dist[v] = dist[u] + weight(u, v)
ans = dist[z];