Eu encontrei recentementeisso (Editar: Problema A) problema interessante do desafio hacker do Spotify no início deste ano, que envolve a determinação da troca de junções de caminhões de trem para direcionar um trem de volta ao ponto de partida. O trem deve chegar na mesma direção em que saiu e o trem nunca pode reverter nos trilhos.

Pelo que entendi, o problema pode ser modelado como um grafo não direcionado (?) Onde devemos encontrar o ciclo mais curto de um certo vértice, ou detectar que esse ciclo não existe. No entanto, a parte interessante é que, para um vértice, v, os vértices adjacentes a v são dependentes do caminho tomado para v, de modo que o gráfico pode ser considerado direcionado, embora essa direção seja dependente do caminho.

Meu primeiro pensamento foi modelar cada nó como três vértices separados, A, B e C, onde A <-> B e A <-> C, e então usar uma pesquisa de amplitude para construir uma árvore de busca até encontrarmos o original. vértice, mas isso é complicado pela advertência acima, ou seja, que as adjacências para um determinado vértice dependem do vértice anterior que visitamos. Isso significa que na nossa árvore BFS, nós podem ter múltiplos pais.

Obviamente, uma simples busca BFS não será suficiente para resolver este problema. Eu sei que existem algoritmos que existem para detectar ciclos em um gráfico. Uma abordagem pode ser detectar todos os ciclos e, em seguida, para cada ciclo, detectar se o caminho é válido. (isto é, não inverte a direção)

Alguém mais tem alguma idéia sobre abordagens para resolver esse problema?

ATUALIZAR: Eu segui a abordagem sugerida por @Karussell nos comentários.

Aqui está a minha solução no github.

O truque era modelar a situação usando um gráfico baseado em borda, não um gráfico tradicional baseado em vértices. O arquivo de entrada fornecido no concurso é convenientemente especificado em termos de arestas já, portanto, esse arquivo pode ser facilmente usado para construir um gráfico baseado em arestas.

O programa usa duas classes importantes: Road e Solver. Uma estrada tem dois campos inteiros, j1 e j2. j1 representa a junção de origem e j2 representa a junção de destino. Cada estrada é unidirecional, o que significa que você só pode viajar de j1 para j2. Cada estrada também inclui uma LinkedList de estradas adjacentes e uma estrada pai. A classe Road também inclui métodos estáticos para converter entre as strings usadas no arquivo de entrada e índices inteiros que representam os pontos A, B e C em cada junção.

Para cada entrada no arquivo de entrada, adicionamos duas estradas a um HashMap, uma estrada para cada direção entre as duas junções. Agora temos uma lista de todas as estradas que correm entre as junções. Nós só precisamos conectar as estradas juntas nas junções através dos comutadores A, B e C. Se uma estrada termina em Junction.A, procuramos as estradas que começam em Junction.B e Junction.C e adicionamos essas estradas como adjacentes. A função buildGraph () retorna a Estrada cuja junção de destino (j2) é "1A" == índice 0.

Neste ponto, nosso gráfico é construído. Para encontrar o caminho mais curto, simplesmente usei um BFS para percorrer o gráfico. Deixamos a raiz desmarcada e começamos a enfileirar as adjacências da raiz. Se encontrarmos uma estrada cuja junção de destino é "1A" (índice 0), então encontramos o ciclo mais curto através do ponto de partida. Depois que reconstruímos o caminho usando a propriedade pai de cada Estrada, é uma tarefa trivial configurar os comutadores apropriadamente conforme necessário no problema.

Obrigado a Karussell por sugerir essa abordagem. Se você quiser colocar seu comentário no formulário de resposta com uma breve explicação, eu o aceitarei. Graças a @Origin também. Devo admitir que não segui totalmente a lógica da sua resposta, mas isso certamente não quer dizer que isso não seja correto. Se alguém resolver esse problema usando sua solução, eu ficaria muito interessado em vê-lo.