3votos

Laberintos vieneses en Other

por josejuan hace 5 años

La solución anterior no era correcta (¿la leyó alguien? :P), ésta sí (da soluciones correctas en los test). El problema me ha gustado :D. Al final, se puede reducir a una búsqueda. No suelo deslumbrar al mundo con mis artes pictóricas, pero en este caso, he escaneado un croquis por si puede aclarar algo :D

Resolver el denominado laberinto vienés (Viennese Maze)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
Por un lado tenemos el problema de la transición de los semáforos. 
 
Para resolverlo, podemos transformar un grafo bidireccional 
 
    A <----> B 
 
en uno unidireccional, llamando a los nodos con subíndice 0 si 
están en los pasos 0-ésimos módulo 3, con subíndice 1 si están en 
los pasos 1-ésimos módulo 3 y con subíndice 2 si están en los pasos 
2-ésimos módulo 3. 
 
Así, el anterir quedaría como 
 
    A0 ----> B1 
    B0 ----> A1 
    A1 ----> B2 
    B1 ----> A2 
    A2 ----> B0 
    B2 ----> A0 
 
pero claro, esas transiciones ahora sí, podemos eliminar aquellas con 
semáforo en rojo (la tercera parte de ellas). 
 
Por otro lado, tenemos el problema de no poder volver atrás para aprovechar 
un cambio de verde a naranja. 
 
Para ello, convertimos el grafo anterior en otro, en el que los vértices 
del segundo son las aristas del primero, en este caso, tendríamos como 
vértices 
 
    A0B1, B0A1, A1B2, ... 
 
y las aristas vienen dadas por si podemos hacer el enlace, en este caso, 
nunca se podrá, porque siempre dos nodos 
 
    A1B2 ----> B2A0 
 
está volviendo al nodo A, luego esas aristas en el grafo a generar quedarán 
descartadas. 
 
Ahora, debemos unir los posibles nodos iniciales, que podemos llamar 
 
    startA, startB, startC, ... 
 
y crearemos aristas de éstos nodos a todos aquellos que empiezan por su letra, 
¡del primer paso! (subíndice 0) en el ejemplo 
 
    startA -----> A0B1 
    startB -----> B0A1 
 
Para los finales, es similar, pero nos sirve cualquier subíndice 
 
    A0B1 ----> B 
    A1B2 ----> B 
    A2B0 ----> B 
    ... 
 
A éste último grafo, aplicamos Dijkstra ¡y listo!. 
 
(Postearé una implementación en Haskell) 
3 comentarios
0votos

Escrito por drabor hace 5 años

Muy bueno +1!
Si no he entendido mal y resumiéndolo mucho, consiste en transformar un grafo 'dinámico' en uno 'estático', pero con el triple de vértices.
0votos

Escrito por josejuan hace 5 años

Gracias :)

Se transforma un grafo no dirigido (bidireccional) a otro sí dirigido (unidireccional), en dos pasadas: la primera para considerar las transiciones de los semáforos y la segunda para impedir volver por la arista que acabamos de usar (finalmente se añaden algunos nodos y aristas adicionales).

La transformación es tal, que realmente no hace falta usar Dijkstra, puede usarse cualquier algoritmo sobre todo el grafo, es más, se puede usar Floyd-Warshall para calcular de forma eficiente todas las rutas óptimas desde todos los nodos de origen a todos los nodos de destino (Floyd-Warshall es impresionante, calcula con coste cúbico O(|V|^3) una salida de tamaño cuadrático O(|V|^2)).

Es decir, una vez calculado, es todo lo que necesita nuestro ciclista para ir de cualquier sitio a cualquier sitio de forma eficiente.

En cuanto al tamaño del grafo final respecto del primero no es sencillo, una acotación por encima sí, pero requiere considerar el grado de los vértices (nº de aristas que apuntan al vértice); de ahí, que en la práctica será más representativo (útil) un valor medio del coste.

Comenta la solución

Tienes que identificarte para poder publicar tu comentario.