Linear Array com nodos aleatoriamente ligadas a outros nós na matriz, caminho mais curto

Question

INFO: I têm uma série de nodos 100, [0 .. 99]. Cada nó pode ter um número arbitrário de nós ligados:

EG1, 0 links para 5, 10, 15, 20. EG2, 1 ligações a 30, 40, 50. EG3, etc ..

Todos os 100 nós têm pelo menos um nó ligado, nós não sabemos quem links para eles.

PERGUNTA: Como posso encontrar o menor link-caminho se fornecido com início e fim.

por exemplo. INÍCIO = 5, END = 80, Caminho Link (exemplo):? [5] -> 10> 24> 36 -> [80]

Eu estou usando Pascal e / ou PHP, mas a compreensão de como é que eu estou procurando [code também ajuda].

Answer 1

A abundância de leitura / algoritmos: Shortest problema do caminho . Você efetivamente apenas tem cada borda ( "link", como você chamou) com um peso igual.

Answer 2

Faça uma amplitude Primeira Travessia começando com o nó Iniciar e parar assim que encontrar o nó final.

Answer 3

Isso tem ciclos? ou seja, é um DAG?

Se não houver ciclos:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {   
       //If this is the node you are looking for...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the end node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       List<Node> bestPath = null;

       foreach(Node child in startNode.Children)
       {             
          //get the shortest path from this child
          List<Node> childPath = GetShortestPath(child, endNode);
          if (childPath != null &&
             ( bestPath == null || childPath.Count < bestPath.Count))
          { 
              bestPath = childPath;
          }
       }

       bestPath.Insert(0, startNode);
       return bestPath;
    }

[Edit: Adicionado um exemplo para ciclos] Se não pode haver ciclos:

   List<Node> GetShortestPath(Node startNode, Node endNode)
   {
        List<Node> nodesToExclude = new List<Node>();
        return GetShortestPath(startNode, endNOde, nodesToExclude);
   }

   List<Node> GetShortestPath(Node startNode, Node endNode, List<Node> nodesToExclude)
   {   
       nodesToExclude.Add(startNode);

       List<Node> bestPath = null;

       //If this is end node...
       if (startNode.ReferenceEquals(endNode))
       {
           //return a list with just the child node
           List<Nodes> result = new List<Nodes>();
           result.Add(endNode);            
           return result;
       }

       foreach(Node child in startNode.Children)
       {
          if (!nodesToExclude.Contains(child))
          {
              //get the shortest path from this child
              List<Node> childPath = GetShortestPath(child, endNode);
              if (childPath != null &&
                 ( bestPath == null || childPath.Count < bestPath.Count))
              { 
                  bestPath = childPath;
              }
          }
       }

       nodesToExclude.Remove(startNode);
       bestPath.Insert(0, child);

       return bestPath;
    }

Answer 4

Duas estruturas: um conjunto e uma lista.

No set, você armazenar os nós que já visitou. Isso impede que você ciclos seguintes.

A lista de objectos é que contenham: (1) um nó, e (2) uma parte traseira do apontador para o nó que encontrou

.

Começando no nó de início, adicioná-lo ao conjunto, adicioná-lo à lista com uma referência nula para trás, e em seguida, adicione todos os nós que podem chegar à lista de referências de volta para o índice 0 na lista (o iniciar nó).

Então, para cada elemento na lista depois disso, até você chegar ao fim, faça o seguinte:

1. se ele está no conjunto já ignorá-lo (você já o visitaram) e passar para o próximo item na lista.
2. Caso contrário, adicioná-lo ao conjunto, e adicione todos os nós que podem chegar à lista de referências de volta para o índice que você está 'olhando' para o final da lista. Então vá para o próximo índice na lista e repita.

Se em algum momento você chegar ao nó final (optimamente como você está adicionando-o à lista - em oposição a visitá-lo na lista), rastrear através das referências de volta para o nó de início e inverter o caminho

Exemplo:

nós dados de 0 a 3, onde
node0 -> node1
node0 -> node2
node1 -> node2
node2 -> node3
e node0 é INICIAR e node3 é END

SET = {}
LIST = []

Passo 1 - adicionar INÍCIO:

SET = {} node0
LIST = [[node0, null]]

Passo 2 - no índice 0 da lista - adicionar nós alcançáveis:

SET = {node0, node1, node2}
LIST = [ [node0, null] , [node1, 0], [node2, 0]]

Passo 3 - no índice 1 da lista - adicionar nós alcançáveis:

node2 já está no SET. ignorar a adição de nós alcançáveis ??para LIST.
SET = {node0, node1, node2}
LIST = [[node0, null], [node1, 0] , [node2, 0]]

Passo 4 - no índice 2 da lista - adicionar nós alcançáveis:

SET = {node0, node1, node2, node3}
LIST = [[node0, null], [node1, 0], [node2, 0] , [node3, 2]]

Passo 5 - alcançou END, agora backtrack:

O nó FIM (node3) inserido na lista tem uma referência de volta para o índice 2 na lista, que é nó 2. Isto tem uma referência de volta para o índice 0 na lista, que é node0 (START). Inverter esta e você terá um caminho mais curto de node0 -> node2 -.> Node3

Answer 5

Esta é uma árvore / gráfico ou uma floresta? Se é uma floresta, o caminho não pode ser definida sempre. No caso esta é uma árvore / gráfico, tente usar em largura-Search.

Pense nisso desta maneira: digamos, você está fora em uma missão stealth para encontrar pintainhos bonitos em sua vizinhança. Você começa na sua própria casa e marcá-lo como START. Você iria ao lado ir para bater em seus vizinhos mais próximos, certo? Então, vamos fazer exatamente isso - empurrar todos os nós conectados ao começo em uma fila. Agora, repetir a pesquisa vizinho para todos os nós nesta fila. E continuar fazendo isso até chegar a sua menina, err, a END.