1

Problema di Steiner nelle reti di trasmissione

ing. R. Turco (rosario_turco@virgilio.it)

In Matematica esistono innumerevoli problemi, apparentemente

minori, nel senso che non sono direttamente classificati tra i

"problemi del Millennio"; ma che tuttavia se risolti avrebbero un

impatto tecnologico notevole nella vita odierna.

Soprattutto permetterebbero pianificazioni ed uso di risorse in

modo mirato e a minor costo.

Non solo ma risolvendo un problema, si risolverebbero problemi

"isomorfi in altri contesti".

Per farvi comprendere di che si tratta pensate a: traffico aereo,

percorsi idrici, gas, fognature in una città, distensione dei cavi

e delle fibre ottiche, creazione di circuiti integrati con

aggiunta di nuovi nodi o vertici, ma anche nelle trasmissioni

audio, video, etc.

Avete mai fatto delle audio col numero verde 800 dove si collegano

e si scollegano varie persone? Ebbene un sistema efficiente deve

ricalcolare ogni volta l'albero di Steiner più efficace per poter

riequilibrare QoS (Quality of Service) e percorsi di minor costo o

banda.

In poche parole si tratta del “problema di Steiner”. Per

introdurvi al problema immaginate di avere un grafo G di cui

inizialmente avete solo i nodi (i vertici) V e volete creare un

albero (albero di Steiner) col numero minimo di collegamenti

pesati.

Chiariamo subito che per “pesati” occorre immaginare un costo che

può essere, ad esempio, in un’audio telefonica il tempo di

trasmissione o di ritardo e la qualità del segnale QoS; mentre per

albero intendiamo dei collegamenti senza percorsi chiusi (no ad

2

anelli o a circuiti). Ad esempio con quattro vertici colleghiamo

solo 3 lati di un quadrato (l'ultimo lato non lo disegniamo).

Se il grafo fosse statico cioè con vertici fissi, l’algoritmo

ottimizzato di Kruskal risolverebbe benissimo la cosa; ma se c’è

una dinamicità nel tempo dei vertici n=|V|, allora la cosa si

complica di parecchio (anche se è risolvibile ma non in maniera

ottimale assoluta).

La tecnica dell'algoritmo di Kruskal con vertici statici è

semplice. Immaginiamo di avere di ogni coppia di vertici il costo

e ordiniamoli dal costo più basso al costo più alto. A questo

punto colleghiamo (senza creare percorsi chiusi altrimenti non

avremo un albero) i nodi a costo minore, via via arrivando a

quelli di costo maggiore e ci arrestiamo se abbiamo collegato già

tutti i vertici statici.

Siamo, quindi, nella teoria dei grafi, quella iniziata nel

Settecento con Eulero e il problema dei ponti di Konigsberg.

Nel problema di Steiner l'obiettivo è di cercare, ad ogni

variazione del numero di vertici(aggiunta o rimozione) , l’albero

dei collegamenti minimi che ottimizza le risorse (i costi) che

variano nel tempo.

Pensate alla banda di trasmissione e il QoS che deve essere

rispettato all'aumentare dei nodi che si collegano o alla

variazione delle località dei nodi.

E’ dimostrato che il problema di Steiner è NP-completo; per cui il

problema di Steiner rientra 'indirettamente' nel "problema del

millennio P=NP".

A questa famiglia ne appartengono molti : il problema dello zaino

o sacco da viaggio, del commesso viaggiatore, il problema di

Steiner, il problemino dell'individuare il maggior numero di

monetine di ogni taglio disponibile per pagare un conto, la

fattorizzazione del RSA, il logaritmo discreto etc.

Come tutti i problemi NP-completi, non riuscendo a trovare un

algoritmo deterministico polinomiale si cerca di trovare almeno

non l’ "ottimo in assoluto" ma il "miglior ottimo disponibile" con

tecniche euristiche o altre. Il che non significa che non esiste

una soluzione, anzi la soluzione esiste ma è di tipo esponenziale

rispetto ai dati di input e, quindi, poco efficiente.

Sono nati,a tal proposito, molto algoritmi a risoluzione del

problema; ad esempio troviamo tra:

3

Algoritmi ottimi

Spanning Tree Enumeration Algorithm (STEA)

Dynamic Programming Algorithm (DPA)

Euristiche per il problema di Steiner

Pruned Dijkstra Heuristic (PDH)

Distance Network Heuristic (DNH)

Shortest Path Heuristic (SPH)

Kruskal based – Shortest Path Heuristic (K-SPH)

Repetitive Shortest Path Heuristics

Average Distance Heuristic (ADH)

Tecniche di Post-processing

Ma esistono anche tanti altri SAT, 3SAT etc.

Come in tutte le discipline ingegneristiche, dove non esiste una

soluzione ottima assoluta, allora ognuno degli algoritmi trovati è

forte in un "certo range di quantità", per cui anche quelli di cui

parlavo prima hanno una efficienza che li avvantaggia o li

svantaggia all’aumentare del numero di vertici. Spesso un software

di gestione delle risorse dispone più algoritmi, che sceglie in

base alla quantità di vertici in cui si ritrova.

OK, starete già su Wikipedia a vedere la corretta definizione del

problema. Bravi! Si inizia da lì, altrimenti vi ritrovereste a

risolvere un problema mal definito e vi illudereste di aver

trovato la soluzione!

Esistono anche varie versioni del problema di Steiner:

problema di Steiner nelle reti (la versione generale che

interessa)

problema di Steiner rettilineo: la topologia è data dal piano

R^2 con la metrica indotta dalla 'distanza Manhattan';

problema di Steiner euclideo: anche in questo caso la

topologia è data dal piano R^2, con la metrica indotta dalla

distanza euclidea;

Il problema che interessa dovrebbe esser formulato come segue:

"Data una rete connessa e non diretta G = (V, E, w), w : E -> R, e

un insieme Z sottoinsieme di V,trovare il sottografo connesso Gs =

(Vs, Es, w) di G tale che:

4

a) Z sottoinsieme di Vs (strettamente incluso o incluso in Vs);

