miércoles, 19 de mayo de 2010

Proyecto # 5

Algoritmo Detección de Ciclos (Cycle Detection Algorithm)

Liebre y Tortuga (Tortoise & Hare)

Bueno compañeros hoy me toca hablar acerca de la detección de ciclos y más detalladamente acerca del algoritmo liebre tortuga Creado por Robert W. Floyd antes de entrar a este algoritmo y su explicación primero debemos saber que es la detección de ciclos.

Concepto: la detección de ciclos sirve para identificar si estos existen dentro de un grafo.

Teniendo en cuenta esto se podría deducir que nuestro algoritmo nos ayudara de alguna manera a saber si existe o no, pero ese no es lo
único que nuestro algoritmo ara y es lo que veremos a continuación.

Nuestro algoritmo toma base de una fabula en la cual una liebre y una tortuga tiene una carrera en la cual la liebre evidentemente es mas rápida que la tortuga y esta avanza primero y regresa después para burlarse de esta por su lentitud; tomando en base a esto nuestro algoritmo cambia un poco la idea y decide que la liebre regrese pero para advertir de posibles ciclos a la tortuga.

esto quiere decir que en nuestro algoritmo el papel de la liebre será la que pruebe los distintos tipos de caminos entre las opciones de una arista de manera de conseguir siempre el camino más corto esto se logra haciendo que la liebre este adelante de la tortuga.


Tal como
podemos ver en esta imagen la tortuga esta en un punto x1= 0 mientras la liebre lee el
paso siguiente e
n un punto x2 = 6 cada uno con
su respectivo valor.

Al no tener el mismo la tortuga avanza una posición y la liebre avanza dos

Podemos ver entonces que ahora la tortuga se encuentra en un estado ((x1+1) = x2) = 6 y la liebre en un estado
((x2+2)=x4) = 1 al no ser iguales los valores avanzan y repetimos la instrucción

En esta parte la tortuga se encuentra ahora en la posición((x2+1)=x3)=3 y la liebre en una posición
((x4+2)=x6)=3 al encontrarse con un mismo valor en diferentes posiciones se llega a un ciclo y es aquí donde la tortuga toma una ruta distinta en su siguiente paso no se llegase a tener












Esta sería la representación en un grafo claro este solo sería el ejemplo de que pasaría si encuentra un ciclo.















Aquí prácticamente seria repetir exactamente lo escrito arriba así que solo me limitare a decir que esto equivale al paso uno en donde se evalúa cada valor en el grafo.













En esta parte ya la tortuga ah avanzado una posición y se encuentra en 6 mientras la liebre esta en 1.



















Aquí por ultimo vemos que ambos quedaron en la misma posición en este momento el algoritmo reconoce que es un ciclo al tener la liebre y la tortuga el mismo valor por lo cual el camino resulta ineficiente para llegar a la meta indicada.

Con respecto al análisis asintótico de este algoritmo me tope con ciertas dudas dado que su complejidad en O (λ+μ) donde
λ: representa una parte de otra función ya sea f(n).
μ: está definida para todos los números naturales n y tiene valores en {-1, 0, 1} dependiendo en la factorización de n en sus factores primos. (véase este enlace para aclarar dudas)

y tomando en cuenta eso (y suponiendo que los términos estén correctos) se puede decir que la complejidad asintótica del algoritmo depende en cierta forma de la función f(n) del programa y esta a su vez seria la cual afecte a μ ya que dependerá de si f(n) es Ωf(n) pues en base a ello tomara un valor si Ωf(n) = ω(n) ó Ωf(n)>ω(n).

la complejidad computacional debería ser polinomial pues es precisamente lo que hace el algoritmo al tener dos punteros uno con el doble de velocidad que el segundo llámense "a" y "b"
"b" como primera opción siempre intentara buscar el camino más corto al punto deseado pero a su vez topara con ciclos si estos existen mientras "a" ira más lento pero llegara por la ruta más corta al evitar los caminos que se repitan recorridos por "b", y si estos no llegaran a llevar a la meta y solo se produjera un ciclo del cual no se puede salir pues el algoritmo llegaría a su fin al no llegar al punto establecido.

