Algoritmo per trovare l'albero di spanning minimo dei vertici scelti

Question

Uno può utilizzare l'algoritmo di Prim o l'algoritmo di Kruskal per trovare l'albero/grafico spanning minimo di una raccolta di vertici/nodi e bordi/collegamenti. Quello che voglio però è un algoritmo che trova il grafico spanning minimo di questa collezione, ma il grafico risultante deve includere solo nodi scelti arbitrariamente, invece di tutti i nodi. Va bene se il grafico risultante include più nodi di quelli necessari.

Esiste un tale algoritmo? Forse si potrebbe semplicemente usare l'algoritmo di Prim (o di Kruskal) dopo aver modificato il grafico per includere solo i nodi necessari? Ma non sono sicuro di come modificare il grafico per farlo mantenendo la sua connessione.

Per esempio, dire che abbiamo un diamante a forma di grafico di partenza (con costi di collegamenti tra parentesi):

A 
(2)/ \(1) 
    B C 
(2)\ /(5) 
    D 

Ora, abbiamo arbitrariamente decidere che solo nodi A e D sono necessari. Se iniziassimo ad A, vorremmo comunque che prendesse il percorso a sinistra, perché ((2 + 2) < (1 + 5)).

Say modifichiamo il grafico leggermente:

A 
(2)/ \(1) (2) 
    B C ------E 
(2)\ /(5) 
    D 

Se si decide che solo nodi A, D ed E sono necessari, ci si rende conto che il percorso con il minimo costo non è necessariamente quella con il minor collegamenti. Prendendo A - B - D e A - C - E costa 7, ma A - C - D e C - E costa 8.

Answer 1

Quello che vuoi trovare è un discreto Steiner tree. Quando non tutti i vertici nel grafico sono obbligatori ma l'albero può dividersi sui vertici opzionali, il problema è NP-difficile.

Wikipedia dice (collegato sopra) di questo problema: si ritiene che in genere un rapporto di approssimazione arbitrariamente buono non possa essere raggiunto in tempo polinomiale. Esiste un algoritmo tempo-polinomiale che trova un'approssimazione del fattore 1.39 di un albero Steiner minimo.