Problemi matematici minori ?

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 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 mopnetine 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:

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:
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".

Alla prox