(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)
5 comentarios:
¿Muy interesante, hay bibliografía sobre el tema?
Realmente no conozco bibliografía sobre este tema específico.
El acercamiento a la complejidad de un laberinto ha sido muy interesante. Sin embargo, me temo que al desarrollar un poco más el tema (puede que un software que ejecute los cálculos?) encontrarás que finalmente se trate de un problema NP-completo (http://es.wikipedia.org/wiki/NP-completo), lo cual significa un gran desconsuelo, no?
Ánimo con el resto.
Veo mucha complicacián aqui sobre una custión trivial: la dificultad de los laberintos es directamente proporcional al "largo" de los muros con que está constriuido.
Para "resolverlos" hay que mantener contacto permanente con uno de los muros, es indistinto si el izquierdo o el derecho, y eso nos llevará directo a la salida. (O nuevamente a la entrada si se trata de laberintos imbricados)
Si el laberinto está bien construido, obligará a recorrer por completo toda la longitud de sus muros, si es de nodo simple, bastará con recorrer la mitad.
La propocicion de que la dificultad de un laberinto depende del largo de susu muros posiblemente sea util para ciertos laberintos por separados, pero se crea un problema al tratar e comparar dos laberintos pues con la anterior propuesta dos laberintos diferentes con igual longitud de sus muros podrian ser igualmente dificiles siendo que uno podria tener muchas mas deciciones que siguiendo solo un muro serian inutiles.
Se que serian muy pocos laberintos los que cumplan estas caracteristicas pero me parecio necesario plantear la duda.
Publicar un comentario