Problema de la trayectoria hamiltoniana

El problema del camino hamiltoniano es un tema que se discute en los campos de la teoría de la complejidad y la teoría de grafos . Decide si un grafo dirigido o no dirigido , G , contiene un camino hamiltoniano , un camino que visita cada vértice del grafo exactamente una vez. El problema puede especificar el inicio y el final del camino, en cuyo caso se deben identificar el vértice inicial s y el vértice final t . ^[1]

El problema del ciclo hamiltoniano es similar al problema de la ruta hamiltoniana, excepto que pregunta si un gráfico dado contiene un ciclo hamiltoniano . Este problema también puede especificar el inicio del ciclo. El problema del ciclo hamiltoniano es un caso especial del problema del viajante , que se obtiene fijando la distancia entre dos ciudades en uno si son adyacentes y en dos en caso contrario, y verificando que la distancia total recorrida sea igual a n. Si es así, la ruta es un ciclo hamiltoniano.

El problema de la trayectoria hamiltoniana y el problema del ciclo hamiltoniano pertenecen a la clase de problemas NP-completos , como se muestra en el libro de Michael Garey y David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness y la lista de 21 problemas NP-completos de Richard Karp . ^{[2] [3]}

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

• En una dirección, el problema de la trayectoria hamiltoniana para el grafo G se puede relacionar con el problema del ciclo hamiltoniano en un grafo H obtenido a partir de G añadiendo un nuevo vértice universal x , que conecta x con todos los vértices de G . Por lo tanto, encontrar una trayectoria hamiltoniana 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 sumar los 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 da a v' la misma vecindad 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, uno tendría que verificar cada camino posible en el grafo de entrada G. Hay n ! secuencias diferentes de vértices que podrían ser caminos hamiltonianos en un grafo de n vértices dado (y lo son, en un grafo completo ), por lo que un algoritmo de búsqueda de fuerza bruta que pruebe todas las secuencias posibles sería muy lento.

Un algoritmo temprano y exacto 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: las que deben estar en la ruta, las que no pueden estar en la ruta 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 la ruta se pueden eliminar, por lo que la búsqueda se hace cada vez más pequeña. El algoritmo también divide el grafo en componentes que se pueden resolver por separado, lo que reduce en gran medida 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 ² 2 ⁿ ). 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 buscar a partir de información ya calculada en el programa dinámico. ^{[6] [7]}

Andreas Björklund proporcionó un enfoque alternativo que utiliza 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, de contar las coberturas de ciclos, que se puede resolver calculando ciertos determinantes de matriz. Utilizando este método, mostró cómo resolver el problema del ciclo hamiltoniano en grafos arbitrarios de n vértices mediante un algoritmo de Monte Carlo en tiempo O(1,657 ⁿ ); para grafos bipartitos, este algoritmo se puede mejorar aún más hasta el tiempo O (1,415 ⁿ ). ^[8]

Para gráficos de grado máximo tres, una búsqueda cuidadosa hacia atrás puede encontrar un ciclo hamiltoniano (si existe uno) en el 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 una aplicación al problema 3-SAT . Como resultado, 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 trayectoria y ciclo hamiltonianos en computadoras convencionales, también se han estudiado en modelos no convencionales de computación. Por ejemplo, Leonard Adleman demostró que el problema de la trayectoria hamiltoniana se puede resolver utilizando una computadora de ADN . Aprovechando el paralelismo inherente a las reacciones químicas, el problema se puede resolver utilizando un número de pasos de reacción química lineal en el número de vértices del gráfico; 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 es crear una estructura similar a un grafo hecha de cables ópticos y divisores de haz que sean atravesados ​​por la luz para construir una solución para el problema. El punto débil de este enfoque es la cantidad de energía requerida, que es exponencial en el número de nodos.

El problema de encontrar un ciclo o camino hamiltoniano está en FNP ; el problema de decisión análogo es comprobar si existe un ciclo o camino hamiltoniano. Los problemas de ciclo hamiltoniano dirigido y no dirigido fueron dos de los 21 problemas NP-completos de Karp . Siguen siendo NP-completos incluso para tipos especiales de grafos, como:

• grafos bipartitos , ^[12]
• grafos planares no dirigidos de máximo grado tres, ^[13]
• grafos planos dirigidos con grado de entrada y grado de salida como máximo dos, ^[14]
• grafos bipartitos regulares triplanares no dirigidos y sin puentes ,
• Gráficos bipartitos 3-regulares y 3-conexos, ^[15]
• subgrafos del gráfico de cuadrícula cuadrada , ^[16]
• subgrafos cúbicos del gráfico de cuadrícula cuadrada. ^[17]

