3-opciones

En optimización, 3-opt es una heurística de búsqueda local simple para encontrar soluciones aproximadas al problema del viajante de comercio y problemas de optimización de red relacionados. En comparación con el algoritmo 2-opt más simple , es más lento pero puede generar soluciones de mayor calidad.

El análisis 3-opt implica eliminar tres aristas de la solución actual al problema, creando tres sub-recorridos. Hay ocho formas de conectar estos sub-recorridos nuevamente en un solo recorrido, uno de los cuales consiste en las tres aristas eliminadas. Estas reconexiones se analizan para encontrar la óptima. Este proceso se repite luego para un conjunto diferente de 3 conexiones, hasta que se hayan probado todas las combinaciones posibles en una red. Un solo paso a través de todos los triples de aristas tiene una complejidad temporal de . ^[1] El 3-opt iterado, en el que los pases se repiten hasta que no se pueden encontrar más mejoras, tiene una complejidad temporal mayor. ${\displaystyle O(n^{3})}$

• Heurística de Lin-Kernighan

• BOCK, F. (1958). "Un algoritmo para resolver problemas de optimización de redes de vendedores ambulantes y similares". Investigación de operaciones . 6 (6).
• Lin, Shen (1965). "Soluciones informáticas del problema del viajante de comercio". Bell System Technical Journal . 44 (10). Instituto de Ingenieros Eléctricos y Electrónicos (IEEE): 2245– 2269. doi :10.1002/j.1538-7305.1965.tb04146.x. ISSN  0005-8580.
• Lin, S.; Kernighan, BW (1973). "Un algoritmo heurístico eficaz para el problema del viajante de comercio". Investigación de operaciones . 21 (2). Instituto de Investigación de Operaciones y Ciencias de la Gestión (INFORMS): 498– 516. doi :10.1287/opre.21.2.498. ISSN  0030-364X.
• Sipser, Michael (2006). Introducción a la teoría de la computación . Boston: Thomson Course Technology. ISBN 0-534-95097-3.OCLC 58544333  .