Teorema de los monos infinitos.

El teorema de los monos infinitos dice:

    Un mono pulsando teclas al azar sobre un teclado durante un periodo de tiempo infinito casi seguramente podrá escribir finalmente cualquier libro que se halle en la Biblioteca Nacional Francesa.

Que básicamente dice que si intentas mucho algo que puede pasar (aunque sea muy difícil que pase) muy probable mente lograras tu cometido.



El otro día en la clase de diseño y análisis de algoritmos (impartida en linea gratis por la universidad de stanford Link al curso), el programa de tarea consistía en implementar el algoritmo de Karger, para el problema de corte mínimo.


En esencia para el problema de corte mínimo se tiene un grafo G = ( V, E ), en el cual se traza una linea que separe el grafo en 2 subconjuntos, cada subconjunto no debe ser vació. Y la solución a este problema es encontrar una linea que separe al grafo en 2 subconjuntos y exista el menor número de vértices que vallan de los nodos de un subconjunto a los nodos del otro.


En la imagen se muestra un grafo con nodos A, B, C y D, en la primera imagen se divide el grafo en en los 2 subconjuntos {B}  y {A, C, D}, a esto le llamamos un corte, y como existen 2 vértices que unen al subconjunto 1 con el subconjunto 2, decimos que es un corte de orden 2, los vértices en este caso serían los unen a A con B, y a  C con B.

La tercera imagen muestra otro corte para este mismo grafo. En este caso, los 2 subconjuntos generados son {D} y {A, B, C}, este corte es de orden 1, y debido a que es el menor número de cortes que se pueden realizar, se dice que es un corte mínimo.

Hay que notar que no se permite realizar cortes en que existan subconjuntos vacíos y que un grafo puede tener mas de un corte mínimo.

La cuestión con este algoritmo es que es un algoritmo probabilistico, esto es, no necesaria mente llega a la solución mínima, pero dado un número suficiente de corridas llega a la solución correcta.

Esto ya es una aplicación del teorema de los monos infinitos, hay que correr este algoritmo varias veces para poder (casi seguramente) llegar a una solución.

El problema con el que me encontré fue que tenía un bug muy escurridizo que ocasionaba que a veces el programa crasheara,
debido a que tenía poco tiempo para dedicarle al programa decidí aplicar nuevamente el teorema de los monos infinitos.

Como el programa no crasheaba siempre, y de las veces que no crasheaba a veces llegaba a una solución correcta (pues así funciona el algoritmo).
Solo puse un try catch, que en realidad solo evitaba que el programa crasheara.
Poner a correr esta programa un número de veces los suficiente mente grande me dio la solución correcta, y gracias a una buena implementación y que
el tamaño de la instancia era pequeño, en realidad no tardaba nada en terminar.

Anexo el código hecho en java, nunca tuve tiempo de corregir el bug, pero funciona casi perfectamente =p.
http://pastebin.com/FGh9H4LL
y la info del problema esta aquí:
http://pastebin.com/R1uJHHu3

---

Otra aplicación del teorema de los monos infinitos se da en las personas que hablan mucho, si dices un chingo de cosas, alguna de ellas tendrá sentido.
Claro eso no quiere decir que sea agradable escuchar todas la basura que sale por tu boca.

---

Karger's algorithm

El algoritmo de karger se basa en realizar contracciones de los nodos del grafo, cada paso del algoritmo se contraen 2 nodos reduciendo el número de nodos en 1. El algoritmo termina cuando el número de nodos es 2, y el valor del corte es el número de vértices que unen a los 2 nodos.

Se agregan dibujillos hechos por mi para mayor claridad. En este grafo, primero se contrajeron los nodos A y C, y posteriormente se contrajeron los nodos {A, C} y D, como el número de nodos en este punto es 2, el algoritmo termina, reportando un corte con valor de 2.

Contraer nodos A y C

Grafo resultante de la contracción de A y C

Contraer nodo {A, C} y D

Grafo final, con un corte de 2

Suponga que en la tercera imagen, en lugar de contraer los nodos {A, C} con el nodo D, se contrajeran los nodos {A, C} con el nodo B. En este caso también terminaria el algoritmo al tener solo 2 nodos, pero ahora tenemos un corte con valor de 1.

Lo único adicional que hay que mencionar es que el algoritmo de Karger realiza la elección de que nodos unir de forma aleatoria con base al número de vértices que tiene cada nodo. Entre mas vértices tenga un nodo, mas probable es que este sea elegido. Suponga que queremos encontrar un corte mínimo dado, donde sabemos que el nodo A se encuentra en un subconjunto que se crea por el corte, y el nodo B se encuentra en el otro subconjunto.
Si en algún momento el algoritmo de Karger realiza una contracción del nodo A y B, estos dos nodos terminaran en un mismo subconjunto al terminar el algoritmo. Esto quiere decir que al terminar, no encontramos el corte mínimo en el que A y B terminan en subconjuntos diferentes.

Una idea intuitiva del porque de este algoritmo es que, un corte mínimo es aquel que separa al grafo en 2 subconjuntos en los que el número de vértices que los unen es el menor posible. Este algoritmo elegirá contraer con mayor probabilidad aquellos nodos que tengan un alto número de vértices, esto lleva a que aquellos vértices que tengan un alto número de vértices acaben en el mismo subconjunto.
Lo que con suerte, quiere decir que tendremos un corte mínimo.