Definición del problema
Un ciclo hamiltoniano, también llamado circuito de Hamilton, ciclo de Hamilton, es un ciclo de gráfico (es decir, en circuito cerrado) a través de un gráfico de visitas que debe visitar cada nodo exactamente una ves. Por convención, la gráfica trivial en un solo nodo se considera que posee un ciclo de Hamilton, pero el gráfico conectado a dos nodos no lo es. Un gráfico que posee un ciclo hamiltoniano se dice que es un grafo hamiltoniano . El ciclo hamiltoniano es el nombre de Sir William Rowan Hamilton, quien ideó un puzzle en el que este camino a lo largo de los bordes poliedro de un dodecaedro se solicitó (el juego Icosian ).
Un ciclo hamiltoniano de un grafo, que sin embargo, sólo da resultados correctos para los grafos no dirigidos. Del mismo modo, todos los ciclos hamiltonianos de un grafo dado se puede encontrar utilizando el comando HamiltonianCycle [g, todo] en el Mathematica paquete Combinatorica. Tenga en cuenta que estos comandos devolverá el índice del primer punto como el último punto y con el fin de indicar que el resultado es un ciclo cerrado. Una lista de todos los ciclos precalculadas hamiltoniano para muchos gráficos nombre se puede obtener utilizando GraphData gráfico ["HamiltonianCycles"], donde estos ciclos no duplicar el índice de inicio y finalización, y las dos orientaciones de los ciclos se incluyen (de manera que
Un circuito hamiltoniano, o de Hamilton, es un grago G es un camino que comienza y termina en un mismo vértice, pasando exactamente una vez por cada vértice.
Determinar si un grafo no dirigido dado tiene un ciclo hamiltoniano.
- Aunque el problema es muy parecido al del circuito de Euler, no se conoce ningún algoritmo eficiente para resolverlo, en tiempo polinomial.
- El problema del ciclo hamiltoniano pertenece a un conjunto de problemas de difícil solución llamado problemas NP-completos.
- La solución requiere básicamente evaluar todas las posibilidades, dando lugar a un orden de complejidad exponencial o factorial.
- Otra posibilidad es usar métodos heurísticos, que pueden funcionar en algunos casos y en otros no.
El problema de encontrar un ciclo hamiltoniano es NP- completo por lo que la única manera conocida para determinar si un general grafo tiene un ciclo hamiltoniano es llevar a cabo una búsqueda exhaustiva . Rubin (1974) describe un procedimiento de búsqueda eficiente, que puede encontrar algunas o todas las rutas y circuitos de Hamilton en un grafo con las deducciones que reducen en gran medida marcha atrás y las conjeturas. Un algoritmo probabilístico también puede ser útil para encontrar los ciclos hamiltonianos y caminos.
El análisis asintótico es exponencial ya que no sabemos cuantos pasos hará nuestro algoritmo porque tenemos que visitar cada vértice y también analiza si este ya fue visitado anteriormente y es : (n!
Estructura de Datos utilizadas
En este algoritmo lo que utilice fue grafos ya que contamos con nodos y vértices que son los que unen un determinado grafo en especial los grafos no dirigidos. Y también necesite listas ya que necesitamos punteros para poder ir dirigiéndose de un nodo a otro y así sucesivamente.
Aplicaciones al Ciclo Hamilton
Un problema muy común en el ciclo de Hamilton es el problema del viajero que es de optimización combinatoria. El numero finito (n!), exponencial de ciclos hamiltonianos hace que no podamos verificar si un ciclo hamiltoniano en particular sea minimo en tiempo acotado por un polinomio en n. Es decir que el problema del agente viajero es NP- completo.
Lo que se tiene que realizar en este problema es de que te dan una lista de ciudades y sus costos lo que tenemos que encontrar el recorrido mas corto posible que tiene que visitar todas las ciudades que se dan una sola ves.
Otra de las aplicaciones que tiene el ciclo de hamilton y que presenta este algoritmo es el Juego Icosian.
El juego Icosian, también llamado el juego de Hamilton (Ball y Coxeter 1987, p. 262), es el problema de encontrar un ciclo hamiltoniano en los bordes de un dodecaedro , es decir, un camino de tal manera que cada vértice es visitado una sola vez, no borde es visitado dos veces, y el punto final es el mismo que el punto de partida (a la izquierda la figura). The puzzle was distributed commercially as a pegboard with holes at the nodes of the dodecahedral graph , illustrated above (right figure). 
El puzzle se distribuyó comercialmente como una lámina de cartón con agujeros en los nudos del grafo dodecaedro , que se ilustra arriba (figura de la derecha). The Icosian Game was invented in 1857 by William Rowan Hamilton. Hamilton sold it to a London game dealer in 1859 for 25 pounds, and the game was subsequently marketed in Europe in a number of forms (Gardner 1957). El juego fue inventado Icosian en 1857 por William Rowan Hamilton. Hamilton se lo vendió a un distribuidor de juegos de Londres en 1859 por 25 libras, y el juego fue comercializado posteriormente en Europa en una serie de formas (Gardner 1957).
Ejemplos
Autoevaluación
Yo me siento que si aprendi muchas cosas en este curso que me ayudaron mucho, aunque si me faltaron algunas ya que no las entendi muy bien, como el pseudocodigo entre otras, en general del tema que me toco del proyecto 5 pues a mi si me gusto mucho y si entendi lo que el algoritmo tiene que realizar, y otra cosa que necesito cambiar es no dejar todo para ultima hora si no hacerlo con tiempo y no estar a la carrera el ultimo dia todo estresado y preocupado, también me sirvio mucho este curso para aprender cosas nuevas y aunque varias no las entendi muy bien me sirve mucho para mas adelante en mi carrera, y esto que aprendi pues me ayudara mucho.
Bueno compañeros y maestra este fue mi proyecto 5 si tienen alguna duda o pregunta solo dejen su comentario y yo se las hare saber con mucho gusto.
Bibliografía
Pues esto del ciclo hamiltoniano, creo que ya lo habia usado en otro lado cuando estaba en la secu o en las asesorias para entrar a la prepa, me ponian ejercicios con numeros para seguir un ciclo y no lo tenia que romper algo asi, y tambien hay un juegito de esto que te ponen a hacer una figura con un lapiz sin despegar al punta y completar la figura. (y) voy a investigar mas de esto. Muy buena publicacion, nos vemos bye
ResponderEliminarEsta relacionado con mi proyecto que fue el angente viajero.
ResponderEliminarcon el Ciclo Hamilton es aplicable para el problema del viajero.
Tambien lo que comento mi copmpañero , sobre el juegito del lapiz que no podias despegar la punta.
Mucha veses no nos damos cuenta de cosas que hacemos a diario y son aplicaciones como este tipo de proyecto.
Muy buena observacion
Y esta padre tu proyecto .
Tu tambien cometiste el error en analisi asintotico , la unoca difernecia que tu no lo mencionaste en la clase .
ResponderEliminarle pusiste O(n2)
pero pues ya sabes que esta mal ,la profe nos explico que noe s asi porque no es polinomico si no exponencial , bueno lo deje mas breve porque tu si estabans en la clase y viste cuendo la maestra lo explico en mi presnetacion
para que corijas ese error
quedaria n!
si tines dudas me dices , la profe me explico con un ejemplo de que si n=4 al hacer tu formula que es O(n2) quedaria 16 sin embargo si utilizas n! se hace como factorial , bueno espero que me haigas entendido .
se me olvida poner mi blog para que la profe nos pueda identificar
ResponderEliminarhttp://doranellygonzalez.blogspot.com/
si ya lo entendi y lo corregi muchas gracias
ResponderEliminarholaaa si tu clase tambien me parecio muy buena :D entendi lo de como recorrer cada vertice
ResponderEliminarbueno respondiendo a tu pregunta la misma que me hizo dora y a la cual yo conteste que yo pienso o bueno a mi me quedo como enseñanza que cada ves que se nos presente un problema como por ejemplo el proyecto de tarea a exponer que tuvimos que constaba de varios puntos podemos separarlo en partes y asi ponerle mas atencion a cada punto asta que realizemos todo el proyecto en si :D es lo que yo creo
http://klaudialozanoo.blogspot.com/
Hola!
ResponderEliminarexactamente, el algoritmo de kruskal hace exactamente lo que publicaste en tu comentario.
Me alegra que se halla entendido el concepto.
Tu tema tambien es interesante. Empezare a buscar lo del juego de hamilton, creo que sera divertido :D
ahorita no tengo preguntas, pero empezare a checar la entrada en tu blog haber si no tengo alguna jeje
Muy buena clase
Saludos!
Gracias, Dora Nelly, por la corrección importante.
ResponderEliminar