El reto matemático de esta semana de El País (vídeo en español) vuelve a tratar sobre un grafo. En este caso, el grafo es un cubo (8 vértices, 12 aristas), con los vértices numerados como se muestra en el vídeo.
Una hormiga comienza a caminar desde el vértice #1 y, en cada vértice, cambia de dirección aleatoriamente, pudiendo incluso retroceder por la misma arista por la que llegó. Los vértices #7 y #8 están envenenados: si la hormiga entra en alguno de ellos, muere.
El reto consiste en determinar las probabilidades de que la hormiga:
- Muera o sobreviva.
- Si muere, en qué vértice envenenado (#7 u #8) termina.
Este programa utiliza la clase Graph definida anteriormente en el reto del camino hamiltoniano para realizar una simulación de Monte Carlo del problema y proporcionar una respuesta empírica. Sin embargo, el resultado por sí solo no es una solución completa: también debes aportar una demostración teórica que lo justifique. ;-)
#!/usr/bin/env python
# -*- coding: utf-8 -*-
# vim:ts=4:et:sw=4
from random import choice
from grafo import Graph, Vertex
class Point(Vertex):
"""Un vértice que puede contener una trampa de veneno."""
def __init__(self, *args):
Vertex.__init__(self, *args)
self.poisoned = False
def __str__(self):
tmp = '*' if self.poisoned else ''
return f'<{tmp}{self.i}>'
class Cube(Graph):
"""Subclase de Graph donde cada vértice (Point) puede estar envenenado o no."""
def add(self, node, *node_list):
vertex = Point(node, *node_list)
self.vList[node] = vertex
def run(self, N):
"""Simula una hormiga que comienza en el vértice #1 y camina N pasos aleatorios.
Se detiene si la hormiga entra en un vértice envenenado o completa N pasos.
Devuelve la posición final de la hormiga.
"""
i = 0
pos = 1 # Posición inicial de la hormiga
while i < N:
i += 1
pos = choice(self.vList[pos].nodeList)
if self.vList[pos].poisoned:
break
return pos
if __name__ == '__main__':
G = Cube()
G.add(1, 2, 4, 5)
G.add(2, 1, 3, 6)
G.add(3, 2, 4, 7)
G.add(4, 1, 3, 8)
G.add(5, 1, 6, 8)
G.add(6, 2, 5, 7)
G.add(7, 3, 6, 8)
G.add(8, 4, 5, 7)
# Marcar los vértices 7 y 8 como envenenados
G.vList[7].poisoned = True
G.vList[8].poisoned = True
# Ejecutar la simulación estadística
stats = [0, 0, 0] # Contadores: [sobrevivió, murió en #7, murió en #8]
for _ in range(1000000): # Número total de experimentos
pos = G.run(100) # Simular 100 pasos
if pos > 6: # Mapeo: 0-6 => 0, 7 => 1, 8 => 2
pos -= 6 # 7 = 1, 8 = 2
else:
pos = 0
stats[pos] += 1 # Incrementar el contador correspondiente
total = sum(stats) # Total de experimentos (debe coincidir con el bucle)
print(stats) # Frecuencias absolutas
print([100 * float(x) / total for x in stats]) # Frecuencias relativas (%)