Caminho de comprimento fixo entre dois nós do gráfico

Question

Existe um algoritmo que, se receber dois nós em um gráfico, encontrar uma rota entre eles que leva o número especificado de saltos? Qualquer nó pode ser conectado a qualquer outro.

Os pontos do momento estão localizados no espaço 2D, então não tenho certeza se um gráfico é a melhor abordagem.

Answer 1

Se você tem nós está procurando encontrar rotas em termos de salto, um gráfico provavelmente é a abordagem correta. Não tenho certeza se entendi o que você está tentando fazer e quais são as restrições, especialmente em relação a "qualquer nó pode ser conectado a qualquer outro" .. o que parece um pouco aberto.

Desconsiderando isso, no entanto; Com alguma representação gráfica:

Parece começar no primeiro nó e fazer uma primeira pesquisa de profundidade a partir daí e encerrar uma pesquisa se (a) o salto obtido for maior que o seu número especificado ou (b) chegamos ao segundo nó; Isso determinará o primeiro (não apenas) caminho que conecta os dois nós (no máximo) que muitos saltos.

Se tiver que ser exatamente o salto especificado, encerre qualquer ramo da pesquisa se o salto tiver passado e rescindir com o sucesso se você também tiver chegado ao segundo nó.

Answer 2

Você tentou DFs de profundidade iterada?

Answer 3

Abordagem idiota: (a estrutura de dados é uma matriz de pilhas). Isso está basicamente fazendo a primeira pesquisa em largura (BFS) para a profundidade n, exceto que, se os loops forem permitidos (você não esclareceu, mas presumo que eles sejam), você não exclui os nós visitados de pesquisas adicionais.

1. Empurre o nó inicial em uma pilha armazenada na matriz no índice 0 (índice = profundidade)

2. Para cada nível/índice "L" 0-N:

   Para cada nó em uma pilha armazenada no nível "L", encontre todos os seus vizinhos e empurre -os para uma pilha armazenada no nível "L+1".

   Importante: Se sua tarefa permitir encontrar caminhos que contenham loops, não verifique se você já visitou algum nó que adicionar. Se não permitir loops, use um hash de nós visitados para não adicionar nenhum nó duas vezes **

3. Pare quando terminar o nível "N-1".

4. Faça um loop sobre todos os nós que você acabou de adicionar ao Index "N" e encontre seu nó de destino. Se encontrado: sucesso, se não, não há esse caminho.

Observe que, se "todos os nós podem ser conectados", você está implicando um gráfico totalmente conectado, existe uma resposta matemática que não está envolvendo os nós realmente visitando

(No entanto, a fórmula é muito longa para escrever no campo de entrada de texto do StackOverflow)