Algorithme pour trouver l'arbre minimum Spanning lorsque le coût est en multipliant le poids de bord

Question

On m'a récemment demandé si je pouvais trouver un algorithme pour calculer l'arbre coût minimal couvrant d'un graphe donné, lorsque le coût total de l'arbre couvrant est donnée par le produit des frais de garde plutôt que par leur somme.

Il y a plusieurs algorihms pour calculer le minium régulier spanning tree, mais je ne suis pas sûr de la façon de les modifier pour le cas mentionné ci-dessus. Toutes les idées?

Merci.

Answer 1

Comme log (produit des coûts de bord) = somme (log (coûts de bord)), connectez-vous-transformer le bord des poids, et de trouver l'arbre coût minimum couvrant ces poids.

Answer 2

Depuis un logarithme est une transformation monotone, l'arbre couvrant minimal sera exactement la même chose quand vous prenez le journal de tous les poids et lorsque vous quittez tous les poids de la façon dont ils sont. Donc:. Il n'y a aucune différence à trouver le MST en fonction de la somme de tous les poids et selon le produit de tous les poids

Pour l'article de la preuve du fait cette un arbre couvrant minimal d'un graphe est invariant à la transformation monotone des poids dans le graoh, type La Saga d'arbre minimum dans google. Et le premier lien sera celui que vous avez besoin. Page 167, isomorphisme monocorde.

Answer 3

Ma meilleure idée - Trouver tous un minimum (ce qui signifie des bords inutiles) enjambant les arbres par la force brute, choisissez celui avec le produit le plus petit.

La plupart (ou tous) plus des solutions efficaces ne sont plus valables - principalement des solutions optimales bc ne contiennent plus nécessairement des problèmes optimaux sous. (Quelles sont les restrictions très importantes -. Bords du prix coûtant moins de 1 sont coût réellement négatif, arêtes de longueur 1 sont sans-ils mieux tous positifs!)

Je ne sais pas si cette question est vraiment significative. Pour un, vous devez soit donner des coûts d'auto-boucle (ou assumer 1) parce que nous ne pouvons pas prendre le produit avec zéro. Fractionnement d'un chemin fonctionne différemment, parcourant le même chemin coûte deux fois c ^ 2? De plus, je me sens comme cela devrait être une qualité différente d'un chemin avec un autre nom que « coût »