Programmation dynamique : le plus grand poids possible dans un chemin de nœuds.

Question

Tout d'abord, je voudrais dire que c'est ma première question sur Stack Overflow et que si ma question n'est pas posée correctement ou si c'est une question que je ne devrais pas poser, merci de me le dire pour que je puisse la corriger (j'ai déjà lu la visite guidée mais on ne sait jamais !).

Commençons donc : J'essaie de faire un algorithme dans un graphe acyclique dirigé et pondéré (le poids peut être négatif ou positif). L'algorithme devra trouver le chemin avec le plus grand poids à partir d'un noeud spécifique et qui peut passer par un maximum de N noeuds (il peut utiliser moins de noeuds s'il obtient un meilleur poids).

J'ai compris que je devais utiliser la programmation dynamique pour le faire, mais je n'ai aucune idée de la façon dont je pourrais le faire. J'ai fait pas mal de recherches et je n'ai trouvé que "l'algorithme du plus long chemin d'un nœud u à un nœud v" mais ce n'est pas ce que j'essaie de faire.

Je connais l'algorithme de Dijkstra, mais je ne pense pas que c'est ce que je suis censé utiliser.

Merci beaucoup de me lire et merci d'avance pour votre aide.

Answer 1

L'algorithme sur l'entrée v, z :

1. Trouver un composant fortement connecté, savoir si vous avez un cycle avec un poids positif à l'intérieur d'un chemin à partir du nœud v vous pouvez retourner à l'infini.

2. Trier le graphe dirigé en utilisant dfs

3. Commence par les noeuds des feuilles et retourne le maximum(weight_of_node(leave1, z),.....)

4. Pour le noeud actuel, imprimez-le et choisissez le noeud père avec le plus de poids calculé par une fonction récursive. Si le noeud n'a qu'un seul père, choisissez ce père, si le noeud est v, retournez le poids de v et imprimez-le.

5. Maintenant tous les noeuds sélectionnés sont imprimés

*lorsque vous calculez le poids du noeud

`weight_of_node(x, z) :

Si z==0

   return - infinite 

return maximum(weight_of_node(father_node1) , weight_of_node(father_node2) ,...) +current_node_weight`, z - 1)