# Quarantraining - 08

**URL:** <https://forum.olinfo.it/t/quarantraining-08/6134>\
**Category:** Materiale didattico\
**Created:** [7 Aprile 2020, 11:58am UTC](https://forum.olinfo.it/t/quarantraining-08/6134 "2020-04-07T11:58:18Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![MyK\_00L](https://forum.olinfo.it/user_avatar/forum.olinfo.it/myk_00l/32/3000_2.png) [@MyK\_00L](https://forum.olinfo.it/u/MyK_00L)\
**Post date:** [7 Aprile 2020, 11:58am UTC](https://forum.olinfo.it/t/quarantraining-08/6134/1 "2020-04-07T11:58:18Z")

</div>

# Steiner Trees

## Prerequisiti

- [dfs tree](https://forum.olinfo.it/t/quarantraining-07/6131)
- [bitmasks](https://forum.olinfo.it/t/quarantraining-05/6125)
- [APSP (all pairs shortest path)](https://cp-algorithms.com/graph/dijkstra.html)
- [programmazione dinamica](https://en.wikipedia.org/wiki/Dynamic_programming)

## 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

```auto
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](https://en.wikipedia.org/wiki/Karp%27s_21_NP-complete_problems)

# Risorse

- [Algorithms live](https://www.youtube.com/watch?v=BG4vAoV5kWw) (spiega anche spiderman algorithm)

# Problemi

- [Ticket to ride](http://poj.org/problem?id=3123)