Ciclos Hamiltonianos
Dado un grafo, un ciclo hamiltoniano es un camino que recorre todos los nodos exactamente una vez y termina en el primer nodo.
Este algoritmo encuentra todos los ciclos hamiltonianos de un grafo. Puesto que necesitamos explorar todos los ciclos del grafo y existe la posibilidad de tener que retroceder en la exploración de un nodo si llegamos a un nodo ya visitado, este problema encaja con el planteamiento del esquema de vuelta atrás.
El procedimiento es el siguiente:
- Se fija un vértice de comienzo.
- Se recorre el árbol de búsqueda, retrocediendo a un punto anterior si llegamos a un nodo que no esté conectado o que ya se haya visitado anteriormente en el ciclo.
- El algoritmo recorre recursivamente los nodos del grafo, comprobando si cada nodo está conectado con el anterior de la ruta y comprobando si ya fue incluido previamente. Si ya se han añadido todos los nodos del grafo y la ruta es circular, tendremos una solución.
La figura muestra un ejemplo de ciclo hamiltoniano:
Ejemplos de aplicaciones prácticas:
- Planificación de rutas: Problema del Viajante de Comercio (PVC), planificación de viajes, rutas de medios de transporte...
- Diseño de circuitos electrónicos.
- Mapeo de genomas.
- Investigación de operaciones financieras.
En la sección de visualización podrás aprender su funcionamiento. Introduce los datos de entrada del grafo en la matriz de adyacencia. Para ello, en primer lugar indica el número de nodos del grafo y pulsa RESET. A continuación, rellena la matriz de adyacencia introduciendo un 1 si hay una arista entre los vértices y un 0 si no la hay y pulsa ACTUALIZAR. Podrás ver la evolución del algoritmo y de las estructuras de datos implicadas mediante los botones de control de la parte superior.