Resumen

El problema del ciclo hamiltoniano es uno de los problemas combinatorios más explorados. Al ser un problema NP-completo, las aproximaciones heurísticas resultan más potentes que los algoritmos exactos de tiempo exponencial. Este trabajo presenta una heurística híbrida eficiente que se sitúa entre las aproximaciones complejas fiables y las aproximaciones simples más rápidas. El algoritmo propuesto es una combinación de heurística codiciosa, de transformación rotacional y de vértice inalcanzable que funciona en tres fases. En la primera fase, se crea una ruta inicial utilizando la búsqueda greedy depth first. Esta trayectoria inicial se convierte en una trayectoria hamiltoniana en la segunda fase mediante la transformación rotacional y la búsqueda codiciosa de profundidad. La tercera fase convierte la trayectoria hamiltoniana en un ciclo hamiltoniano mediante una transformación rotacional. El enfoque propuesto podría encontrar ciclos hamiltonianos a partir de un conjunto de grafos duros recogidos de la literatura, todas las instancias hamiltonianas (1000 a 5000 vértices) dadas en TSPLIB, y algunas instancias de FHCP Challenge Set. Además, el algoritmo tiene una complejidad temporal de O(n3) en el peor de los casos. El rendimiento del algoritmo se ha comparado con los algoritmos más avanzados y se ha descubierto que HybridHAM supera a los demás en términos de tiempo de ejecución.

• Materias:Control del proceso Desarrollo de procesos Programación Matemática Diagnóstico de fallos Optimización de procesos
• Subjects: Process development Mathematical Programming Fault diagnosis Process optimization
• Palabras claves:transformación rotacional, algoritmo, camino hamiltoniano, primera búsqueda, profundidad codiciosa, camino inicial, complejidad temporal en el peor de los casos, conjunto de retos fhcp, problema del ciclo hamiltoniano, enfoques complejos fiables
• Keywords:rotational transformation, algorithm, hamiltonian path, first search, greedy depth, initial path, worst case time complexity, fhcp challenge set, hamiltonian cycle problem, complex reliable approaches