Problema de la trayectoria hamiltoniana

Los problemas de encontrar un camino hamiltoniano y un ciclo hamiltoniano pueden relacionarse de la siguiente manera:

• En cierto sentido, el problema del camino hamiltoniano para el grafo G puede relacionarse con el problema del ciclo hamiltoniano en un grafo H obtenido a partir de G mediante la adición de un nuevo vértice universal x , que conecta x con todos los vértices de G. Por lo tanto, encontrar un camino hamiltoniano no puede ser significativamente más lento (en el peor de los casos, en función del número de vértices) que encontrar un ciclo hamiltoniano.
• En la otra dirección, el problema del ciclo hamiltoniano para un grafo G es equivalente al problema del camino hamiltoniano en el grafo H obtenido al agregar vértices terminales ( de grado uno) s y t unidos respectivamente a un vértice v de G y a v', una copia escindida de v que le da a v' el mismo vecindario que v . El camino hamiltoniano en H que pasa por los vértices ⁠${\displaystyle svx-\cdots -yv'-t}$⁠ corresponde al ciclo hamiltoniano en G que pasa por ⁠${\displaystyle vx-\cdots -y(-v)}$⁠ . ^{[ 4 ]}

Para decidir si un grafo tiene un camino hamiltoniano, habría que comprobar cada posible camino en el grafo de entrada G. Hay n ! secuencias diferentes de vértices que podrían ser caminos hamiltonianos en un grafo dado de n vértices (y lo son, en un grafo completo ), por lo que un algoritmo de búsqueda por fuerza bruta que pruebe todas las secuencias posibles sería muy lento.

Un algoritmo exacto temprano para encontrar un ciclo hamiltoniano en un grafo dirigido fue el algoritmo enumerativo de Martello. ^{[ 3 ]} Un procedimiento de búsqueda de Frank Rubin ^{[ 5 ]} divide las aristas del grafo en tres clases: aquellas que deben estar en el camino, aquellas que no pueden estar en el camino y las indecisas. A medida que avanza la búsqueda, un conjunto de reglas de decisión clasifica las aristas indecisas y determina si se debe detener o continuar la búsqueda. Las aristas que no pueden estar en el camino se pueden eliminar, por lo que la búsqueda se reduce continuamente. El algoritmo también divide el grafo en componentes que se pueden resolver por separado, lo que reduce considerablemente el tamaño de la búsqueda. En la práctica, este algoritmo sigue siendo el más rápido.

Además, se puede utilizar un algoritmo de programación dinámica de Bellman, Held y Karp para resolver el problema en tiempo O( n² ^{2n )} . En este método, se determina, para cada conjunto S de vértices y cada vértice v en S , si existe un camino que cubra exactamente los vértices en S y termine en v . Para cada elección de S y v , existe un camino para ( S , v ) si y solo si v tiene un vecino w tal que existe un camino para ( S − v , w ), que se puede consultar a partir de la información ya calculada en el programa dinámico. ^{[ 6 ] [ 7 ]}

Andreas Björklund propuso un enfoque alternativo utilizando el principio de inclusión-exclusión para reducir el problema de contar el número de ciclos hamiltonianos a un problema de conteo más simple: el de contar las coberturas de ciclos, que puede resolverse calculando ciertos determinantes de matrices. Mediante este método, demostró cómo resolver el problema de los ciclos hamiltonianos en grafos arbitrarios de n vértices mediante un algoritmo de Monte Carlo en tiempo O(1,657 ⁿ ); para grafos bipartitos, este algoritmo puede mejorarse aún más hasta un tiempo O (1,415 ⁿ ). ^{[ 8 ]}

Para grafos de grado máximo tres, una búsqueda de retroceso cuidadosa puede encontrar un ciclo hamiltoniano (si existe) en tiempo O(1,251 ⁿ ). ^{[ 9 ]}

Los caminos hamiltonianos se pueden encontrar utilizando un solucionador SAT . El camino hamiltoniano es NP-completo, lo que significa que se puede reducir mediante mapeo al problema 3-SAT . Por lo tanto, encontrar una solución al problema del camino hamiltoniano es equivalente a encontrar una solución para 3-SAT.

Debido a la dificultad de resolver los problemas de la ruta hamiltoniana y del ciclo en computadoras convencionales, también se han estudiado en modelos de computación no convencionales. Por ejemplo, Leonard Adleman demostró que el problema de la ruta hamiltoniana puede resolverse utilizando una computadora de ADN . Aprovechando el paralelismo inherente a las reacciones químicas, el problema puede resolverse utilizando un número de pasos de reacción química lineal con respecto al número de vértices del grafo; sin embargo, requiere un número factorial de moléculas de ADN para participar en la reacción. ^{[ 10 ]}

También se ha propuesto una solución óptica al problema hamiltoniano. ^{[ 11 ]} La idea consiste en crear una estructura similar a un grafo, formada por cables ópticos y divisores de haz, que la luz recorre para construir una solución al problema. El punto débil de este enfoque es la cantidad de energía requerida, que es exponencial con respecto al número de nodos.

Las redes en chip (NoC) se utilizan en sistemas informáticos y procesadores para la comunicación entre componentes integrados en el chip. ^{[ 24 ]} El rendimiento de una NoC está determinado por el método que utiliza para mover paquetes de datos a través de la red . ^{[ 25 ]} El problema de la ruta hamiltoniana se puede implementar como un método basado en rutas en el enrutamiento multicast . Los algoritmos multicast basados ​​en rutas determinan si existe una ruta hamiltoniana desde el nodo de inicio hasta cada nodo final y envían los paquetes a través de la ruta correspondiente. La utilización de esta estrategia garantiza un enrutamiento libre de interbloqueos y bloqueos permanentes , lo que aumenta la eficiencia de la NoC. ^{[ 26 ]}

Los motores de renderizado son un tipo de software utilizado en gráficos por computadora para generar imágenes o modelos a partir de datos de entrada. ^{[ 27 ]} En el renderizado de gráficos tridimensionales , una entrada común al motor es una malla poligonal . El tiempo que tarda en renderizar el objeto depende de la velocidad a la que se recibe la entrada, lo que significa que cuanto mayor sea la entrada, mayor será el tiempo de renderizado. Sin embargo, para mallas triangulares, el tiempo de renderizado puede reducirse hasta en un factor de tres. Esto se logra "ordenando los triángulos de manera que los triángulos consecutivos compartan una cara". ^{[ 28 ]} De esta forma, solo cambia un vértice entre cada triángulo consecutivo. Este ordenamiento existe si el grafo dual de la malla triangular contiene un camino hamiltoniano.