Algoritmo de Caminata Aleatoria en Python: Clase Borracho

Clase 6 de 24 • Curso de Estadística Computacional con Python

Contenido del curso

Introducción

1
Programación Dinámica y Estocástica: Optimización y Modelado de Datos
01:56 min

Programación Dinámica

Caminos Aleatorios

Programas Estocásticos

Simulaciones de Montecarlo

Muestreo e Intervalos de Confianza

Datos Experimentales

Conclusiones

24
Optimización de Programas con Programación Dinámica y Simulaciones
02:54 min

Tomar examen

Resumen

¿Cómo funciona la caminata aleatoria y cómo se implementa su algoritmo?

¡Bienvenidos a un fascinante viaje al mundo de los caminos aleatorios! Este concepto, conocido también como la "caminata del borracho", es un problema sencillo pero intrigante en el cual un objeto puede desplazarse en múltiples direcciones con igual probabilidad. Vamos a repasar cómo nosotros podemos implementar este modelo con clases en Python para simular estos movimientos aleatorios y representar el comportamiento en un plano cartesiano.

¿Qué es un camino aleatorio?

Un camino aleatorio comienza en un punto de origen y puede moverse en varias direcciones: arriba, abajo, izquierda, o derecha, con una probabilidad igual del 25% para cada dirección. Este proceso se repite en cada paso, llevando a infinitas posibilidades de recorrer diferentes trayectorias. Algunos aspectos interesantes de un camino aleatorio incluyen:

Puede ser extendido a múltiples dimensiones, no solo en 2D, sino también en 3D, 5D, etc.
Se pueden asignar probabilidades diferentes para cada movimiento.
La distancia recorrida se calcula fácilmente mediante el teorema de Pitágoras.

¿Cómo podemos representar un borracho?

En el contexto del camino de borrachos, un borracho es una entidad que se mueve al azar en un plano. Implementamos la clase Borracho para abstraer el comportamiento de esta entidad.

class Borracho:
    def __init__(self, nombre):
        self.nombre = nombre

De esta manera, al extender Borracho, podemos crear subclases que modelen diferentes tipos de trayectorias y comportamientos. Un ejemplo de subclase es el BorrachoTradicional, quien se mueve aleatoriamente entre cuatro opciones: arriba, abajo, izquierda y derecha.

¿Cómo defino los movimientos del borracho?

Usamos la clase BorrachoTradicional para implementar esta lógica con la ayuda de la librería random de Python.

import random

class BorrachoTradicional(Borracho):
    def __init__(self, nombre):
        super().__init__(nombre)

    def camina(self):
        return random.choice([(0, 1), (0, -1), (1, 0), (-1, 0)])

Aquí random.choice se utiliza para seleccionar aleatoriamente una de las direcciones posibles, reflejando nuestro modelo de movimientos equiprobables.

¿Cómo manejamos las coordenadas y calculamos distancias?

Para gestionar la posición en el plano, creamos la clase Coordenada. Esta clase se encarga de las posiciones y desplazamientos del borracho.

import math

class Coordenada:
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def mover(self, delta_x, delta_y):
        return Coordenada(self.x + delta_x, self.y + delta_y)

    def distancia(self, otra_coordenada):
        delta_x = self.x - otra_coordenada.x
        delta_y = self.y - otra_coordenada.y
        return math.sqrt(delta_x**2 + delta_y**2)

Aquí, utilizamos el teorema de Pitágoras para calcular la distancia entre dos puntos.

¿Cómo se representa el campo?

El campo es el espacio que contiene a los borrachos. Implementamos esto a través de la clase Campo, la cual permitirá añadir, mover, y consultar las coordenadas de nuestros "borrachos".