Sin embargo, para algunas clases especiales de gráficos, el problema se puede resolver en tiempo polinomial:

• Los gráficos planares 4-conectados son siempre hamiltonianos por un resultado debido a Tutte , y la tarea computacional de encontrar un ciclo hamiltoniano en estos gráficos se puede llevar a cabo en tiempo lineal ^[18] calculando una denominada ruta de Tutte.
• Tutte demostró este resultado al mostrar que cada grafo plano biconexo contiene un camino de Tutte. Los caminos de Tutte a su vez pueden calcularse en tiempo cuadrático incluso para grafos planos biconexos, ^[19] lo que puede usarse para encontrar ciclos hamiltonianos y ciclos largos en generalizaciones de grafos planos.

Juntando todas estas condiciones, queda abierto el interrogante de si los grafos planares bipartitos 3-regulares y 3-conexos deben contener siempre un ciclo hamiltoniano, en cuyo caso el problema restringido a esos grafos no podría ser NP-completo; véase la conjetura de Barnette .

En los grafos en los que todos los vértices tienen grado impar, un argumento relacionado con el lema del handshaking muestra que el número de ciclos hamiltonianos a través de cualquier arista fija es siempre par, por lo que si se da un ciclo hamiltoniano, entonces también debe existir un segundo. ^[20] Sin embargo, encontrar este segundo ciclo no parece ser una tarea computacional fácil. Papadimitriou definió la clase de complejidad PPA para encapsular problemas como este. ^[21]

El problema de la trayectoria hamiltoniana es NP-completo , lo que significa que una solución propuesta se puede verificar en tiempo polinomial . ^[1]

Un algoritmo de verificación para el camino hamiltoniano tomará como entrada un grafo G, vértice inicial s y vértice final t. Además, los verificadores requieren una solución potencial conocida como certificado , c. Para el problema del camino hamiltoniano, c consistiría en una cadena de vértices donde el primer vértice es el inicio del camino propuesto y el último es el final. ^[22] El algoritmo determinará si c es un camino hamiltoniano válido en G y, de ser así, lo aceptará.

Para decidir esto, el algoritmo primero verifica que todos los vértices en G aparecen exactamente una vez en c. Si esta verificación es satisfactoria, a continuación, el algoritmo se asegurará de que el primer vértice en c sea igual a s y el último vértice sea igual a t. Por último, para verificar que c es una ruta válida, el algoritmo debe verificar que cada arista entre los vértices en c sea de hecho una arista en G. Si alguna de estas verificaciones falla, el algoritmo rechazará. De lo contrario, aceptará. ^{[22] [23]}

El algoritmo puede verificar en tiempo polinomial si los vértices en G aparecen una vez en c. Además, se necesita tiempo polinomial para verificar los vértices de inicio y fin, así como las aristas entre los vértices. Por lo tanto, el algoritmo es un verificador en tiempo polinomial para el problema de la trayectoria hamiltoniana. ^[22]

Las redes en chip (NoC) se utilizan en sistemas informáticos y procesadores que sirven como comunicación para los componentes en chip. ^[24] El rendimiento de NoC está determinado por el método que utiliza para mover paquetes de datos a través de una red . ^[25] El problema de la ruta hamiltoniana se puede implementar como un método basado en rutas en el enrutamiento de multidifusión . Los algoritmos de multidifusión basados ​​en rutas determinarán si hay una ruta hamiltoniana desde el nodo de inicio hasta cada nodo final y enviarán paquetes a través de la ruta correspondiente. El uso de esta estrategia garantiza un enrutamiento sin bloqueos ni bloqueos activos , lo que aumenta la eficiencia del NoC. ^[26]

Los motores de renderizado son una forma de software que se utiliza en gráficos de 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 las mallas triangulares, el tiempo de renderizado se puede reducir hasta en un factor de tres. Esto se hace "ordenando los triángulos de modo que los triángulos consecutivos compartan una cara". ^[28] De esa manera, solo cambia un vértice entre cada triángulo consecutivo. Este orden existe si el gráfico dual de la malla triangular contiene una ruta hamiltoniana.

Medios relacionados con el problema de la trayectoria hamiltoniana en Wikimedia Commons