Algoritmo per generare soluzioni TSP casuale

Question

L'euristica più comuni per risolvere il problema TSP (in particolare l'euristica Kernighan-Lin) richiedono di lavoro su un giro generato in modo casuale e per migliorare la soluzione partendo da questo. Tuttavia, l'unico modo in cui mi si avvicinò con per farlo è quello di generare una permutazione casuale dei vertici e per verificare se si tratta di una soluzione o no.

Per le grandi istanze del problema (ad esempio, 1000 i vertici) questo processo può richiedere del tempo. C'è un altro modo intelligente per generare un giro a caso per il problema TSP più veloce ?? Si noti che sto cercando un tour, a qualunque costo, e non una soluzione ottimale.

Grazie in anticipo

Answer 1

Si potrebbe semplicemente creare un array che contiene le città di THS problema e poi mischiare a caso tale matrice (ci sono metodi che potrebbero fare questo). La matrice risultante è infatti una permutazione casuale.

Answer 2

Se siete solo in cerca di qualsiasi tour, è possibile utilizzare Larghezza o ricerca in profondità per generare un percorso durante il contrassegno i nodi visitati.

Answer 3

Si desidera utilizzare uno spazio-riempimento-curva.