seegongsik
Mis palabras
Algoritmos

Resolver tirando dados

Con lo voraz elegiste lo mejor que tenías delante. Pero algunas soluciones simplemente tiran dados. Deciden qué elegir al azar. Suena raro, pero a veces es más rápido y simple. ¿Cómo puede ayudar dejarlo a la suerte?

01

Elegir con dados

Algunas soluciones
deciden qué hacer luego
tirando dados.
No pensándolo bien,
sino dejándolo a la suerte.
Cada vez que pulsas,
los dados ruedan una vez.
No puedes saber de antemano
qué cara saldrá.

Pulsa para tirar
tiradas previas

Pulsa y los dados ruedan. (No sabes la próxima cara)

¿Por qué dejarlo a la suerte adrede?
Si siempre eliges igual,
alguien puede apuntar a esa costumbre
y complicarlo a propósito.
Elegir al azar
esquiva esos trucos.
En el siguiente paso
verás la utilidad real.

02

Usar una referencia al azar

Entre los ordenamientos rápidos
hay uno que elige una referencia,
pone lo menor a la izquierda,
lo mayor a la derecha,
y divide.
Pero si siempre tomas
el último valor como referencia,
con una entrada ya ordenada
la división se inclina toda a un lado
y se vuelve muy lento.

Referencia siempre-final
Referencia al azar

Referencia siempre-final vs al azar, compara las divisiones. (Inclinarse a un lado = lento)

Elige la referencia al azar
y para cualquier entrada que llegue,
inclinarse todo a un lado
casi nunca pasa.
Una trampa contra entradas malas
tampoco funciona.
Así que en promedio
las divisiones salen parejas
y el ordenamiento se acelera.

03

Lanzar mucho para estimar

El azar sirve para estimar también.
Dibuja un círculo
dentro de un cuadrado.
Esparce puntos por todos lados.
Mira la proporción de puntos
dentro del círculo frente al total,
y puedes estimar
el área que ocupa el círculo.
Suelta los puntos uno a uno.

en círculo: 0total: 0proporción: -valor real: 0.785
Suelta puntos y mira la proporción

Más puntos, la proporción se acerca al valor real. (puntos en el círculo / total)

Cuando hay pocos puntos
la estimación salta.
Pero cuantos más puntos sueltas,
la proporción se pega al valor real.
No puedes fiarte de uno o dos golpes de suerte,
pero el promedio de incontables lanzamientos
es fiable.
Esta es la forma de lanzar mucho
para estimar una respuesta.

04

Cambiar certeza por velocidad

Una solución aleatoria no es gratis.
Rápida y simple, sí,
pero no puede prometer
la misma respuesta cada vez.
Con mala suerte
puede ser lenta de vez en cuando.
Qué ganas
y qué cedes,
pulsa ambos lados y compara.

Pulsa ambos lados para comparar

Pulsa para comparar ganancia y costo. (rápido y simple vs sin la misma respuesta garantizada)

Así que el azar no es
siempre bueno
sino que tiene su lugar.
Usalo cuando lo rápido y simple
vale más
que un poco de incertidumbre.
Cedes un poco de certeza
y compras a cambio
velocidad y simplicidad.

05

Cerrar la idea

Reunamos
la solución aleatoria de un vistazo.
Elige con dados,
esquiva trampas con una referencia al azar,
lanza mucho para estimar una respuesta,
cambia certeza por velocidad.
Haz clic en los puntos clave en orden
y ciérralo tú mismo.

Haz clic en los puntos clave en orden para cerrar

Haz clic en los cuatro puntos en orden. (dados · referencia al azar · estimar con muchos lanzamientos · intercambio)

Dejarlo a la suerte
parece endeble,
pero bien usado, el azar
es una herramienta rápida y fiable.
Donde los datos crecen
enormes más adelante,
esta idea de estimar con muchos lanzamientos
se usa a mayor escala.
Esa historia queda para después.

En una líneaAlgunas soluciones tiran dados y eligen qué hacer al azar. En quicksort, usar siempre el último valor como referencia se vuelve lento con entradas malas, pero elegir la referencia al azar esquiva esa trampa y es más rápido en promedio. También puedes esparcir puntos dentro de un cuadrado y mirar la fracción que cae en un círculo para estimar un área. Cuantos más lances, más afinada la estimación. Una solución aleatoria no puede prometer la misma respuesta cada vez, pero a cambio es rápida y simple. Cedes un poco de certeza y ganas velocidad.
Algoritmos
¿Te fue útil? Apoyar seegongsik