Percorso di lunghezza minima tra 3 punti assegnati


L'applet in questa pagina illustra il problema del network minimale tra tre punti assegnati. Supponiamo di avere 3 città P1, P2 e P3, che vogliamo congiungere con strade disegnate in modo che la loro lunghezza totale sia la minima possibile.

Le tre città sono rappresentate dai punti blu nell'applet, mentre una possibilità per le tre strade è disegnata in rosso: è possibile trascinare con il mouse l'"incrocio" centrale (il punto rosso), in modo da cercare di minimizzare la lunghezza totale. Il regolo verde nella parte destra dell'applet ci fornisce un'idea di quanto la lunghezza attuale sia distante dalla minima: dobbiamo cercare di spostare l'incrocio in modo che il cursore bianco si porti nell'estremità sinistra del regolo stesso.

L'istogramma sopra il regolo mostra gli angoli formati dalle tre strade, allo scopo di evidenziare un'importante proprietà della posizione ottimale (che ci può anche aiutare a trovarla!). Si consideri infatti il triangolo formato dalle tre città, e supponiamo che nessuno dei suoi angoli al vertice sia maggiore o uguale a 120o. In tal caso, la posizione ottimale dell'incrocio è data dall'unico punto interno al triangolo tale che gli angoli formati delle tre strade tra di loro siano tutti di 120o (esso è chiamato Punto di Steiner). Se invece il triangolo possiede un angolo ottuso maggiore o uguale a 120o, un tale punto non esiste e la soluzione si realizza portando l'incrocio sul vertice corrispondente all'angolo ottuso.

Che fare se non siamo capaci di trovare da soli la posizione ottimale? La ricerca di un tesoro è notoriamente più facile se si possiede una mappa! Premendo il pulsante "Mostra/Nascondi Mappa Lunghezza", viene resa visibile una "carta topografica" della lunghezza totale delle strade: in ogni punto, una tonalità di verde ci informa della maggiore o minore lunghezza che si ottiene spostando l'incrocio sul punto stesso. A tonalità più scure corrisponde una minore lunghezza del percorso totale, per cui il minimo corrisponde al "buco nero" visibile nella mappa...

Se poi vogliamo cimentarci con posizioni differenti delle tre città, abbiamo due possibilità: possiamo trascinarle con il mouse in punti a nostro piacimento, oppure possiamo far scegliere automaticamente all'applet premendo il pulstante "Piazza i Punti a caso".