class Campo:
    def __init__(self):
        self.coordenadas_de_borrachos = {}

    def añadir_borracho(self, borracho, coordenada):
        self.coordenadas_de_borrachos[borracho] = coordenada

    def mover_borracho(self, borracho):
        delta_x, delta_y = borracho.camina()
        coordenada_actual = self.coordenadas_de_borrachos[borracho]
        nueva_coordenada = coordenada_actual.mover(delta_x, delta_y)
        self.coordenadas_de_borrachos[borracho] = nueva_coordenada

    def obtener_coordenada(self, borracho):
        return self.coordenadas_de_borrachos[borracho]

Con esto, ahora tenemos el framework necesario para implementar simulaciones complejas de caminos aleatorios. Estas clases nos ofrecen la flexibilidad para modelar diferentes escenarios de simulación.

¡Construye y observa tu simulación!

Con las bases listas, podemos avanzar hacia integrar todo en un solo programa. Esto te permitirá realizar experimentos con diferentes escenarios y parámetros, y observar cómo varía la distancia al origen a medida que aumenta el número de pasos. Este ejercicio no solo es útil para aprender sobre programación orientada a objetos, sino también sobre probabilidad y estadísticas. ¡Sigue experimentando y expandiendo tus conocimientos!

Karl Behrens Gil

student•

https://github.com/karlbehrensg/programacion-dinamica-y-estocastica Camino de Borrachos

Este es un ejercicio donde empezando desde un punto 0 aleatoriamente podemos decidir que dirección tomar, dependiendo de las opciones establecidas.

Para realizar un ejemplo de aleatoriedad vamos a crear un programa que representara el problema del "Camino de Borrachos". Para esto crearemos 3 clases: uno que represente al agente que camina, una que genere una abstracción de las coordenadas y una que represente el plano en el cual nos estamos moviendo, y vamos a graficar la distancia en la que termina nuestro agente a medida que definimos una mayor cantidad de pasos que puede dar.

Primero crearemos un ambiente virtual, para ello vamos a la terminar.

mkdir camino_de_borramos    # Creamos una carpeta para nuestro proyecto.
cd camino_de_borrachos      # Ingresamos a la carpeta.
python3 -m venv env         # Creamos nuestro ambiente virtual.
source env/bin/activate     # Activamos nuestro ambiente.
pip install bokeh           # Instalamos el paquete de bokeh para generar nuestra gráfica.

Luego de haber creado nuestro entorno de trabajo creamos los siguientes archivos en nuestra carpeta.

# Creamos un archivo borracho.py
import random

# Creamos nuestra Clase borracho.
class Borracho:

    def __init__(self, nombre):
        self.nombre = nombre


# Creamos la clase BorrachoTradicional que extiende de Borracho.
class BorrachoTradicional(Borracho):

    def __init__(self, nombre):
        super().__init__(nombre)

    # Y tendrá un método caminar que devolverá la dirección a la que ira.
    def camina(self):
        # Con random.choice elegimos un elemento aleatoriamente de la lista.
        return random.choice([(0, 1), (0, -1), (1, 0), (-1, 0)])

# Creamos un archivo coordenada.py

# La clase Coordenada guardara las coordenadas de nuestro agente
class Coordenada:

    # Definimos unas posiciones iniciales.
    def __init__(self, x, y):
        self.x = x
        self.y = y

    # Y cuando se mueve simplemente a las coordenadas actuales se les
    # suma las coordenadas X e Y que ingresan como parámetros.
    def mover(self, delta_x, delta_y):
        return Coordenada(self.x + delta_x, self.y + delta_y)


    # Y si queremos saber la distancia del agente con respecto a
    # unas coordenadas, simplemente lo calculamos con el
    # teorema de Pitágoras.
    def distancia(self, otra_coordenada):
        delta_x = self.x - otra_coordenada.x 
        delta_y = self.y - otra_coordenada.y 

        return (delta_x**2 + delta_y**2)**0.5

