Recientemente me encontréesto (Edit: Problema A) Un problema interesante del desafío de piratas informáticos de Spotify a principios de este año, que consiste en determinar el cambio en los cruces de los camiones para encaminar un tren hasta su punto de partida. El tren debe llegar en la misma dirección que la izquierda y el tren nunca puede retroceder en las vías.

Como lo entiendo, el problema puede ser modelado como un gráfico no dirigido (?) Donde debemos encontrar el ciclo más corto de un vértice determinado, o detectar que no existe dicho ciclo. Sin embargo, la parte interesante es que para un vértice, v, los vértices adyacentes a v dependen de la trayectoria tomada en v, por lo que, en cierto sentido, el gráfico podría considerarse dirigido, aunque esta dirección depende de la trayectoria.

Mi primer pensamiento fue modelar cada nodo como 3 vértices separados, A, B y C, donde A <-> B y A <-> C, y luego usar una búsqueda de amplitud para construir un árbol de búsqueda hasta que encontremos el original vértice, pero esto se complica por la advertencia anterior, a saber, que las adyacencias para un vértice dado dependen del vértice anterior que visitamos. Esto significa que en nuestro árbol BFS, los nodos pueden tener varios padres.

Obviamente, una simple búsqueda BFS no será suficiente para resolver este problema. Sé que hay algoritmos que existen para detectar ciclos en una gráfica. Un enfoque podría ser detectar todos los ciclos, luego, para cada ciclo, detectar si la ruta es válida. (es decir, no invierte la dirección)

¿Alguien más tiene alguna idea sobre los enfoques para resolver este problema?

ACTUALIZAR: Seguí el enfoque sugerido por @Karussell en los comentarios.

Aquí está mi solución en github.

El truco consistió en modelar la situación utilizando un gráfico basado en bordes, no un gráfico tradicional basado en vértices. El archivo de entrada suministrado en el concurso ya se ha especificado convenientemente en términos de bordes, por lo que este archivo se puede usar fácilmente para crear un gráfico basado en bordes.

El programa utiliza dos clases importantes: Road y Solver. Un camino tiene dos campos enteros, j1 y j2. j1 representa la unión de origen y j2 representa la unión de destino. Cada camino es unidireccional, lo que significa que solo puede viajar de j1 a j2. Cada camino también incluye una lista enlazada de caminos adyacentes y un camino principal. La clase Road también incluye métodos estáticos para convertir entre las cadenas utilizadas en el archivo de entrada y los índices enteros que representan los puntos A, B y C en cada unión.

Para cada entrada en el archivo de entrada, agregamos dos Carreteras a un HashMap, una Carretera para cada dirección entre las dos uniones. Ahora tenemos una lista de todos los caminos que se ejecutan entre uniones. Solo necesitamos conectar las carreteras juntas en los cruces a través de los interruptores A, B y C. Si una Carretera termina en Junction.A, buscamos las carreteras que comienzan en Junction.B y Junction.C y agregamos estas carreteras como adyacentes. La función buildGraph () devuelve la Carretera cuya unión de destino (j2) es "1A" == índice 0.

En este punto, nuestra gráfica está construida. Para encontrar la ruta más corta, simplemente usé un BFS para atravesar el gráfico. Dejamos la raíz sin marcar y comenzamos por poner en cola las adyacencias de la raíz. Si encontramos una carretera cuyo cruce de destino es "1A" (índice 0), hemos encontrado el ciclo más corto hasta el punto de partida. Una vez que reconstruimos la ruta usando la propiedad principal de cada Camino, es un asunto trivial configurar los interruptores de manera apropiada según lo requerido en el problema.

Gracias a Karussell por sugerir este enfoque. Si desea poner su comentario en forma de respuesta con una breve explicación, lo aceptaré. Gracias a @Origin, también. Debo admitir que no seguí completamente la lógica de su respuesta, pero eso no quiere decir que no sea correcto. Si alguien resuelve este problema usando su solución, estaría muy interesado en verlo.