stringtranslate.com

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]

Reducciones

Reducción del problema de la trayectoria al problema del ciclo

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

Algoritmos

Fuerza bruta

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.

Caminos parciales

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.

Programación dinámica

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 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 un camino para ( S , v ) si y solo si v tiene un vecino w tal que existe un camino para ( Sv , w ), que se puede buscar a partir de información ya calculada en el programa dinámico. [6] [7]

Montecarlo

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 n ); para grafos bipartitos, este algoritmo se puede mejorar aún más hasta el tiempo O (1,415 n ). [8]

Retrocediendo

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 n ). [9]

Satisfacción booleana

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.

Métodos no convencionales

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.

Complejidad

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:

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

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]

Verificador de tiempo polinomial

La solución propuesta {s,w,v,u,t} forma una trayectoria hamiltoniana válida en el gráfico G.

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]

Aplicaciones

Redes en chip

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]

Gráficos de computadora

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.

Referencias

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

  1. ^ ab Sipser, Michael (2013). Introducción a la teoría de la computación (3.ª ed.). Cengage Learning. págs. 292–314.
  2. ^ Garey, Michael R; Johnson, David S. (1979). Computadoras e intratabilidad: una guía para la teoría de la NP-completitud . WH Freeman and Company. pág. 60.
  3. ^ ab Held, M.; Karp, RM (1965). "La construcción de algoritmos de programación dinámica discreta". IBM Systems Journal . 4 (2): 136–147. doi :10.1147/sj.42.0136. ISSN  0018-8670.
  4. ^ Reducción de ciclo hamiltoniano a camino hamiltoniano
  5. ^ Rubin, Frank (1974), "Un procedimiento de búsqueda para caminos y circuitos de Hamilton", Journal of the ACM , 21 (4): 576–80, doi : 10.1145/321850.321854 , S2CID  7132716
  6. ^ Bellman, Richard (enero de 1962). "Tratamiento de programación dinámica del problema del viajante". Revista de la ACM . 9 (1): 61–63. doi : 10.1145/321105.321111 . ISSN  0004-5411. S2CID  15649582.
  7. ^ Held, Michael; Karp, Richard M. (marzo de 1962). "Un enfoque de programación dinámica para problemas de secuenciación". Revista de la Sociedad de Matemáticas Industriales y Aplicadas . 10 (1): 196–210. doi :10.1137/0110015. ISSN  0368-4245.
  8. ^ Bjorklund, Andreas (octubre de 2010). "Sumas determinantes para hamiltonicidad no dirigida". 2010 IEEE 51st Annual Symposium on Foundations of Computer Science . IEEE. págs. 173–182. arXiv : 1008.0541 . doi :10.1109/focs.2010.24. ISBN. 978-1-4244-8525-3.
  9. ^ Iwama, Kazuo; Nakashima, Takuya (2007), Lin, Guohui (ed.), "Un algoritmo exacto mejorado para TSP de grafos cúbicos", Computing and Combinatorics , Lecture Notes in Computer Science, vol. 4598, Berlín, Heidelberg: Springer Berlin Heidelberg, págs. 108-117, doi :10.1007/978-3-540-73545-8_13, ISBN 978-3-540-73544-1, consultado el 7 de octubre de 2023
  10. ^ Adleman, Leonard (noviembre de 1994), "Cálculo molecular de soluciones a problemas combinatorios", Science , 266 (5187): 1021–1024, Bibcode :1994Sci...266.1021A, CiteSeerX 10.1.1.54.2565 , doi :10.1126/science.7973651, JSTOR  2885489, PMID  7973651 .
  11. ^ Mihai Oltean (2006). Un dispositivo basado en luz para resolver el problema de la trayectoria hamiltoniana . Computación no convencional. Springer LNCS 4135. págs. 217–227. arXiv : 0708.1496 . doi :10.1007/11839132_18.
  12. ^ "Prueba de que la existencia de un camino de Hamilton en un grafo bipartito es NP-completo". Stack Exchange en Ciencias de la Computación . Consultado el 18 de marzo de 2019 .
  13. ^ Garey, MR ; Johnson, DS ; Stockmeyer, L. (1974), "Algunos problemas NP-completos simplificados", Proc. 6.º Simposio ACM sobre teoría de la computación (STOC '74) , págs. 47-63, doi :10.1145/800119.803884, S2CID  207693360.
  14. ^ Plesńik, J. (1979), "La NP-completitud del problema del ciclo hamiltoniano en dígrafos planares con grado dos" (PDF) , Information Processing Letters , 8 (4): 199–201, doi :10.1016/0020-0190(79)90023-1.
  15. ^ Akiyama, Takanori; Nishizeki, Takao ; Saito, Nobuji (1980–1981), "NP-completitud del problema del ciclo hamiltoniano para grafos bipartitos", Journal of Information Processing , 3 (2): 73–76, MR  0596313.
  16. ^ Itai, Alon; Papadimitriou, Christos; Szwarcfiter, Jayme (1982), "Caminos de Hamilton en gráficos de cuadrícula", SIAM Journal on Computing , 4 (11): 676–686, CiteSeerX 10.1.1.383.1078 , doi :10.1137/0211056 .
  17. ^ Buro, Michael (2001), "Finales de Amazon simples y su conexión con circuitos de Hamilton en gráficos de subcuadrícula cúbica" (PDF) , Computers and Games , Lecture Notes in Computer Science, vol. 2063, pp. 250–261, CiteSeerX 10.1.1.40.9731 , doi :10.1007/3-540-45579-5_17, ISBN  978-3-540-43080-3.
  18. ^ Chiba, Norishige; Nishizeki, Takao (1989), "El problema del ciclo hamiltoniano es solucionable en tiempo lineal para grafos planares 4-conectados", Journal of Algorithms , 10 (2): 187–211, doi :10.1016/0196-6774(89)90012-6
  19. ^ Schmid, Andreas; Schmidt, Jens M. (2018), "Computing Tutte Paths", Actas del 45º Coloquio Internacional sobre Autómatas, Lenguajes y Programación (ICALP'18), próxima a aparecer.
  20. ^ Thomason, AG (1978), "Ciclos hamiltonianos y grafos con aristas coloreables de forma única", Advances in Graph Theory (Cambridge Combinatorial Conf., Trinity College, Cambridge, 1977), Annals of Discrete Mathematics, vol. 3, págs. 259-268, doi :10.1016/S0167-5060(08)70511-9, ISBN 9780720408430, Sr.  0499124.
  21. ^ Papadimitriou, Christos H. (1994), "Sobre la complejidad del argumento de paridad y otras pruebas ineficientes de existencia", Journal of Computer and System Sciences , 48 ​​(3): 498–532, CiteSeerX 10.1.1.321.7008 , doi :10.1016/S0022-0000(05)80063-7, MR  1279412 .
  22. ^ abc Bun, Mark (noviembre de 2022). "Teoría de la computación de la Universidad de Boston" (PDF) .
  23. ^ Bretscher, A (5 de febrero de 2021). "Apuntes de la semana 7 del curso CSCC63 de la Universidad de Toronto" (PDF) .
  24. ^ Bahn, Jun Ho. "Descripción general de la red en chip". Universidad de California en Irvine .
  25. ^ Satish, EG (2022). "Análisis comparativo del rendimiento de la topología de enrutamiento para la arquitectura NoC". Investigación emergente en informática, información, comunicación y aplicaciones . Apuntes de clase en ingeniería eléctrica. Vol. 790. págs. 431–440. doi :10.1007/978-981-16-1342-5_34. ISBN 978-981-16-1341-8– vía Springer.
  26. ^ Bahrebar, P.; Stroobandt, D. (2014). "Mejora de los métodos de enrutamiento basados ​​en Hamilton para redes en chip: un enfoque basado en modelos de giro". Conferencia y exposición sobre diseño, automatización y pruebas en Europa de 2014 : 1–4 – a través de IEEE.
  27. ^ Garsiel, Tali; Irish, Paul (5 de agosto de 2011). "Cómo funcionan los navegadores".
  28. ^ Arkin, Esther M.; Mitchell, Joseph SB; Held, Martin; Skiena, Steven S. "Triangulaciones hamiltonianas para renderizado rápido" (PDF) . Departamento de Ciencias de la Computación de la Universidad de Stony Brook .