Shortest Path

Shortest Path è un programma dimostrativo di ricerca di una soluzione approssimata per il problema del commesso viaggiatore, che consiste nel trovare il percorso più breve per unire dei punti.

Appartiene ad una classe di problemi che non possono essere risolti semplicemente provando tutte le possibilità dato che queste, semplificando grossolanamente, sono "troppe" (ulteriori informazioni su Wikipedia).

L'approccio utilizzato è quello degli algoritmi evoluzionistici: si procede partendo da percorsi casuali e andando verso soluzioni sempre più ottimizzate, selezionando ad ogni generazione i percorsi migliori e replicandoli introducendo alcune variazioni.

Per sua natura, questa soluzione si adatta ai cambiamenti: potete spostare i punti con il mouse mentre il programma elabora la soluzione migliore, e questo si adatterà alla nuova situazione.

Download

Il programma è stato sviluppato con il framework .NET 2.0 e funziona con Mono 2.0 su Linux; i sorgenti non sono ancora disponibili dato che ho intenzione di riorganizzarli e di pubblicare una versione che utilizzi Silverlight.

E' disponibile l'eseguibile (non è richiesta installazione).

E' possibile anche provare Shortest Path via ClickOnce senza scaricare nulla.

Alcune considerazioni

Il problema del commesso viaggiatore è rilevante, oltre che da un punto di vista teorico, anche per molti problemi pratici (minimizzazione degli sprechi, ottimizzazione della logistica) ad esso riconducibili.

Infine, il fatto che le soluzioni di tali problemi non possano essere trovate con un calcolo deterministico, ma solo provate e rifinite iterazione dopo iterazione, mi ricorda le metodologie agili di sviluppo software, di cui sono sostenitore.