IL MIGLIORE DEI PERCORSI POSSIBILI
Martina Basini – Giulia Bianchi
Liceo Scientifico Alessandro Volta – Milano
Tutor universitario: prof.Stefano Mortola
Docente responsabile: prof. Pierangela Lentini
The shortest path problem
Minimizing a network’s length is one of the oldest optimization problems in mathematics. The Steiner problem was to find the point P that minimizes the sum of the distances from P to each of three given points in the plane. The team analysed several applications of the Steiner problem tree connected to ordinary life. In fact this problem can be useful for the construction of railways, motorways, piping systems, and integrated circuits.
Sommario
Le studentesse Giulia Bianchi e Martina Basini si sono occupate degli aspetti del problema di Steiner affrontabili con mezzi di matematica elementare, non trascurando gli aspetti applicativi del problema stesso.
Il problema di Steiner consiste nel trovare una rete di lunghezza minima che colleghi un numero finito di punti assegnati nel piano.
Questo problema presenta numerose e notevoli applicazioni pratiche nella vita quotidiana. In settori ingegneristici vi è, ad esempio, il problema del multicast in una rete: si vuol trasmettere un messaggio lungo una linea inviando una stessa informazione da un nodo della rete ad un gruppo di altri nodi (trasmissione multicast), ovviamente si desidera minimizzare i costi di trasmissione. Altro esempio è offerto dalla posa in opera in un centro urbano o in aree più estese delle varie reti di servizi, quali la rete idrica, la rete del gas o le reti di telecomunicazioni e di trasporti (reti stradali e ferroviarie). In ciascuno di questi casi è utile cercare di minimizzare la lunghezza delle canalizzazioni da costruire, mantenendo comunque collegate tutte le utenze richieste. Il caso, forse il più frequente, dell’applicazione del problema di Steiner si ha nella progettazione di circuiti elettronici, dove la ricerca di una rete minima di conduttori del circuito integrato è funzionale al conseguimento di una superiore velocità di funzionamento.
Anche il campo biologico offre possibili applicazioni di questo problema in riferimento alla costruzione di alberi filogenetici di costo minimo, che esprimono in forma schematica le relazioni evoluzionistiche presenti tra le diverse specie viventi o estinte.
Il lavoro di Giulia Bianchi e Martina Basini e’ consistito nelle seguenti tre fasi.
- Implementare un programma al calcolatore che permetta di individuare la rete minima di Steiner.
- Costruire una “macchina” che illustri visivamente come appare la rete minima cercata quando si parte da 4 punti fissati nel piano.
- Studiare varianti significative del problema originario, per esempio ambientare la rete minima nello spazio invece che nel piano, oppure cercare la rete minima fra quelle che hanno i lati paralleli agli assi coordinati o ancora limitarsi a quelle reti che hanno come nodi solo i punti fissati inizialmente e non introducono ulteriori nodi aggiuntivi, cosa che succede generalmente per la rete di Steiner.
Il lavoro ha avuto un riconoscimento a livello della gara italiana “I GIOVANI E LE SCIENZE – CONCORSO EUROPEO EDIZIONE 2004” che ha permesso alle due studentesse di partecipare all’ EU Contest for Young Scientist tenutosi a Dublino dal 24 al 29 Settembre 2004.
http://ec.europa.eu/research/youngscientists/dublin/photos-country_en.htm Le studentesse sono citate in un articolo di Anna Maria Speroni che ha per tema il concorso europeo “I GIOVANI E LE SCIENZE”. L’articolo compare sul supplemento settimanale del Corriere della Sera – Io Donna – n.44 del 30 ottobre 2004 è disponibile qui.
