miniatura|Camí hamiltonià 3D El problema del camí hamiltonià és un tema que es discuteix en els camps de la teoria de la complexitat i la teoria de grafs. Decideix si un graf dirigit o no dirigit, G, conté un camí hamiltonià, un camí que visita tots els vèrtexs del graf exactament una vegada. El problema pot especificar l'inici i el final del camí, en aquest cas s'han d'identificar el vèrtex inicial s i el vèrtex final t.
El problema del cicle hamiltonià és similar al problema del camí hamiltonià, excepte que pregunta si un gràfic donat conté un cicle hamiltonià. Aquest problema també pot especificar l'inici del cicle. El problema del cicle hamiltonià és un cas especial del problema del viatjant de comerç, que s'obté establint la distància entre dues ciutats a una si són adjacents i a dues en cas contrari, i verificant que la distància total recorreguda és igual a n. Si és així, la ruta és un cicle hamiltonià.
El problema del camí hamiltonià i el problema del cicle hamiltonià pertanyen a la classe de problemes NP-complets, tal com es mostra al llibre de Michael Garey i David S. Johnson Computers and Intractability: A Guide to the Theory of NP-Completeness i a la llista de 21 problemes NP-complets de Richard Karp.
Reduccions Reducció del problema del camí al problema del cicle Els problemes de trobar un camí hamiltonià i un cicle hamiltonià es poden relacionar de la següent manera:
En una direcció, el problema del camí hamiltonià per al graf G es pot relacionar amb el problema del cicle hamiltonià en un graf H obtingut de G afegint un nou vèrtex universal x, que connecta x a tots els vèrtexs de G. Per tant, trobar un camí hamiltonià no pot ser significativament més lent (en el pitjor dels casos, en funció del nombre de vèrtexs) que trobar un cicle hamiltonià. En l'altra direcció, el problema del cicle hamiltonià per a un graf G és equivalent al problema del camí hamiltonià en el graf H obtingut sumant els vèrtexs terminals (grau u) s i t units respectivament a un vèrtex v de G i a v', una còpia dividida de v que dóna a v''' el mateix veïnat que v. El camí hamiltonià en H que passa pels vèrtex al cicle hamiltonià de G que passa .Reduction from Hamiltonian cycle to Hamiltonian path
Algorismes Força bruta Per decidir si un graf té un camí hamiltonià, s'hauria de comprovar cada camí possible al graf d'entrada G. Hi ha n ! seqüències diferents de vèrtexs que podrien ser camins hamiltonians en un graf de n vèrtexs donat (i ho són, en un graf complet), de manera que un algorisme de cerca per força bruta que provi totes les seqüències possibles seria molt lent.
Camins parcials Un dels primers algorismes exactes per trobar un cicle hamiltonià en un graf dirigit va ser l'algorisme enumeratiu de Martello. Un procediment de cerca de Frank Rubin divideix les arestes del graf en tres classes: les que han d'estar al camí, les que no poden estar al camí i les indecises. A mesura que avança la cerca, un conjunt de regles de decisió classifica les arestes indecises i determina si s'ha d'aturar o continuar la cerca. Les arestes que no poden estar al camí es poden eliminar, de manera que la cerca es fa contínuament més petita. L'algorisme també divideix el graf en components que es poden resoldre per separat, reduint considerablement la mida de la cerca. A la pràctica, aquest algorisme continua sent el més ràpid.
Programació dinàmica A més, es pot utilitzar un algorisme de programació dinàmica de Bellman, Held i Karp per resoldre el problema en un temps O(n² 2n)). En aquest mètode, es determina, per a cada conjunt S de vèrtexs i cada vèrtex v de S, si hi ha un camí que cobreixi exactament els vèrtexs de S i acabi a v. Per a cada elecció de S i v, existeix un camí per a ( S, v) si i només si v té un veí w tal que existeix un camí per a ( S − v, w ), que es pot consultar a partir d'informació ja calculada al programa dinàmic.
Monte Carlo Andreas Björklund va proporcionar un enfocament alternatiu utilitzant el principi d'inclusió-exclusió per reduir el problema de comptar el nombre de cicles hamiltonians a un problema de comptatge més simple, de comptar cobertures de cicles, que es pot resoldre calculant certs determinants matricials. Utilitzant aquest mètode, va mostrar com resoldre el problema del cicle hamiltonià en gràfics de n'' vèrtexs arbitraris mitjançant un algorisme de Monte Carlo en temps O(1.657n); per a gràfics bipartits, aquest algorisme es pot millorar encara més fins al temps O (1.415n).
Retrocés Per a gràfics de grau màxim tres, una cerca de retrocés acurada pot trobar un cicle hamiltonià (si n'hi ha) en un temps O(1.251n).
Satisfactibilitat booleana Els camins hamiltonians es poden trobar utilitzant un solucionador SAT. El camí hamiltonià és NP-complet, és a dir, es pot reduir al problema 3-SAT. Com a resultat, trobar una solució al problema del camí hamiltonià és equivalent a trobar una solució per a 3-SAT.
Mètodes no convencionals A causa de la dificultat de resoldre els problemes de camins i cicles hamiltonians en ordinadors convencionals, també s'han estudiat en models informàtics no convencionals. Per exemple, Leonard Adleman va demostrar que el problema del camí hamiltonià es pot resoldre mitjançant un ordinador d'ADN. Aprofitant el paral·lelisme inherent a les reaccions químiques, el problema es pot resoldre mitjançant diversos passos de reacció química lineals en el nombre de vèrtexs del gràfic; tanmateix, requereix un nombre factorial de molècules d'ADN per participar en la reacció..
També s'ha proposat una solució òptica al problema hamiltonià. La idea és crear una estructura semblant a un graf feta de cables òptics i divisors de feix que són travessats per la llum per tal de construir una solució per al problema. El punt feble d'aquest plantejament és la quantitat d'energia necessària, que és exponencial en el nombre de nodes.
Complexitat El problema de trobar un cicle o camí hamiltonià és en FNP; el problema de decisió anàleg és provar si existeix un cicle o camí hamiltonià. Els problemes de cicle hamiltonià dirigit i no dirigit eren dos dels 21 problemes NP-complets de Karp. Romanen NP-complets fins i tot per a tipus especials de grafs, com ara:
gràfics bipartits, gràfics planars no dirigits de grau màxim tres,. gràfics planars dirigits amb grau interior i grau exterior com a màxim dos,. gràfics bipartits regulars 3-planars sense direcció sense pont, Grafs bipartits 3-connexos 3-regulars,. subgrafs del gràfic de malla quadrada,. subgrafs cúbics del gràfic de malla quadrada..
Tanmateix, per a algunes classes especials de grafs, el problema es pot resoldre en temps polinòmic:
Els grafs planars 4-connexos són sempre hamiltonians per un resultat degut a Tutte, i la tasca computacional de trobar un cicle hamiltonià en aquests grafs es pot dur a terme en temps lineal calculant un anomenat camí de Tutte. Tutte va demostrar aquest resultat mostrant que cada graf planar 2-connex conté un camí de Tutte. Els camins de Tutte, al seu torn, es poden calcular en temps quadràtic fins i tot per a grafs planars 2-connexos, que es poden utilitzar per trobar cicles hamiltonians i cicles llargs en generalitzacions de grafs planars.
Si sumem totes aquestes condicions, queda obert si els grafs planars bipartits 3-regulars i 3-connexos han de contenir sempre un cicle hamiltonià, en aquest cas el problema restringit a aquests grafs no podria ser NP-complet; vegeu la conjectura de Barnette.
En grafs en què tots els vèrtexs tenen grau senar, un argument relacionat amb el lema de la transposició mostra que el nombre de cicles hamiltonians a través de qualsevol aresta fixa és sempre parell, de manera que si es dóna un cicle hamiltonià, també n'ha d'existir un segon.. Tanmateix, trobar aquest segon cicle no sembla una tasca computacional fàcil. Papadimitriou va definir la classe de complexitat PPA per encapsular problemes com aquest..
Verificador de temps polinòmic miniatura|221x221px|La solució proposada {s,w,v,u,t} forma un camí hamiltonià vàlid en el graf G. El problema del camí hamiltonià és NP, és a dir, que una solució proposada es pot verificar en temps polinòmic.
Un algorisme verificador per a un camí hamiltonià prendrà com a entrada un graf G, amb el vèrtex inicial s i el vèrtex final t. A més, els verificadors requereixen una solució potencial coneguda com a certificat, c. Per al problema del camí hamiltonià, c consistiria en una cadena de vèrtexs on el primer vèrtex és l'inici del camí proposat i l'últim és el final. L'algorisme determinarà si c és un camí hamiltonià vàlid a G i, si és així, l'acceptarà.
Per decidir això, l'algorisme primer verifica que tots els vèrtexs de G apareixen exactament una vegada a c. Si aquesta comprovació passa, a continuació, l'algorisme s'assegurarà que el primer vèrtex de c sigui igual a s i l'últim vèrtex sigui igual a t. Finalment, per verificar que c és un camí vàlid, l'algorisme ha de comprovar que cada aresta entre els vèrtexs de c sigui realment una aresta de G. Si alguna d'aquestes comprovacions falla, l'algorisme rebutjarà. En cas contrari, acceptarà.
L'algorisme pot comprovar en temps polinòmic si els vèrtexs de G apareixen una vegada a c. A més, es necessita temps polinòmic per comprovar els vèrtexs inicial i final, així com les arestes entre els vèrtexs. Per tant, l'algorisme és un verificador de temps polinòmic per al problema del camí hamiltonià.
Aplicacions Xarxes en xip Les xarxes en xip (NoC) s'utilitzen en sistemes informàtics i processadors que serveixen com a comunicació per a components en xip. El rendiment del NoC està determinat pel mètode que utilitza per moure paquets de dades a través d'una xarxa. El problema del camí hamiltonià es pot implementar com un mètode basat en camins en l'encaminament multicast. Els algorismes multicast basats en camins determinaran si hi ha un camí hamiltonià des del node inicial fins a cada node final i enviaran paquets a través del camí corresponent. L'ús d'aquesta estratègia garanteix un encaminament sense interbloquejos i sense bloquejos directes, augmentant l'eficiència del NoC.
Gràfics per ordinador Els motors de renderització són una forma de programari utilitzat en gràfics per ordinador per generar imatges o models a partir de dades d'entrada. En la renderització de gràfics tridimensionals, una entrada comuna al motor és una malla de polígons. El temps que es triga a renderitzar l'objecte depèn de la velocitat a la qual es rep l'entrada, és a dir, com més gran sigui l'entrada, més llarg serà el temps de renderització. Per a les malles triangulars, però, el temps de renderització es pot reduir fins a un factor de tres. Això es fa mitjançant "ordenant els triangles de manera que els triangles consecutius comparteixin una cara". D'aquesta manera, només canvia un vèrtex entre cada triangle consecutiu. Aquest ordre existeix si el gràfic dual de la malla triangular conté un camí hamiltonià.
Referències
Categoria:Problemes matemàtics