# Creamos un archivo campo.py
class Campo:

    # Nuestra clase tendrá como atributo un diccionario.
    def __init__(self):
        self.coordenadas_de_borrachos = {}


    # Añadimos un agente a nuestro diccionario, nuestra llave sera
    # nuestro parámetro "borracho" y tendrá el valor asignado "coordenada"
    # que es una clase Coordenada creado en coordenada.py.
    def anadir_borracho(self, borracho, coordenada):
        self.coordenadas_de_borrachos[borracho] = coordenada


    def mover_borracho(self, borracho):
        # Al mover a nuestro agente ejecutamos el método camina de
        # nuestra clase BorrachoTradicional creado en el archivo borracho.py,
        # devolviendo la dirección hacia donde se movió.
        delta_x, delta_y = borracho.camina()

        # Obtenemos el objeto de Coordenada.
        coordenada_actual = self.coordenadas_de_borrachos[borracho]

        # Del objeto Coordenada ejecutamos el método mover con los parámetros
        # que el objeto borracho genero. El resultado lo guardamos en
        # nueva_coordenada.
        nueva_coordenada = coordenada_actual.mover(delta_x, delta_y)

        # El objeto guardado en nueva_coordenada ahora estará asociado
        # a la llave de borracho.
        self.coordenadas_de_borrachos[borracho] = nueva_coordenada


    def obtener_coordenada(self, borracho):
        return self.coordenadas_de_borrachos[borracho]

# Creamos el archivo camino_aleatorio.py

# Importamos las clases que creamos anteriormente.
from borracho import BorrachoTradicional
from campo import Campo
from coordenada import Coordenada

# Importamos bokeh para generar un gráfico con nuestros resultados.
from bokeh.plotting import figure, show


def caminata(campo, borracho, pasos):
    # De la instancia Campo obtenemos las coordenadas actuales de la llave "borracho".
    inicio = campo.obtener_coordenada(borracho)

    # Repetiremos la misma cantidad de pasos definidos.
    for _ in range(pasos):

        # De la instancia campo ejecutaremos mover_borracho.
        campo.mover_borracho(borracho)

    # Y devolveremos la distancia entre las coordenadas de la instancia
    # inicio y campo.
    return inicio.distancia(campo.obtener_coordenada(borracho))


def simular_caminata(pasos, numero_de_intentos, tipo_de_borracho):

    # Definimos los parámetros para crear una instancia de Campo.
    borracho = tipo_de_borracho(nombre='Karl')
    origen = Coordenada(0, 0)

    # Creamos una lista que guardara las distancias en cada simulación.
    distancias = []

    # Por cada numero de intento.
    for _ in range(numero_de_intentos):

        # Creamos una instancia de Campo.
        campo = Campo()

        # A nuestra instancia de Campo le damos la llave borracho y sus coordenadas de origen.
        campo.anadir_borracho(borracho, origen)

        # Obtenemos la distancia final de la simulación.
        simulacion_caminata = caminata(campo, borracho, pasos)

        # El resultado lo guardamos en la lista de distancias.
        distancias.append(round(simulacion_caminata, 1))
    
    # Retornamos la lista de distancias.
    return distancias


def graficar(x, y):
    # Creamos una instancia de figure, con su titulo y las etiquetas de los ejes.
    grafica = figure(title='Camino aleatorio', x_axis_label='pasos', y_axis_label='distancia')

    # Ingresamos los datos de X e Y.
    grafica.line(x, y, legend='distancia media')

    # Generamos una gráfica en HTML.
    show(grafica)


def main(distancias_de_caminata, numero_de_intentos, tipo_de_borracho):

    # Creamos una lista que guardara el promedio de cada caminata.
    distancias_media_por_caminata = []

    # Por cada ítem en nuestras series de caminata.
    for pasos in distancias_de_caminata:

        # Guardamos las distancias que generan todas las simulaciones definido en numero_de_intentos.
        distancias = simular_caminata(pasos, numero_de_intentos, tipo_de_borracho)

        # De la lista de distancias obtenemos la distancia promedio.
        distancia_media = round(sum(distancias) / len(distancias), 4)

        # De la lista de distancias obtenemos el máximo valor.
        distancia_maxima = max(distancias)

        # De la lista de distancias obtenemos el menor valor.
        distancia_minima = min(distancias)

        # Guardamos el promedio de la caminata en la lista distancias_media_por_caminata.
        distancias_media_por_caminata.append(distancia_media)

        # Imprimimos los datos de la caminata actual.
        print(f'{tipo_de_borracho.__name__} caminata aleatoria de {pasos} pasos')
        print(f'Media = {distancia_media}')
        print(f'Max = {distancia_maxima}')
        print(f'Min = {distancia_minima}')

    # Generamos un gráfico con la información de las distancias finales según la cantidad de pasos.
    graficar(distancias_de_caminata, distancias_media_por_caminata)

