El algoritmo de escalada se utiliza para resolver el problema del viajante.
Se ha demostrado que el problema TSP es NP completo. Este tipo de problema no se puede resolver con algoritmos exactos, solo se puede resolver con algoritmos similares.
Los problemas de TSP se dividen en dos categorías: TSP simétrico y TSP asimétrico.
Este artículo resuelve el problema del TSP simétrico.
Supuesto: A representa la ciudad A, B representa la ciudad B, D(A->B) es la distancia de la ciudad A a la ciudad B, de manera similar, D(B->a) es la distancia de la ciudad B a la ciudad a.
En TSP simétrico, d(a->B) = D(B->a), formando un grafo no dirigido entre ciudades.
En TSP asimétrico, d(a->B)≠D(B->a), formando un grafo dirigido entre ciudades.
En la vida real, pueden darse situaciones como calles de sentido único, accidentes de tráfico y diferentes precios de billetes de avión de ida y vuelta. , lo que rompe la simetría.
El algoritmo de escalada es un método de optimización local que utiliza un método heurístico. La explicación intuitiva es la siguiente:
El algoritmo de escalada de montañas, como su nombre indica, consiste en escalar una montaña y detenerse cuando encuentre el primer pico como resultado del algoritmo. Por lo tanto, el algoritmo de escalada puede utilizar fácilmente la solución óptima local A como salida del algoritmo. Nuestro objetivo es encontrar la solución óptima global b.
Como se muestra en la figura siguiente, aunque hay muchos máximos locales en esta figura, el algoritmo de recocido simulado aún se puede usar para encontrar el máximo global.
Ver comentarios para explicaciones necesarias.
Para conocer la fórmula para calcular la distancia entre ciudades en función de la longitud y la latitud, consulte ¿Calcular la distancia entre dos puntos de longitud y latitud? (Fórmula de Havershin)
La fuente de datos de inicialización aquí puede utilizar los datos proporcionados en TSPLIB. Este programa explica aproximadamente la implementación del algoritmo de escalada.
Escrito en una noche de insomnio
Como novato, ¿puedes comunicarte entre sí en el área de comentarios para acelerar tu crecimiento y el mío? .