miércoles, 19 de mayo de 2010

Proyecto #5

CICLO DE HAMILTON
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 1, 2, 3 1, 2, 3 se considera distinta de la 3, 2, 1 3, 2, 1 ). Un conteo precalculadas del correspondiente número de ciclos de Hamilton viene dada por GraphData gráfico ["HamiltonianCycleCount"].

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.
Complejidad Computacional

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.

Análisis Asintótico

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

http://translate.google.com.mx/translate?hl=es&langpair=en|es&u=http://mathworld.wolfram.com/HamiltonianCycle.html

http://148.202.148.5/cursos/mt260/matedisc/unidad4/tem4.5.htm


8 comentarios:

  1. 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

    ResponderEliminar
  2. Esta relacionado con mi proyecto que fue el angente viajero.

    con 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 .

    ResponderEliminar
  3. Tu tambien cometiste el error en analisi asintotico , la unoca difernecia que tu no lo mencionaste en la clase .

    le 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 .

    ResponderEliminar
  4. se me olvida poner mi blog para que la profe nos pueda identificar

    http://doranellygonzalez.blogspot.com/

    ResponderEliminar
  5. si ya lo entendi y lo corregi muchas gracias

    ResponderEliminar
  6. holaaa si tu clase tambien me parecio muy buena :D entendi lo de como recorrer cada vertice
    bueno 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/

    ResponderEliminar
  7. Hola!
    exactamente, 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!

    ResponderEliminar
  8. Gracias, Dora Nelly, por la corrección importante.

    ResponderEliminar


Ejemplo de una maquina turing

Diagrama de flujo

Diagrama de flujo
representacion grafica de un algoritmo

Numeros Binarios

* Cada entero positivo se puede expresar como la

suma de selectas potencias de dos



*Cada potencia aparece por máximo una vez



* La presencia de una potencia se indica con el

dígito uno, su ausencia con el dígito cero



* La potencia cero se ubica en el extremo derecho

de la cadena binaria



EJEMPLO:

5612 convertido a numero binario

quedaria asi:

1010111101100



13503 convertido a numero binario

quedaria asi:

11010010111111

Se preguntaran que es lo que hice bueno hay les van los pasos para realizar este cambio:
1. Buscamos el multiplo de 2 que este mas cerca de nuestro numero, pero sin pasarse por ejemplo en el 5612 el multiplo mayor que utilizamos fue el 12 que seria 4096.
2. Despues restamos primero el multiplo de dos que tengamos mayor y asi susecivamente vamos restando de lo que nos queda el sig. multiplo y cada que restemos ponemos un "1" y en caso de que un numero no lo podamos restar porque es menor lo brincamos pero en nuestro numero binario pondriamos un "0" y asi hasta llegar a cero.
3. Luego comprobamos sumando todos los multiplos de 2 que restamos y nos debe de dar el mismo resultado.

Ejemplo: 5612
el multiplo con el que empezariamos seria el de 12- 4096 se lo restamos al 5612 y en este caso pondriamos en nuestro numero binario un "1" lo que nos de lo restamos al siguiente y asi sucesivamente.