Soluciones Desafío 63

Pardillano dice:

Ante todo, daros las gracias a todos por la participación en el Primer Concurso Pitagórigo de Diseño de Laberintos. Si, eso significa lo que os teméis, que habrá secuela. Pero vayamos con lo primero, los resultados:

– Ganadores del premio “puñetero”, por orden alfabético: Dospew, Rubenman, Sebas, SPZ

– Ganadores del premio “majete”: Dospew, Rubenman, Sebas, SPZ

Aunque no ha enviado solución, Suschus también ha estado ahí dándole vueltas.

El “truco” del desafío es que todos los laberintos tienen la misma complejidad, y que los premios se otorgan en función de la incertidumbre, para la que resulta sencillo encontrar casos en que se maximiza o minimiza. Lo curioso es que todos habéis optado por soluciones con dos ramales, cuando hay soluciones para el premio “Puñetero” más “parecidas” a un típico laberinto.

Respecto a las soluciones recibidas, Rubenman fue el primero en enviar su respuesta. Además de la calcular la complejidad e incertidumbre del laberinto, incluye las respuestas a las preguntas para debatir. Impecables las de las celdas de entrada y las celdas inaccesibles. Para la de los caminos circulares, que es la que tiene miga, su razonamiento lleva a conclusiones opuestas a las mías. A estas alturas yo se que el mío falla, y no puedo rebatir el de Rubenman, pero las simulaciones tampoco lo corroboran.

SPZ desarrolla una demostración y encuentra una utilidad inesperada al diseñador de laberintos, que podréis ver al final de su solución, y que me he permitido copiar para la imagen.  Además, SPZ ha estado dándole vueltas a las preguntas para debatir, particularmente a los “Caminos circulares y la madre que los parió”. Aunque no encontraréis nada de esto en la solución que envía, se ha estado volviendo loco con ellos, sobre todo porque se me olvidó advertirle de que el simulador no los representaba como es de esperar.

Imagen_blog

El proximo jueves nuevo Desafio, Sebas y sus triángulos…

D63-Dospew

D63_Pardillano

D63_Rubenman

D63_sebas

D63_Sebas

 D63_SPZ

Anuncios

12 pensamientos en “Soluciones Desafío 63

  1. Desde mi punto de vista intuitivo y no demostrado, los caminos circulares dentro de ramales sin salida serían indiferentes, y los que estén en el camino correcto, depende. En los casos en que un nuevo camino acorte el camino correcto, aumentará la incertidumbre, y en los casos en que lo alargue, la disminuirá.
    Si el nuevo camino es igual de largo, la incertidumbre quedará igual. La complejidad no cambiará en ningún caso.
    No estoy seguro de entender el razonamiento de Rubenman. Parece dar importancia al hecho de que dependiendo del azar, haya zonas que no se visiten (las rosas). Yo creo que eso no importa. La incertidumbre se calcula con el peor caso posible, y ese tendrá que pasar por todas las casillas… a no ser que la estructura de las paredes y las reglas de movimiento del explorador garanticen que se tiene que dejar alguna zona sin visitar. Esto no lo veo nada claro, pero si fuera así, afectaría también a la complejidad.
    Si el simulador está en lo cierto, y la complejidad es constante, supongo que eso implica que en el peor de los casos, el explorador gafe lo recorre todo.

    Suschus, si estás perdido ahí dentro, ¡corre hacia la luz!
    O mejor no, ¡hay un triángulo esperando aquí fuera!

    • El problema de los circulares creo que esdebido a que haría falta alguna norma adicional, esa es mi conclusión después de haber estudiado (en papel) varios supuestos.
      Creo que cada uno lo hemos interpretado aplicando alguna condición o restricción ya sea lógica o menos lógica. Este caso requiría alguna aclaración más.
      Según interpreto yo el caso, en un camino circular de una entrada, no se estaría obligado a pasar por todas las casillas. Y si se interpreta que sí, la cosa cambia obviamente.
      Obviamente en el peor de los casos, siempre se explorará todo. Pero si el camino es circular sin ramificaciones, tampoco se pasaría 2 veces por todas las casillas.
      La casuística es mucho más variada de lo que parece.

      • Es decir, que tú crees que el peor caso no siempre es posible, ¿no?
        En ese caso, además de afectar a la incertidumbre, debería bajar la complejidad, pero el simulador (sin normas adicionales) no lo indica.

        • Sí que es posible, no interpretemos mal. Otra cosa es que siempre que se meta por ahí, deba hacer el recorrido completo 2 veces. Ahí es donde podemos estar interpretando variantes en uno u otro sentido, que hagan ver a favor o en contra.

  2. Enhorabuena a todos por vuestras soluciones.
    Me ha resultado muy llamativo el cambio de la complejidad estimada al aumentar el número de simulaciones. Casos que inicialmente parecía que iban a dar un valor alto, o un valor bajo, se terminan aproximando a 101, pero con fluctuaciones muy altas. La convergencia parece muy débil.

  3. Una aclaración respecto a los caminos circulares, que no he expresado bien. Rubenman preparó su respuesta ANTES de que yo definiera el comportamiento del explorador para estos casos. Sin esa norma adicional, me parece que el análisis de Rubenman es correcto.

    La norma adicional es la que se explicaba en el addendum al desafío, y consiste en que si llegamos a través de un camino circular a una celda ya visitada, no penetraremos en ella. Actuaremos como si nos hubiéramos encontrado una pared. Con esa norma, algunos de los supuestos de Rubenman no se pueden dar. Por ejemplo, si entras en una zona sin salida, la recorrerás toda, y no te puedes dejar celdas sin visitar aun cuando dentro de la zona haya caminos circulares.

    Esta es la norma que sigue el simulador, como podréis ver en el caso del explorador gafe para el laberinto diáfano que está en mi solución.

    Yo me he liado al redactar los comentarios de las soluciones. El simulador no contradice el análisis de Rubenman sin la norma adicional. Lo que podría contradecir es esas mismas conclusiones si se obtuvieran considerando la norma adicional. Pero no es el caso.

    Considerando la norma adicional, parece experimentalmente que la complejidad no varía. Pero incluso sobre esto deberíamos mantener un resquicio de duda. Como dice Suschus, la convergencia es muy baja. Para alguno de los supuestos que meto en mi solución, después de efectuar 50000 simulaciones la complejidad me quedaba más cerca de 100 que de 101. Lo solucioné borrando todas y ejecutando otras 50000. Quizá, si la complejidad varía muy poco, necesitemos 1.000.000 de simulaciones para comprobarlo. Pero, bueno, digamos que casi con total seguridad la complejidad permanece invariante. ¿Cómo demostrarlo?

Responder

Introduce tus datos o haz clic en un icono para iniciar sesión:

Logo de WordPress.com

Estás comentando usando tu cuenta de WordPress.com. Cerrar sesión / Cambiar )

Imagen de Twitter

Estás comentando usando tu cuenta de Twitter. Cerrar sesión / Cambiar )

Foto de Facebook

Estás comentando usando tu cuenta de Facebook. Cerrar sesión / Cambiar )

Google+ photo

Estás comentando usando tu cuenta de Google+. Cerrar sesión / Cambiar )

Conectando a %s