El problema de la trayectoria hamiltoniana es un tema discutido en los campos de la teoría de la complejidad y la teoría de grafos . Decide si un gráfico dirigido o no dirigido , G , contiene un camino hamiltoniano , un camino que visita cada vértice del gráfico exactamente una vez. El problema puede especificar el inicio y el final de la ruta, en cuyo caso se deben identificar el vértice inicial sy el vértice final t . [1]
El problema del ciclo hamiltoniano es similar al problema de la trayectoria hamiltoniana, excepto que pregunta si una gráfica determinada 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 estableciendo la distancia entre dos ciudades en uno si son adyacentes y dos en caso contrario, y verificando que la distancia total recorrida es igual a n. Si es así, la ruta es un ciclo hamiltoniano.
El problema de la ruta hamiltoniana y el problema del ciclo hamiltoniano pertenecen a la clase de problemas NP-completos , como se muestra en el libro Computers and Intractability: A Guide to the Theory of NP-Completeness de Michael Garey y David S. Johnson y en la lista de 21 NP de Richard Karp. -Problemas completos . [2] [3]
Los problemas de encontrar una trayectoria hamiltoniana y un ciclo hamiltoniano se pueden relacionar de la siguiente manera:
Para decidir si un gráfico tiene una ruta hamiltoniana, habría que verificar cada ruta posible en el gráfico de entrada G. ¡Hay n ! diferentes secuencias de vértices que podrían ser caminos hamiltonianos en un gráfico de n vértices dado (y lo son, en un gráfico completo ), por lo que un algoritmo de búsqueda de fuerza bruta que pruebe todas las secuencias posibles sería muy lento.
Uno de los primeros algoritmos exactos para encontrar un ciclo hamiltoniano en un gráfico dirigido fue el algoritmo enumerativo de Martello. [3] Un procedimiento de búsqueda de Frank Rubin [5] divide los bordes del gráfico en tres clases: los que deben estar en el camino, los que no pueden estar en el camino y los indecisos. A medida que avanza la búsqueda, un conjunto de reglas de decisión clasifica los bordes indecisos y determina si se debe detener o continuar la búsqueda. El algoritmo divide el gráfico en componentes que se pueden resolver por separado.
Además, se puede utilizar un algoritmo de programación dinámica de Bellman, Held y Karp para resolver el problema en el tiempo O ( n 2 2 n ). 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 una ruta para ( S , v ) si y solo si v tiene un vecino w tal que exista una ruta 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 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, de contar las coberturas de ciclos, que puede resolverse calculando ciertos determinantes matriciales. Utilizando este método, mostró cómo resolver el problema del ciclo hamiltoniano en gráficos arbitrarios de n -vértices mediante un algoritmo de Monte Carlo en el tiempo O (1,657 n ); para gráficos bipartitos, este algoritmo se puede mejorar aún más hasta el tiempo O (1,415 n ). [8]
Para gráficos de grado tres máximo, una búsqueda cuidadosa de retroceso puede encontrar un ciclo hamiltoniano (si existe) en el tiempo O (1,251 n ). [9]
Las rutas hamiltonianas se pueden encontrar utilizando un solucionador SAT . La ruta hamiltoniana es NP-Completa, lo que significa que se puede reducir al problema 3-SAT . Como resultado, encontrar una solución al problema del camino hamiltoniano equivale a encontrar una solución para 3-SAT.
Debido a la dificultad de resolver los problemas de ciclo y trayectoria hamiltoniana 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 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 lineales en el número de vértices del gráfico; sin embargo, se 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 gráfico hecha de cables ópticos y divisores de haz que son atravesados por la luz para construir una solución al 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 consiste en comprobar si existe un ciclo o trayectoria hamiltoniana. Los problemas del 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 gráficos, como:
Sin embargo, para algunas clases especiales de gráficos, el problema se puede resolver en tiempo polinomial:
Juntando todas estas condiciones, queda abierto si los gráficos planos bipartitos regulares 3 conectados siempre deben contener un ciclo hamiltoniano, en cuyo caso el problema restringido a esos gráficos no podría ser NP-completo; ver la conjetura de Barnette .
En gráficos en los que todos los vértices tienen grados impares, un argumento relacionado con el lema del apretón de manos muestra que el número de ciclos hamiltonianos a través de cualquier borde fijo 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 ruta 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 la ruta hamiltoniana tomará como entrada un gráfico G, un vértice inicial s y un vértice final t. Además, los verificadores requieren una posible solución 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 pasa, a continuación, el algoritmo garantizará 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 comprobaciones falla, el algoritmo la rechazará. En caso contrario, aceptará. [22] [23]
El algoritmo puede verificar en tiempo polinómico si los vértices en G aparecen una vez en c. Además, se necesita tiempo polinómico para verificar los vértices inicial y final, así como los bordes entre los vértices. Por lo tanto, el algoritmo es un verificador de tiempo polinómico para el problema de la trayectoria hamiltoniana. [22]
Las redes en chip se utilizan en sistemas informáticos y procesadores que sirven como comunicación para 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 existe una ruta hamiltoniana desde el nodo inicial hasta cada nodo final y enviarán paquetes a través de la ruta correspondiente. La utilización de esta estrategia garantiza un enrutamiento libre de interbloqueos y 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 por computadora para generar imágenes o modelos a partir de datos de entrada. [27] En la representación de gráficos tridimensionales , una entrada común al motor es una malla poligonal . El tiempo que lleva 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 renderización. 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 un vértice cambia entre cada triángulo consecutivo. Este orden existe si la gráfica dual de la malla triangular contiene una trayectoria hamiltoniana.
Medios relacionados con el problema de la ruta hamiltoniana en Wikimedia Commons
