Algorithmus, um minimale Spannungsbaum zu finden, wenn die Kosten durch Multiplizieren von Kantengewichten angegeben werden

Question

Ich wurde kürzlich gefragt, ob ich einen Algorithmus finden könnte, um die minimalen Kosten zu berechnen, die Baumstamm eines bestimmten Diagramms berechnet, wobei die Gesamtkosten des Spanning -Baumes durch das Produkt der Kantenkosten und nicht durch ihre Summe angegeben sind.

Es gibt mehrere Algorihm, um den regulären Miniumspannungsbaum zu berechnen, aber ich bin mir nicht sicher, wie man sie für den oben genannten Fall optimiert. Irgendwelche Ideen?

Vielen Dank.

Answer 1

Da log (Produkt der Kantenkosten) = Summe (Log (Kantenkosten)), log die Kantengewichte an und ermitteln Sie die minimalen Kosten für diese Gewichte.

Answer 2

Da ein Logarithmus eine monotonische Transformation ist, ist der minimale Spannungsbaum genau gleich, wenn Sie das Protokoll aller Gewichte nehmen und wenn Sie alle Gewichte so lassen, wie sie sind. Also: Es gibt keinen Unterschied in der Finden des MST gemäß der Summe aller Gewichte und gemäß dem Produkt aller Gewichte.

Für den Artikel des Beweises der Tatsache, dass ein minimaler Spannungsbaum eines Diagramms für die monotonische Transformation der Gewichte im Graoh invariiert, geben Sie die Saga des minimalen Spannungsbaums in Google ein. Und der erste Link wird derjenige sein, den Sie benötigen. Seite 167, monotoner Isomorphismus.

Answer 3

Meine beste Idee - Finden Sie alle minimalen (dh für unnötigen Kanten), die Bäume mit brutaler Kraft überspannen, und wählen Sie das mit dem kleinsten Produkt.

Die meisten (oder alle) effizienteren Lösungen gelten nicht mehr - hauptsächlich bc -optimale Lösungen enthalten nicht mehr unbedingt optimale Subprobleme. (Was sind die Einschränkungen?

Ich bin mir nicht sicher, ob diese Frage wirklich bedeutungsvoll ist. Zum einen müssen Sie entweder Selbstschleifenkosten geben (oder 1 annehmen), weil wir das Produkt nicht mit Null nehmen können. Die Aufteilung eines Pfades funktioniert anders und kostet zweimal C^2? Darüber hinaus habe ich das Gefühl, dass dies eine andere Qualität eines Pfades mit einem anderen Namen als "Kosten" sein sollte.