Quale approccio produce il tour più breve nel problema TSP: vicino più prossimo o algoritmi genetici?

Question

Negli ultimi giorni ho notato un paio di noreferrer siti che hanno dimostrato la soluzione TS utilizzando algoritmi genetici.

Qual è l'approccio produce il tour più breve nel problema TSP:? Vicino più prossimo o algoritmi genetici

Answer 1

Dal momento che né tecnica garantisce una soluzione ottimale, il tuo chilometraggio può variare. Con un po 'di fortuna, sia tecnica può fuori eseguire l'altro. Entrambe le tecniche hanno vantaggi e svantaggi.

Vicino più prossimo: + veloce, + semplice, -di solito non ottimale

Algoritmo Genetico: -slower, complesso -più, + soluzioni tendenza verso ottimale nel tempo

La grande differenza è che gli algoritmi randomizzati quali annealing simulato e algoritmi genetici possono continuare a migliorare nel tempo - il più a lungo si lascia correre, più probabilità hai di una soluzione ottimale (anche se non ci sono garanzie).

Dal momento che NN è veloce, non c'è nulla ti impedisce di combinare le tecniche. Esegui NN per trovare una soluzione di partenza, eventualmente-better-than-casuale. Quindi, alimentare tale soluzione nel vostro algoritmo genetico e farlo funzionare fino a quando si sente è appropriato.

Se siete interessati a soluzioni ottimali, controllare le Lin-Kernighan euristica e Linear Programming . Entrambi sono stati utilizzati per trovare le soluzioni ottimali per i grandi tour tra cui questa soluzione un rel="nofollow 85.900 Tour della città e un 24.978 città Svezia giro .

Il Georgia Tech TSP sito è una grande risorsa.