Proyecto Numero 5

Deteccion de Ciclos: Algoritmo de tortuga y liebre

El algoritmo de la tortuga y la liebre, sirve para la detección de datos, este fue inventado por Robert W. Floyd, quien lo invento a final de los 60’s.

Para conocer bien este método, primero necesitamos saber que es un grafo. Un grafo se determina conexo siempre y cuando estén conectado un nodo con otro nodo, ya sea por medio de aristas, flechas etc. En estos grafos siempre habrá un inicio y un final,pero se puede dar la ocasión que nos podemos encontrar con un ciclo, y este ciclo hace que el grafo se repita. Para eso estamos aquí.

Esto es un ejemplo de un grafo.

El algoritmo de detección de ciclos, que se implemente por medio de la historia clásica de “ La tortuga y la liebre”. Este algoritmo consiste en detectar en los grafos ciclos, estos ciclos ya sean del mismo tipo, una repetición de un dato, o de cualquier cosa, solo que se repita en el mismo grafo, o en la secuencia del mismo.

Aqui podemos apreciar que en el primer paso la liebre avanza 2 pasos, y luego la tortuga solo uno. En la segunda iteracion, la tortuga avanza al siguiente y la liebre otros 2 pasos. En el tercer paso se encuentre un dato igual, esto quiere decir que se encontro un ciclo. Cuando se encuentra el ciclo, este proceso termina.


La solucion mas facil, para buscar la ciclos, es aquella que vayas por toda la lista, anotando o memorizando que nodos has visitado. Es muy obvio que esto tiene un análisis asintótico de O(n^2) respecto a tiempo, esto significa que no es muy eficiente y a la ves aun mas complicado que nuestro algoritmo.

Problema de Decision

"En el grafo que se tiene, es posible encontrar un ciclo?"

Claro que es posible, ya que existen grafos con ciclos, o bien sin ciclos, aqui les demostrare 2 grafos de los 2 tipos.

El algoritmo de la tortuga y la liebre posiblemente es el mas famoso para detectar ciclos y a la ves muy eficiente. Tanto como la tortuga y la liebre son punteros, y ambos empiezan en el inicio del grafo. Para cada iteración o bien , para cada paso la tortuga avanzara un paso, y la liebre avanzara dos pasos. Si es que existe un ciclo, la liebre ira por ese ciclo y es posible que mas de una ves, y en algún tiempo la liebre se econtrara con nuestra tortuga. Si esto sucede, quiere decir que existe un ciclo. En caso de que no exista ningún ciclo, tanto como la tortuga y la liebre llegaran al final del grafo, sin tener que toparse.


A continuacion un ejemplo de un grafo con ciclo, aplicado con un pseudocodigo.

1 tortuga = inicio
2 hare = inicio
3
4 iteracion:
5 if liebre == final :
6 return 'No hay ciclo'
7 liebre = liebre.siguiente // Aqui se hace que la liebre avanze dos posiciones.
8
9
10 tortuga=tortuga.siguiente // La tortuga avanza una posicion
11
12 if tortuga == tortuga:

13 return 'Se encontró un ciclo!'.

Aqui podemos encontrar el inicio del algoritmo. Done usamos el

1 tortuga = inicio
2 hare = inicio

Aqui empezamos en el proceso.

En la iteracion numero dos, podemos ver que el humano(la tortuga) avanzo 1 numero de pasos, mientras que el caballo (liebre) avanzo 2 pasos. En este paso es donde se empieza la iteracion a partir del paso numero 4.

Sucede exactamente lo mismo, y como aun no se encuentra el uno con el otro, el programa aun no termina.

Lo mismo, seguimos en la iteracion repetitiva para encontrar el ciclo.

Aqui podemos ver que ya se estan acercando, sin embargo nada ha cambiado en este grafo, excepto por las posiciones de los datos.

Aqui es donde encontramos el ciclo, ya que tanto como la tortuga y la liebre se encontraron. Y es aqui donde nuestro pseudocodigo encuentra el ciclo, y vemos que si funciona el algoritmo de la tortuga y la liebre para encontrar ciclos.

Una persona se puede preguntar, por que no va la liebre sola?, pues esto no puede pasar, ya que si hay un ciclo la liebre avanzara para siempre, y no se detectarían ciclos, ademas la tortuga tiene que estar ahi, para asegurar que tengas un numero de "n" pasos, y facilita nuestro trabajo.

ANALISIS ASINTOTICO

Este problema tiene una complejidad O(n), ya que este problema se puede determinar en n pasos, sin tener que molestarte en procedimientos largos y complejos.

COMPLEJIDAD COMPUTACIONAL

Este problema tiene una complejidad de P, ya que se puede resolver por una maquina turing en un determinado tiempo, o bien en n tiempo. No es de complejidad alta, y solo toma un numero de n pasos.

ESTRUCTURA DE DATOS UTILIZADOS

En este algoritmo se usan arreglos e iteraciones, con el fin de poder ciclar las posiciones avanzadas hasta encontrar un ciclo. Se pueden emplear en listas hash, o tablas de datos, con el objetivo de encontrar un dato repetido.

APLICACIONES

Este algoritmo se puede usar en diferentes cosas como por ejemplo:

• Rutas de camiones, mientras se realiza un programa para determinar las rutas de los camiones, es importante saber por donde cruzan y hacia donde van, con el objetivo de optimizar las calles y sus rutas.
• Para determinar ciclos infinitos en programas de computadoras
• Para configuraciones en automatas celulares, mientras se simulan se aplican algoritmos de de deteccion de ciclos, cada estado del automata.
• Muchos algoritmos numerous-teoricos estan basados en deteccion de ciclos, incluyendo Pollard rho para la factorización de enteros, y el algoritmo del canguro con el problema logaritmo discreto

Conclusion Personal

En este proyecto siento que me ira muy bien, solo que me pudo haber ido mejor si no hubiera tenido unos problemas con el itnernet explroer, ya que al momento de subir mi trabajo tuve unas complicaciones te que mi internet no respondia, y no sabia por que, entonces cuando pasa eso el internet se cierra automaticamente y se reinicia asi que perdia toda mi informacion. Si lo pudiera haber hecho a la primera, me hubiera salido mucho mejor, ya que me estaba estresando cada ves mas. Fuera de eso siento que hice un buen trabajo, y con 3 ejemplos claros y simples. (2 en el blog y otro en la presentacion). Gracias espero que les haya gustado.