(A la parte 12)
Medición de la dificultad
Vamos a proponer (¡finalmente!) un método para calcular la dificultad de un laberinto. Cuando Teseo está recorriendo el grafo llega a veces a un nodo en el que tiene que hacer alguna elección al azar. Cada vez que esto sucede decimos que Teseo toma una decisión.
Cada recorrido completo (es decir, que un recorrido que conecte la entrada con la salida) contendrá cierta cantidad de decisiones, esta cantidad será un número entero mayor o igual que cero (cero, pues es posible que no haya habido decisión alguna). Cada recorrido completo tiene, a su vez, una cierta probabilidad de ocurrir (veíamos en la entrada anterior, apenas ayer, un recorrido de probabilidad 1/32 en un cierto laberinto).
Proponemos como medida de dificultad del laberinto el número esperado de decisiones. Esto es, para cada recorrido posible se calcula el producto de su probabilidad por la cantidad de decisiones que involucra y luego se suman todos los valores así obtenidos. Así por ejemplo, el laberinto trivial (que tiene un único eje que conecta la entrada con la salida) tiene dificultad cero, pues hay un único recorrido completo, con probabilidad 1 y cero decisiones.
Cuestiones pendientes:
1) Verificar que, en efecto, esta propuesta cumple todos los postulados antes expuestos.
2) Aplicar esta teoría al cálculo de la dificultad de Sudokus u otros juegos similares.
(A la parte 12)
