Quarantraining - 08

Materiale didattico
1

Steiner Trees

Prerequisiti

Problema

Dato un grafo non diretto con n nodi (pesato o non), di cui t speciali, e m archi, trova l’albero minimo che connette tuttti i t nodi speciali.

Soluzione

Questo problema e’ NP-completo, la soluzione che spiego avra’ una complessita esponenziale su t.
I t nodi speciali si chiamano terminali.
I nodi non terminali sullo steiner tree che hanno almeno 3 archi connessi, si chiamano steiner nodes.
Consideriamo quindi l’albero ridotto con solo i terminali e gli steiner nodes e la radice.
Assumiamo di avere risolto il problema per ogni radice per ogni subset di nodi, tranne quello completo,
allora possiamo provare per ogni coppia di subset complementari e radici a collegare le due radici.
Questo procedimento da la soluzione corretta, quindi per induzione possiamo estenderlo a ogni subset di nodi.
Al posto di provare ogni coppia di radici, possiamo dopo aver trovato la soluzione per una radice, provare a “spostarla” a ogni nodo.
chiamo dp_{i,mask} la soluzione quando i e’ la “radice” dello steiner tree e mask indica i terminali da prendere
allora dp_{i,mask} sara’ il minimo dp_{i,sm1}+dp_{i,sm2} \forall sm1,sm2 tc sm1 \oplus sm2 = mask

Implementazione

Precomputa dist[i][j], la distanza tra i nodi i e j per ogni i,j < n
Setta dp[i][mask] a \infty per ogni i < n e mask < 2^t e a 0 quando mask = 0

for(int mask=1; mask<(1<<t); ++mask){
	for(int i=0; i<n; ++i){
		for (int sm=mask; sm; sm=(sm-1)&mask)
			dp[i][mask]=min(dp[i][mask],dp[i][sm]+dp[i][sm^mask]);
		for(int j=0; j<n; ++j)
			dp[j][mask]=min(dp[j][mask],dp[i][mask]+dist[i][j]);
	}
}

Note

La complessita’ di quest’algoritmo e’ O(n \cdot 3^t + n^2) (nota che iterare tutte le sottomaschere di ogni maschera lunga t e’ O(3^t))
Questo algoritmo risolve anche il problema per ogni subset di terminali
Esiste un algoritmo per risolvere questo problema con una complessita’ migliore che pero’ funziona solo con t \le 5 chiamato “Spiderman Algorithm”
Questo problema e’ uno dei 21 problemi NP-hard di Karp

Risorse

Problemi

6 Mi Piace