Caminho mais curto em um gráfico não direcionado?

19

Então eu pensei que essa pergunta (embora um pouco básica) pertencia aqui:

Digamos que eu tenha um gráfico do tamanho 100 nós dispostos em um padrão 10x10 (pense no tabuleiro de xadrez). O gráfico não é direcionado e não é ponderado. Mover-se pelo gráfico envolve mover três espaços para frente e um espaço para a direita ou esquerda (semelhante à maneira como um cavaleiro de xadrez se move através de um tabuleiro).

Dado um nó inicial fixo, como encontrar o caminho mais curto para qualquer outro nó no quadro?

Imaginei que haveria apenas uma aresta entre os nós que são movimentos viáveis. Portanto, com essas informações, eu gostaria de encontrar o caminho mais curto de um nó inicial para um nó final.

Meu pensamento inicial foi que cada aresta é ponderada com o peso 1. No entanto, o gráfico não é direcionado, portanto o Djikstras não seria o ajuste ideal. Portanto, decidi fazê-lo usando uma forma alterada de uma primeira pesquisa em profundidade.

No entanto, durante toda a minha vida, não consegui visualizar como obter o caminho mais curto usando a pesquisa.

Outra coisa que tentei foi colocar o gráfico em forma de árvore com o nó inicial como raiz e selecionar o resultado mais raso (menor número de linhas) que me deu o nó final desejado ... isso funcionou, mas foi incrivelmente ineficiente e, portanto, não funcionaria para um gráfico maior.

Alguém tem alguma idéia que possa me indicar a direção certa?

Muito obrigado.

(Tentei colocar uma visualização do gráfico, mas não consegui devido à minha baixa reputação)

gfppaste
fonte

Respostas:

19

Se as arestas no gráfico representam apenas movimentos válidos entre determinadas posições, o uso de Dijkstra funcionaria perfeitamente. No entanto, como o gráfico não é ponderado, isso seria um exagero. Uma simples busca pela primeira vez dará a resposta ideal.

Nicholas Mancuso
fonte
ohhhhhh cara, eu nem pensei em um BFS! muito obrigado!
Gfppaste
Como é um exagero? pode ser a implementação é um pouco mais difícil nada mais.
Eu também gostaria de acrescentar que o BFS é mais eficiente. BFS tem O(|E|), enquanto Dijkstra tem O(|E| + |V|log(|V|).
Doug Ramsey
@ user742 O BFS é mais rápido que o Djikstras. Djikstra é O(mn)enquanto BFS éO(V + E)
CodyBugstein
13

Nicholas já forneceu uma resposta perfeita. No entanto, deixe-me abordar sua tentativa original de usar a pesquisa profunda.

Primeiro, o Dijkstra (que funciona bem com os nós não ponderados, como observado por Nicholas Mancuso) ou a pesquisa pela primeira vez incorrem em desperdício exponencial de sua memória. Sua vantagem, no entanto, é que eles nunca reexpandem nenhum nó enquanto garantem a solução ideal. Infelizmente, sua limitação é bastante importante e não se espera que eles aumentem razoavelmente.

dmumaxkEudmumax+Eu×kdmumax=k=1 você tem a garantia de encontrar a solução ideal enquanto usa a memória linear na profundidade da solução.

bb-1b

Felicidades,

Carlos Linares López
fonte