if __name__ == '__main__':
    # Definamos cuantos pasos queremos que camine en cada serie.
    distancias_de_caminata = [10, 100, 1000, 10000]
    
    # Determinamos la cantidad de simulaciones que generara en cada serie.
    numero_de_intentos = 100

    # Ejecutamos el método main con los parámetros definidos anteriormente
    # y además pasamos la clase BorrachoTradicional
    main(distancias_de_caminata, numero_de_intentos, BorrachoTradicional)

Dentro el pensamiento estocástico debemos realizar varias simulaciones, por ese motivo en el ejemplo anterior realizamos varios intentos. Lo importante de esta aleatoriedad es que podemos distribuirla a lo largo de varios intentos, con esto podemos obtener certeza de que el comportamiento de nuestro programa se comporte en que esperamos estadísticamente.

Para ejecutar nuestro programa iremos nuevamente a la consola.

python3 camino_aleatorio.py     # Ejecutamos nuestro programa

# Y veremos nuestros resultados:

BorrachoTradicional caminata aleatoria de 10 pasos
Media = 2.639
Max = 6.3
Min = 0.0
BorrachoTradicional caminata aleatoria de 100 pasos
Media = 8.914
Max = 23.5
Min = 1.4
BorrachoTradicional caminata aleatoria de 1000 pasos
Media = 28.58
Max = 73.8
Min = 2.0
BorrachoTradicional caminata aleatoria de 10000 pasos
Media = 86.012
Max = 241.3
Min = 22.4

Luis Fernando Pedroza Taborda

student•

Wow quedo muy bien explicado, gracias Karl.

Patricia Calisto Gutierrez

student•

Muchas gracias!!!!

David Martínez Jiménez

Demetrio Cumplido Narciso

Elisa Zamarron Muñoz

Bryan Duarte

Edward Toledo López

Daniel Andrés Giraldo Benites

Fernando Andres Muñoz Suazo

Neftali García González

Rafnix Gabriel Guzmán Garcia

Moises Diaz

William Leonardo Torres Toloza

María José Medina

Mauricio Cruz

Jordy Alexis Cadena Diaz

Royer Guerrero Pinilla

Gabriel Martins Santos

Iván Ricardo Bohórquez Basto

Oscar Hernan Pomi Piazza

Kevin Gabriel Salazar Selvas

José Manuel Piña Rodríguez

Fredy Alberto Orozco Loaiza

Enmanuel Castillo

Juan Mercado

Santiago Ahumada Lozano

Usuario anónimo

user•

Walter Alvarado

César Pizarro

Luis Fernando Cruz Carrillo

Josue Noha Valdivia

JULIO RAUL CARRANZA RUIZ

Alan Rafael Pereyra

Cristian Blandon

Sebastián Andrade

Nery Alberto Cano Ortigoza

Maximo Daniel Di napoli

Jesús Joel Sarabia Félix

Algoritmo de Caminata Aleatoria en Python: Clase Borracho

Introducción

Programación Dinámica y Estocástica: Optimización y Modelado de Datos

Programación Dinámica

Programación Dinámica: Optimización de Problemas con Memorización

Optimización de Algoritmos con Programación Dinámica en Python

Caminos Aleatorios

Simulaciones con Caminos Aleatorios en Programación

Camino Aleatorio en Programación Orientada a Objetos