|
|
Uno schema consolidato nella progettazione di algoritmi prevede la costruzione della soluzione iniziale con un algoritmo di tipo Greedy e l’applicazione successiva di una Ricerca Locale. Analizziamo il TSP che è l’acronimo di “Traveling Salesman Problem”, ovvero il problema del commesso viaggiatore. Siano date n città, dij la distanza tra città i e lacittà j ed un intero k. È possibile partire da una città, attraversare ogni città esattamente una volta, e ritornare alla città di partenza percorrendo una distanza complessiva non superiore a k.
Si può calcolare una soluzione, non necessariamente ottima, con i seguente schema:
soluzione iniziale con euristica “Nearest Neighbor”
miglioramento con 2-opt exchange
L’idea semplice della Nearest Neighbor è quella di selezionare a caso un nodo di partenza. Ad ogni passo ci si sposta sul nodo più vicino al nodo corrente. Si ripete questa visita sino a quando tutti i nodi sono visitati. L’ultimo passo prevede di unire il nodo ultimo visitato con quello più vicino per completare il circuito.
Data una soluzione, ovvero un circuito, l’intorno “2-opt exchanges” prevede l’individuazione di due archi, la loro eliminazione e la ricreazione del circuito usando due archi non appartenenti alla soluzione. La speranza è quella che scambiando gli archi si migliori la soluzione.
Tutto quanto riportato in questa pagina è a puro scopo informativo personale. Se non ti trovi in accordo con quanto riportato nella pagina, vuoi fare delle precisazioni, vuoi fare delle aggiunte o hai delle proposte e dei consigli da dare, puoi farlo mandando un email. Ogni indicazione è fondamentale per la continua crescita del sito.