b) w(Gs) = Sum(i,j,w(i,j)) sia minimo con i,j appartenenti a Es".

L’insieme Z è detto, con riferimento al problema trattato,

'insieme di multicast'; mentre l’insieme Vs – Z viene denotato con

S ed è costituito dai 'nodi di Steiner'.

Se la funzione di costo w(i, j) degli archi assume sempre valori

positivi il sottografo soluzione è un albero, detto 'albero di

Steiner', che verrà indicato nel seguito con Tz. Si pone inoltre n

= |V|, m = |E|, p = |Z|, s = |S|.Alcuni casi limite del problema

di Steiner però ricadono in problemi ben noti della teoria dei

grafi:

p = 2: si tratta di trovare il percorso più breve che

connetta i due nodi dell’insieme Z; il problema viene risolto

dall’algoritmo di Dijkstra, che restituisce un albero di

cammini minimi da un nodo verso tutti gli altri nodi della

rete;

p = n, cioè Z = V: si tratta di calcolare il minimum spanning

tree o MST del grafo dato;in questo caso il problema viene

risolto dall’algoritmo di Prim o dalla variante di Kruskal.

La valutazione della qualità degli algoritmi di questo genere di

solito avviene su due fattori di merito:

la competitività di costo, intesa come bontà della soluzione

trovata Th (l'albero di STeiner trovato) rispetto a quella

ottima Tz e in formule :

ch = w(Th)/w(Tz)

la complessità computazionale, in notazione O(f(n))

Molti altri problemi sono importanti per l'industria alimentare

come quello dell'impacchettamento (pensate al problema

dell'impacchettamento delle sfere di Keplero) o della

realizzazione di scatole al minor costo e con determinate qualità.

Pensate alle buste del latte o ai nuovi contenitori ideati i

cosiddetti 'tetrapack' o anche a mobili in alluminio/acciao o a

macchine per catene di montaggio; ma ne parleremo la prossima

volta. Aggiungo solo una nota di colore: Steiner era svizzero e la

sua cultura era autodidatta. Imparò a leggere e scrivere a 14 anni

e si dimostrò un genio matematico tale da insegnare a 20 anni.

Ma soprattutto era uno genio della geometria: molti teoremi li

dimostrava visivamente, grazie alla geometria, come la

dimostrazione del "problema di Didone" e del "problema

isoperimetrico".