Algoritmo per trovare l'albero di copertura minimo quando il costo è dato dalla moltiplicazione pesi bordo

Question

Recentemente sono stato chiesto se riuscivo a trovare un algoritmo per calcolare l'albero costo di copertura minimo di un dato grafico, dove il costo totale del spanning tree è dato dal prodotto dei costi bordo piuttosto che dalla loro somma.

Ci sono diversi algorihms per calcolare il minio regolare spanning tree, ma sono sicuro di come modificarli per il caso di cui sopra. Tutte le idee?

Grazie.

Answer 1

Dal log (prodotto dei costi di bordo) = somma (log (i costi di bordo)), basta accedere, trasformare gli edge-pesi, e trovare l'albero costo di copertura minimo per questi pesi.

Answer 2

Dal momento che un logaritmo è una trasformazione monotona, l'albero di copertura minimo sarà esattamente la stessa cosa quando si prende il registro di tutti i pesi e quando si esce tutti i pesi così come sono. Quindi:. Non c'è differenza nel trovare il MST in base alla somma di tutti i pesi e secondo il prodotto di tutti i pesi

Per l'articolo della prova del fatto quella un albero di copertura minimo di un grafico è invariante verso monotono trasformazione dei pesi in graoh, genere La saga di Minimum Spanning Tree in google. E il primo collegamento sarà quello che vi serve. Pagina 167, monotona isomorfismo.

Answer 3

La mia idea migliore - Trova tutti minima (nel senso di bordi non necessari) spanning tree con la forza bruta, scegliere quello con più piccola del prodotto.

La maggior parte (o tutte) le soluzioni più efficienti non applicare - principalmente bc soluzioni ottimali più necessariamente contengono problemi ottimali sub. (Quali sono le restrizioni molto importanti -?. Bordi costare meno di 1 sono costo realmente negativo, bordi di lunghezza 1 sono liberi che meglio essere tutti positivi!)

Non sono sicuro se questa domanda è veramente significativo. Per uno, è necessario dare i costi di auto-loop (o assumere 1) perché non possiamo prendere prodotto con zero. Dividere un percorso funziona in modo diverso, viaggiando i costi stesso percorso due volte c ^ 2? Inoltre, mi sento come questo dovrebbe essere una qualità diversa di un percorso con un nome diverso da quello 'costo'