He intentado resolver el siguiente problema utilizando la matriz de adyacencia para encontrar el camino más corto entre la entrada y la salida de este laberinto. El truco de esto es que no se puede salir de un nodo usando el mismo color con el que se ha entrado por lo que cada nodo acaba siendo 3, uno para cada color, y se obtiene una matriz de adyacencia asimétrica y con software resolver el grafo dirigido usando dijsktra. El problema que tengo es que me he pasado un montón de horas intentando resolverlo pero no consigo hacer bien la matriz de adyacencia y no encuentro información sobre este problema en internet. Cada vez que rehago la matriz de adyacencia el algoritmo no encuentra el camino más corto así que empiezo a preguntarme si no hay camino posible entre los dos puntos. Lo publico aquí por dos razones:
- Este problema se publicó en la revista Scientific American, así que quizá alguien de aquí haya visto antes este laberinto y conozca la respuesta.
- ¿Hay alguna forma más sencilla de hallar la matriz de adyacencia o de resolverla para evitar trabajar con una matriz de 61x61? (¿Quizás algún software donde pueda dibujar manualmente el grafo y luego resolverlo o algo similar?)
Por ahora lo resuelvo con matlab. Intentaré subir el archivo .m que contiene la matriz con la que he estado trabajando por si a alguien le puede interesar comprobarlo. Cualquier información será muy apreciada. Gracias