pseudocódigo del algoritmo
este es un pequeño pseudocódigo que encontré que muestra prácticamente lo que se dice arriba

def floyd(f, x0):
---------------------------------------------------------------------------------

# La fase principal del algoritmo,buscara una repeticion x_mu = x_2mu
# La Liebre se Mueve dos veces mas rapido que la tortuga
tortuga, liebre = f(x0), f(f(x0)) # f(x0) es el elemento ó nodo siguiente de x0.
while tortuga != liebre:
tortuga = f(tortuga)
liebre = f(f(liebre))

# encontrar la posicion de la primera repeticion de la longitud "mu"
# La tortuga y la liebre se mueven ala misma velocidad
mu = 0
tortuga, liebre = x0, tortuga
while tortuga != liebre:
tortuga = f(tortuga)
liebre = f(liebre)
mu += 1

# encontrar la longitud del cyclo mas corto empezando de x_mu
# la liebre se mueve mientras la tortuga se queda sin moverse
lam = 1
liebre = f(tortuga)
while tortuga != liebre:
tortuga = f(liebre)
lam += 1

return lam, mu

------------------------------------------------------------------------

nota: cabe recordar que los dialogos despues del simbolo "#" representan un comentario en el pseudocodigo.

hay que tener en cuenta que este código solo tiene acceso a la secuencia mediante el almacenamiento y la copia de punteros, evaluaciones de la función, y las pruebas de la igualdad, por lo que califica como un algoritmo de puntero.

Las estructuras de datos utilizadas en este algoritmo son:
listas, arreglos, punteros, funciones.

aquí incluyo un ejemplo de dicho algoritmo en un programa si desean pueden copiar el código o descargarlo directamente desde la pagina del creador en los links de la parte de abajo.
-------------------------------------------------------------------------
#include


typedef struct node_s {
void *data;
struct node_s *next;
} NODE;


int list_has_cycle(NODE *list)
{
NODE *fast=list;
while(1) {
if(!(fast=fast->next)) return 0;
if(fast==list) return 1;
if(!(fast=fast->next)) return 0;
if(fast==list) return 1;
list=list->next;
}
return 0;
}


int main()
{
NODE n1, n2, n3, n4, n5;

n1.next=&n2;
n2.next=&n3;
n3.next=&n4;
n4.next=&n5;
n5.next=NULL;

printf("Test without cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");


n5.next=&n3;

printf("Test with cycle: ");
if(list_has_cycle(&n1)) printf("cycle\n");
else printf("no cycle\n");

return 0;
-------------------------------------------------------------------
dentro del código podemos ver que si los nodos n siguen su paso hasta un estado n5 = NULL se logra llegar al estado deseado por lo tanto no hay un ciclo en el transcurso pero si cambiásemos dicha ruta por una ya escrita tal como se ve en la línea donde n5=&n3 regresamos de nueva cuenta hacia n3 donde este toma el valor de n4 y así sucesivamente es por eso que utilizamos nuestra función list_has_cycle para que en la decisión imprima si existe o no un ciclo.


Detección de ciclos (explicación en ingles)

Biografía del Autor de Dicho algoritmo
Pagina web de apoyo para mi reporte
Otra web de apoyo.
*me falto anexar algunos archivos pdf de los cuales base la investigacion que subire en estos dias para que tmb pase a revisarlos.


4 comentarios:

  1. no entendi muy bien le pseudocogigo , tal vez porque aun no domino tanto el inlges.

    ResponderEliminar
  2. listo editado y trasladado el codigo lo mantuve en ingles debido a que cuenta cuenta con un error dentro de la funcion list_has_Cycle por lo cual lo editare tan pronto como identifique como cambiarlo

    ResponderEliminar
  3. OK. A mi se me hace que en esa función hay algún problema con el segundo if - no llego a ver qué quería con eso el programador.

    ResponderEliminar

Seguidores