Existe-t-il un moyen de programmation dynamique pour calculer les k arbres couvrant au minimum?

Question

Mon professeur nous a demandé d'implémenter une solution de programmation dynamique à ce problème, mais je pense qu'il n'existe pas car je ne l'ai pas trouvé avec Google. Quoi qu'il en soit, étant donné un graphique et un k, disons 3, vous devez trouver les 3 meilleurs MST. Si le graphe est tel qu'il n'a pas de sous-arbre k, vous pouvez renvoyer le même arbre plusieurs fois ou des arbres sous-optimaux.

Je ne peux pas vraiment penser à une solution.

Answer 1

Vous m'avez confus pendant un moment là-bas et je pensais que vous pourriez avoir mal compris le problème. Le problème "k-MST" consiste à trouver k arêtes qui forment un sous-arbre de sorte que la somme de ses arêtes soit inférieure ou égale à toutes les autres sommes que vous pouvez obtenir des sous-ares de k arêtes. Mais alors j'ai vu le pluriel s. Donc, pour votre problème, j'essaierais personnellement de trouver un algorithme DP pour trouver le MST qui combine avec un moyen de générer un "prochain" MST. Puisqu'il s'agit d'une programmation dynamique, j'examinerais de façon répétée l'optimisation (dans ce cas, la désoptimisation pour chaque étape) ou les différentes façons de partitionner les bords en sous-ensembles qui ont un sens dans un paramètre MST. Il pourrait y avoir plusieurs façons.

Cependant, la recherche de partitions et minimum arborescences j'ai trouvé ce qui pourrait être plus d'aide si vous voulez juste la réponse: http://www.scielo.br/scielo.php?script=sci_arttext&pid=S0101-74382005000200004