ALGORITMOS COMPUTACIONALES."KARLA": mayo 2010

Tema: Ciclo de HamiltonProblema que este Algoritmo Resuelve:

Un ciclo hamiltoniano (o circuito hamiltoniano) es un camino cerrado en un que utiliza cada vertice del grafo exactamente una vez, exceptuando el ultimo que es igual a l primero, osea vertice inicial = vertice terminal.

En el cual:
Teorema (condición suficiente)
Sea G un grafo simple de n vértices. Si para todo par de vértices x e y
no adyacentes se cumple que d(x)+d(y) ≥ n , entonces G es hamiltoniano.

Teorema (condición necesaria)
Si G es un grafo hamiltoniano entonces,
∀ S ⊂ V se cumple que comp. conexas de (G − S) ≤ S

Hay propiedades para demostrar que un grafo no contiene un circuito hamiltoniano
(ej: grafo con vertice de grado 1).
Un circuito hamiltoniano no puede contener un circuito mas pequeño dentro de el.
Ideas:
*Ambas aristas de un vertice de grado 2 tienen que formar parte del circuito hamiltoniano .
*No hay caracterización para los grafos hamiltonianos.
*Un grafo bipartito no es hamiltoniano .

De Desición:
Encontrar un circuito hamiltoniano en un grafo completo, de mínimo coste
Una instancia del problema: encontrar un circuito hamiltoniano de mínimo coste. Este problema de desición es de tiempo exponencial. Ya que el Algoritmos al crecer el tamaño del problema, el tiempo de resolución crece muy rápidamente (exponencialmente).

De Optimización:

Se dice quees un ciclo Hamiltoniano cuando se recorre cada uno de sus vértices sin repetirlos.

En donde el inicio y el final son los unicos que se repetiran.

Debido a que el problema de decisión es NP-completo el problema de optimizacion es NP-duro.
Ejemplo:

Dado: Ciclo Hamiltoniano

Restricción: Pasar por sus vértices solo una vez y regresar al inicio.

Objetivo:Hacer el ciclo HAmiltoniano con mayor eficacia en un menor tiempo.

Complejidad Computacional:
La clase de complejidad es NP-completo, es el conjunto de los problemas de decisión que pueden ser resueltos por una máquina no determinista en tiempo polinómico. Esta clase contiene muchos problemas que se desean resolver en la práctica, como lo es un ciclo Hamiltoniano para recorrer todos los vértices una sola vez. Todos los problemas de esta clase tienen la propiedad de que su solución puede ser verificada efectivamente.

Análisis Asintótico del Algoritmo:

El análisis asintótico es de clase factorial por lo tanto es: (n!)
Ya que recorremos cada vertice y analisamos si este ya fue visitado anteriormente.

Estructuras de Datos utilizadas:

Utilizamos listas ya que
A base de punteros hay que mantener un puntero al primer elemento.
Cada elemento contiene, en adición a su dato, un puntero a
su seguidor. Al añadir un elemento, se modifica el puntero del elemento
después del cual se está insertando para que apunte al elemento nuevo.

Ejemplo paso a paso:

El Ciclo de Hamilton es un ciclo cerrado, el cual pasa por un respectivo vertice solo una vez, y regresa al vertice de donde partio, es decir se uniran el inicio con el final.

Tomemos en cuenta que no se conoce ningún criterio que permita distinguir los grafos hamiltonianos de los que no lo son.

Podemos tomar cualquier nodo al azar, en este caso se tomo un vertice del centro de la figura de la cual partiremos para poder hacer el ciclo hamiltoniano. En este caso comenzamos llamando los vertices con números ordenados, el primero es el número 1, despues pasamos al siguiente vertice número 2, despues al 3 y asi asta llegar al último vertice de esa figura que es la mas pequeña, el cúal seria el vertice número 5, la cúal no cierra la figura sino que abre el ciclo a la figura mas grande, donde recorrera los vertices de la orilla de la figura sin repetirlos. Despues al llegar al último vertice de la figura repetira el mismo mecanismo de no cerrar sino que ahora pasara a la figura siguiente que veiene siendo la mediana en la cual se repetiran los pasos de recorrer las orillas de la figura i cuando llege a su ultimo vertice tomara posicion en el vertice en el cual comenzamos el recorrido.

En este caso se siguio la siguiente serie (1,2,3,4,5,6,7,8,9,10................20)

Aplicaciones:

El problema del agente viajero (TSP).

Es un problema de optimización combinatoria estudiado en la investigación de operaciones y la informatica teorica . Dada una lista de las ciudades y sus distancias dos a dos, la tarea es encontrar un recorrido más corto posible que visita cada ciudad exactamente una vez.

Un viajante desea salir de Alboraya, y recorrer las 50 ciudades más importantes de España, para finalmente volver a Alboraya, con la intención de convencer a algunos comerciantes de que comercialicen su horchata. El problema que se le plantea al viajante es encontrar el itinerario que le suponga recorrer la mínima distancia. ¿Cómo se podría resolver la cuestión planteada?

Se obtienen todos los itinerarios posibles que partiendo de Alboraya llegan a Aboraya, recorriendo las 50 ciudades.
Veamos un ejemplo para 3 ciudades. Construimos el grafo del problema, tal y como se observa en la siguiente figura: cada par de ciudades quedan unidas por una arista, y el número sobre cada una, refleja el coste en km. que implica recorrerla, en un sentido o en otro (es un grafo no dirigido).

Una posible solución al problema sería A-C1-C3-C2-A. Es decir, salir de Alboraya, ir a C1, luego a C3, luego a C2, y finalmente volver a Alboraya. En este caso, el coste en kilómetros, sería: 7 + 10 + 2 + 3 = 22 km. ¿Cuantos posibles caminos de estas características hay?. Pues 3! = 6. Algunos ejemplos y el coste correspondiente: