Encontre todos os caminhos entre dois nós do gráfico

Eu estou trabalhando em uma implementação do Algoritmo Dijkstras para recuperar o caminho mais curto entre os nós interconectados em uma rede de rotas. Eu tenho a implentação funcionando. Ele retorna todos os caminhos mais curtos para todos os nós quando eu passo o nó inicial para o algoritmo.

Minha pergunta: Como é possível recuperar todos os caminhos possíveis do Nó A para o Nó G ou até mesmo todos os caminhos possíveis do Nó A e de volta para o Nó A?

    Encontrar todos os caminhos possíveis é um problema difícil, pois há um número exponencial de caminhos simples. Mesmo encontrar o kth caminho mais curto [ou o caminho mais longo] é NP-Hard .

    Uma solução possível para encontrar todos os caminhos [ou todos os caminhos até um certo comprimento] de s para t é BFS , sem manter um conjunto visited , ou para a versão ponderada – você pode querer usar busca de custo uniforme

    Note que também em cada gráfico que possui ciclos [não é um DAG ], pode haver um número infinito de caminhos entre s para t .

    Eu implementei uma versão onde basicamente encontra todos os caminhos possíveis de um nó para o outro, mas não conta com nenhum ‘ciclo’ possível (o gráfico que estou usando é cíclico). Então, basicamente, nenhum nó aparecerá duas vezes no mesmo caminho. E se o gráfico fosse acíclico, suponho que você poderia dizer que parece encontrar todos os caminhos possíveis entre os dois nós. Parece estar funcionando muito bem, e para o tamanho do meu gráfico de ~ 150, ele roda quase instantaneamente na minha máquina, embora eu tenha certeza que o tempo de execução deve ser algo exponencial e assim ele vai começar a ficar lento rapidamente gráfico fica maior.

    Aqui está um código Java que demonstra o que eu implementei. Tenho certeza que deve haver maneiras mais eficientes ou elegantes de fazê-lo também.

     Stack connectionPath = new Stack(); List connectionPaths = new ArrayList<>(); // Push to connectionsPath the object that would be passed as the parameter 'node' into the method below void findAllPaths(Object node, Object targetNode) { for (Object nextNode : nextNodes(node)) { if (nextNode.equals(targetNode)) { Stack temp = new Stack(); for (Object node1 : connectionPath) temp.add(node1); connectionPaths.add(temp); } else if (!connectionPath.contains(nextNode)) { connectionPath.push(nextNode); findAllPaths(nextNode, targetNode); connectionPath.pop(); } } } 

    Vou lhe dar uma versão (um tanto pequena) (embora compreensível, eu acho) de uma prova científica de que você não pode fazer isso sob uma quantidade de tempo viável.

    O que eu vou provar é que a complexidade de tempo para enumerar todos os caminhos simples entre dois nós selecionados e distintos (digamos, s e t ) em um grafo arbitrário G não é polinomial. Observe que, como nos preocupamos apenas com a quantidade de caminhos entre esses nós, os custos de borda não são importantes.

    Claro que, se o gráfico tiver algumas propriedades bem selecionadas, isso pode ser fácil. Eu estou considerando o caso geral embora.


    Suponha que tenhamos um algoritmo polinomial que liste todos os caminhos simples entre s e t .

    Se G estiver conectado, a lista não está vazia. Se G não é e s e t estão em componentes diferentes, é realmente fácil listar todos os caminhos entre eles, porque não há nenhum! Se eles estão no mesmo componente, podemos fingir que o gráfico inteiro consiste apenas daquele componente. Então, vamos supor que G está de fato conectado.

    O número de caminhos listados deve ser polinomial, caso contrário, o algoritmo não poderia me retornar todos eles. Se enumerar todos eles, deve me dar o mais longo, então está lá. Tendo a lista de caminhos, um procedimento simples pode ser aplicado para me apontar qual é o caminho mais longo.

    Podemos mostrar (embora eu não consiga pensar em uma maneira coesiva de dizê-lo) que esse caminho mais longo tenha que atravessar todos os vértices de G Assim, acabamos de encontrar um caminho hamiltoniano com um procedimento polinomial! Mas esse é um problema bem conhecido de NP.

    Podemos então concluir que é improvável que esse algoritmo polinomial que pensamos ter, a menos que P = NP .

    Aqui está um algoritmo encontrando e imprimindo todos os caminhos de s para t usando a modificação do DFS. Também programação dinâmica pode ser usada para encontrar a contagem de todos os caminhos possíveis. O pseudo código ficará assim:

     AllPaths(G(V,E),s,t) C[1...n] //array of integers for storing path count from 's' to i TopologicallySort(G(V,E)) //here suppose 's' is at i0 and 't' is at i1 index for i<-0 to n if i 

    Você geralmente não quer, porque há um número exponencial deles em charts não triviais; Se você realmente deseja obter todos os caminhos (simples) ou todos os ciclos (simples), basta encontrar um (percorrendo o gráfico) e voltar para outro.

    Eu acho que o que você quer é alguma forma do algoritmo Ford-Fulkerson que é baseado no BFS. É usado para calcular o stream máximo de uma rede, localizando todos os caminhos de aumento entre dois nós.

    http://en.wikipedia.org/wiki/Ford%E2%80%93Fulkerson_algorithm

    caminhos_cadinhos [s, t, d, k]

    Esta questão é agora um pouco antiga … mas vou jogar o meu chapéu no ringue.

    Eu pessoalmente acho um algoritmo da forma find_paths[s, t, d, k] útil, onde:

    • s é o nó inicial
    • t é o nó de destino
    • d é a profundidade máxima para pesquisar
    • k é o número de caminhos para encontrar

    Usando a forma de infinito da sua linguagem de programação para dek lhe dará todos os caminhos.

    § obviamente, se você estiver usando um grafo direcionado e quiser todos os caminhos não direcionados entre s e t você terá que rodar das duas formas:

     find_paths[s, t, d, k]  find_paths[t, s, d, k] 

    Função auxiliar

    Eu pessoalmente gosto de recursion, embora possa dificultar algumas vezes, de qualquer maneira primeiro vamos definir nossa function auxiliar:

     def find_paths_recursion(graph, current, goal, current_depth, max_depth, num_paths, current_path, paths_found) current_path.append(current) if current_depth > max_depth: return if current == goal: if len(paths_found) <= number_of_paths_to_find: paths_found.append(copy(current_path)) current_path.pop() return else: for successor in graph[current]: self.find_paths_recursion(graph, successor, goal, current_depth + 1, max_depth, num_paths, current_path, paths_found) current_path.pop() 

    Função principal

    Com isso fora do caminho, a function principal é trivial:

     def find_paths[s, t, d, k]: paths_found = [] # PASSING THIS BY REFERENCE find_paths_recursion(s, t, 0, d, k, [], paths_found) 

    Primeiro, vamos notar uma coisa:

    • o pseudo-código acima é um mash-up de linguagens - mas mais fortemente parecido com python (já que eu estava apenas codificando nele). Um copy-paste estrito não funcionará.
    • [] é uma lista não inicializada, substitua isto pelo equivalente para a sua linguagem de programação preferida
    • paths_found é passado por referência . É claro que a function de recursion não retorna nada. Lide com isso apropriadamente.
    • aqui graph está assumindo alguma forma de estrutura hashed . Há uma infinidade de maneiras de implementar um gráfico. De qualquer forma, o graph[vertex] fornece uma lista de vértices adjacentes em um gráfico direcionado - ajuste de acordo.
    • Isso pressupõe que você tenha pré-processado para remover "fivelas" (auto-loops), ciclos e multi-arestas

    Se você realmente se importa em ordenar seus caminhos do caminho mais curto para o caminho mais longo, então seria muito melhor usar um Algoritmo A * ou Dijkstra modificado . Com uma pequena modificação, o algoritmo retornará o maior número possível de caminhos possíveis, na ordem do caminho mais curto primeiro. Então, se o que você realmente quer é todos os caminhos possíveis, ordenados do mais curto ao mais longo, então este é o caminho a percorrer.

    Se você quiser uma implementação baseada em A * capaz de retornar todos os caminhos ordenados do mais curto para o mais longo, o seguinte realizará isso. Tem várias vantagens. Em primeiro lugar, é eficiente na sorting do mais curto para o mais longo. Além disso, ele calcula cada caminho adicional apenas quando necessário, portanto, se você parar mais cedo, porque não precisa de todos os caminhos, economizará algum tempo de processamento. Ele também reutiliza dados para caminhos subseqüentes toda vez que calcula o próximo caminho para que seja mais eficiente. Finalmente, se você encontrar algum caminho desejado, poderá abortar antecipadamente, economizando algum tempo de computação. Em geral, esse deve ser o algoritmo mais eficiente se você se importar com a sorting por comprimento de caminho.

     import java.util.*; public class AstarSearch { private final Map> adjacency; private final int destination; private final NavigableSet pending = new TreeSet<>(); public AstarSearch(Map> adjacency, int source, int destination) { this.adjacency = adjacency; this.destination = destination; this.pending.add(new Step(source, null, 0)); } public List nextShortestPath() { Step current = this.pending.pollFirst(); while( current != null) { if( current.getId() == this.destination ) return current.generatePath(); for (Neighbor neighbor : this.adjacency.get(current.id)) { if(!current.seen(neighbor.getId())) { final Step nextStep = new Step(neighbor.getId(), current, current.cost + neighbor.cost + predictCost(neighbor.id, this.destination)); this.pending.add(nextStep); } } current = this.pending.pollFirst(); } return null; } protected int predictCost(int source, int destination) { return 0; //Behaves identical to Dijkstra's algorithm, override to make it A* } private static class Step implements Comparable { final int id; final Step parent; final int cost; public Step(int id, Step parent, int cost) { this.id = id; this.parent = parent; this.cost = cost; } public int getId() { return id; } public Step getParent() { return parent; } public int getCost() { return cost; } public boolean seen(int node) { if(this.id == node) return true; else if(parent == null) return false; else return this.parent.seen(node); } public List generatePath() { final List path; if(this.parent != null) path = this.parent.generatePath(); else path = new ArrayList<>(); path.add(this.id); return path; } @Override public int compareTo(Step step) { if(step == null) return 1; if( this.cost != step.cost) return Integer.compare(this.cost, step.cost); if( this.id != step.id ) return Integer.compare(this.id, step.id); if( this.parent != null ) this.parent.compareTo(step.parent); if(step.parent == null) return 0; return -1; } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Step step = (Step) o; return id == step.id && cost == step.cost && Objects.equals(parent, step.parent); } @Override public int hashCode() { return Objects.hash(id, parent, cost); } } /******************************************************* * Everything below here just sets up your adjacency * * It will just be helpful for you to be able to test * * It isnt part of the actual A* search algorithm * ********************************************************/ private static class Neighbor { final int id; final int cost; public Neighbor(int id, int cost) { this.id = id; this.cost = cost; } public int getId() { return id; } public int getCost() { return cost; } } public static void main(String[] args) { final Map> adjacency = createAdjacency(); final AstarSearch search = new AstarSearch(adjacency, 1, 4); System.out.println("printing all paths from shortest to longest..."); List path = search.nextShortestPath(); while(path != null) { System.out.println(path); path = search.nextShortestPath(); } } private static Map> createAdjacency() { final Map> adjacency = new HashMap<>(); //This sets up the adjacencies. In this case all adjacencies have a cost of 1, but they dont need to. addAdjacency(adjacency, 1,2,1,5,1); //{1 | 2,5} addAdjacency(adjacency, 2,1,1,3,1,4,1,5,1); //{2 | 1,3,4,5} addAdjacency(adjacency, 3,2,1,5,1); //{3 | 2,5} addAdjacency(adjacency, 4,2,1); //{4 | 2} addAdjacency(adjacency, 5,1,1,2,1,3,1); //{5 | 1,2,3} return Collections.unmodifiableMap(adjacency); } private static void addAdjacency(Map> adjacency, int source, Integer... dests) { if( dests.length % 2 != 0) throw new IllegalArgumentException("dests must have an equal number of arguments, each pair is the id and cost for that traversal"); final Set destinations = new HashSet<>(); for(int i = 0; i < dests.length; i+=2) destinations.add(new Neighbor(dests[i], dests[i+1])); adjacency.put(source, Collections.unmodifiableSet(destinations)); } } 

    A saída do código acima é o seguinte:

     [1, 2, 4] [1, 5, 2, 4] [1, 5, 3, 2, 4] 

    Observe que cada vez que você chama nextShortestPath() ele gera o próximo caminho mais curto para você sob demanda. Ele calcula apenas as etapas extras necessárias e não percorre nenhum caminho antigo duas vezes. Além disso, se você decidir que não precisa de todos os caminhos e finalizar a execução cedo, economizou tempo de computação considerável. Você só calcula até o número de caminhos que você precisa e não mais.

    Finalmente, deve-se notar que os algoritmos A * e Dijkstra têm algumas limitações menores, embora eu não ache que isso afetaria você. Ou seja, não funcionará bem em um gráfico que tenha pesos negativos.

    Aqui está um link para o JDoodle onde você pode executar o código no navegador e vê-lo funcionando. Você também pode alterar o gráfico para mostrar que ele também funciona em outros charts: http://jdoodle.com/a/ukx

    Suponho que você queira encontrar caminhos “simples” (um caminho é simples se nenhum nó aparecer nele mais de uma vez, exceto talvez o primeiro e o último).

    Como o problema é NP-hard, você pode querer fazer uma variante de pesquisa em profundidade.

    Basicamente, gere todos os caminhos possíveis de A e verifique se eles acabam em G.

    Há um artigo legal que pode responder a sua pergunta / somente ele imprime os caminhos ao invés de colecioná-los /. Por favor, note que você pode experimentar com as amostras de C ++ / Python no IDE on-line.

    http://www.geeksforgeeks.org/find-paths-given-source-destination/