Algoritmo gráfico para encontrar todas as conexões entre dois vértices arbitrários
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Estou tentando determinar o algoritmo com melhor eficiência de tempo para realizar a tarefa descrita abaixo.
Eu tenho um conjunto de registros.Para este conjunto de registros tenho dados de conexão que indicam como os pares de registros deste conjunto se conectam entre si.Isso representa basicamente um gráfico não direcionado, com os registros sendo os vértices e os dados de conexão as arestas.
Todos os registros do conjunto possuem informações de conexão (ou seja,nenhum registro órfão está presente;cada registro do conjunto se conecta a um ou mais registros do conjunto).
Quero escolher quaisquer dois registros do conjunto e poder mostrar todos os caminhos simples entre os registros escolhidos.Por "caminhos simples" quero dizer os caminhos que não possuem registros repetidos no caminho (ou seja,apenas caminhos finitos).
Observação:Os dois registros escolhidos serão sempre diferentes (ou seja,os vértices inicial e final nunca serão os mesmos;sem ciclos).
Por exemplo:
If I have the following records:
A, B, C, D, E
and the following represents the connections:
(A,B),(A,C),(B,A),(B,D),(B,E),(B,F),(C,A),(C,E),
(C,F),(D,B),(E,C),(E,F),(F,B),(F,C),(F,E)
[where (A,B) means record A connects to record B]
Se eu escolhesse B como meu registro inicial e E como meu registro final, eu gostaria de encontrar todos os caminhos simples através das conexões de registro que conectariam o registro B ao registro E.
All paths connecting B to E:
B->E
B->F->E
B->F->C->E
B->A->C->E
B->A->C->F->E
Este é um exemplo, na prática posso ter conjuntos contendo centenas de milhares de registros.
Solução
Parece que isso pode ser conseguido com uma pesquisa em profundidade do gráfico. A pesquisa em profundidade encontrará todos os caminhos não cíclicos entre dois nós. Este algoritmo deve ser muito rápido e dimensionado para gráficos grandes (a estrutura de dados do gráfico é esparsa, por isso usa apenas a quantidade de memória necessária).
Percebi que o gráfico que você especificou acima possui apenas uma aresta direcional (B,E).Isso foi um erro de digitação ou é realmente um gráfico direcionado?Esta solução funciona independentemente.Desculpe, não consegui fazer isso em C, sou um pouco fraco nessa área.Espero que você consiga traduzir este código Java sem muitos problemas.
Gráfico.java:
import java.util.HashMap;
import java.util.LinkedHashSet;
import java.util.LinkedList;
import java.util.Map;
import java.util.Set;
public class Graph {
private Map<String, LinkedHashSet<String>> map = new HashMap();
public void addEdge(String node1, String node2) {
LinkedHashSet<String> adjacent = map.get(node1);
if(adjacent==null) {
adjacent = new LinkedHashSet();
map.put(node1, adjacent);
}
adjacent.add(node2);
}
public void addTwoWayVertex(String node1, String node2) {
addEdge(node1, node2);
addEdge(node2, node1);
}
public boolean isConnected(String node1, String node2) {
Set adjacent = map.get(node1);
if(adjacent==null) {
return false;
}
return adjacent.contains(node2);
}
public LinkedList<String> adjacentNodes(String last) {
LinkedHashSet<String> adjacent = map.get(last);
if(adjacent==null) {
return new LinkedList();
}
return new LinkedList<String>(adjacent);
}
}
Pesquisa.java:
import java.util.LinkedList;
public class Search {
private static final String START = "B";
private static final String END = "E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "E"); // this is the only one-way connection
graph.addEdge("B", "F");
graph.addEdge("C", "A");
graph.addEdge("C", "E");
graph.addEdge("C", "F");
graph.addEdge("D", "B");
graph.addEdge("E", "C");
graph.addEdge("E", "F");
graph.addEdge("F", "B");
graph.addEdge("F", "C");
graph.addEdge("F", "E");
LinkedList<String> visited = new LinkedList();
visited.add(START);
new Search().depthFirst(graph, visited);
}
private void depthFirst(Graph graph, LinkedList<String> visited) {
LinkedList<String> nodes = graph.adjacentNodes(visited.getLast());
// examine adjacent nodes
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
if (node.equals(END)) {
visited.add(node);
printPath(visited);
visited.removeLast();
break;
}
}
for (String node : nodes) {
if (visited.contains(node) || node.equals(END)) {
continue;
}
visited.addLast(node);
depthFirst(graph, visited);
visited.removeLast();
}
}
private void printPath(LinkedList<String> visited) {
for (String node : visited) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
Saída do programa:
B E
B A C E
B A C F E
B F E
B F C E
Outras dicas
O Dicionário on-line de Algoritmos e Estruturas de Dados do Instituto Nacional de Padrões e Tecnologia (NIST) lista esse problema como "todos os caminhos simples" e recomenda um pesquisa em profundidade.CLRS fornece os algoritmos relevantes.
Uma técnica inteligente usando Redes de Petri é encontrada aqui
Aqui está o pseudocódigo que criei.Este não é um dialeto de pseudocódigo específico, mas deve ser simples o suficiente para seguir.
Alguém quer separar isso.
[p] é uma lista de vértices que representa o caminho atual.
[x] é uma lista de caminhos que atendem aos critérios
[s] é o vértice de origem
[d] é o vértice de destino
[c] é o vértice atual (argumento para a rotina PathFind)
Suponha que exista uma maneira eficiente de procurar os vértices adjacentes (linha 6).
1 PathList [p]
2 ListOfPathLists [x]
3 Vertex [s], [d]
4 PathFind ( Vertex [c] )
5 Add [c] to tail end of list [p]
6 For each Vertex [v] adjacent to [c]
7 If [v] is equal to [d] then
8 Save list [p] in [x]
9 Else If [v] is not in list [p]
10 PathFind([v])
11 Next For
12 Remove tail from [p]
13 Return
Uma vez que a implementação DFS não recursiva existente dada em esta resposta parece estar quebrado, deixe-me fornecer um que realmente funcione.
Escrevi isso em Python, porque acho que é bastante legível e organizado em detalhes de implementação (e porque tem a prática yield palavra-chave para implementação geradores), mas deve ser bastante fácil portar para outros idiomas.
# a generator function to find all simple paths between two nodes in a
# graph, represented as a dictionary that maps nodes to their neighbors
def find_simple_paths(graph, start, end):
visited = set()
visited.add(start)
nodestack = list()
indexstack = list()
current = start
i = 0
while True:
# get a list of the neighbors of the current node
neighbors = graph[current]
# find the next unvisited neighbor of this node, if any
while i < len(neighbors) and neighbors[i] in visited: i += 1
if i >= len(neighbors):
# we've reached the last neighbor of this node, backtrack
visited.remove(current)
if len(nodestack) < 1: break # can't backtrack, stop!
current = nodestack.pop()
i = indexstack.pop()
elif neighbors[i] == end:
# yay, we found the target node! let the caller process the path
yield nodestack + [current, end]
i += 1
else:
# push current node and index onto stacks, switch to neighbor
nodestack.append(current)
indexstack.append(i+1)
visited.add(neighbors[i])
current = neighbors[i]
i = 0
Este código mantém duas pilhas paralelas:um contendo os nós anteriores no caminho atual e outro contendo o índice vizinho atual para cada nó na pilha de nós (para que possamos retomar a iteração pelos vizinhos de um nó quando o retirarmos da pilha).Eu poderia ter usado igualmente uma única pilha de pares (nó, índice), mas imaginei que o método de duas pilhas seria mais legível e talvez mais fácil de implementar para usuários de outras linguagens.
Este código também usa um separado visited set, que sempre contém o nó atual e quaisquer nós na pilha, para permitir verificar com eficiência se um nó já faz parte do caminho atual.Se o seu idioma tiver uma estrutura de dados de "conjunto ordenado" que forneça operações push/pop eficientes do tipo pilha e consultas de associação eficientes, você pode usar isso para a pilha de nós e se livrar do separado visited definir.
Alternativamente, se você estiver usando uma classe/estrutura mutável personalizada para seus nós, você pode simplesmente armazenar um sinalizador booleano em cada nó para indicar se ele foi visitado como parte do caminho de pesquisa atual.É claro que esse método não permitirá que você execute duas pesquisas no mesmo gráfico em paralelo, caso por algum motivo você queira fazer isso.
Aqui está um código de teste que demonstra como funciona a função fornecida acima:
# test graph:
# ,---B---.
# A | D
# `---C---'
graph = {
"A": ("B", "C"),
"B": ("A", "C", "D"),
"C": ("A", "B", "D"),
"D": ("B", "C"),
}
# find paths from A to D
for path in find_simple_paths(graph, "A", "D"): print " -> ".join(path)
A execução deste código no gráfico de exemplo fornecido produz a seguinte saída:
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
Observe que, embora este gráfico de exemplo não seja direcionado (ou seja,todas as suas arestas vão em ambos os sentidos), o algoritmo também funciona para gráficos direcionados arbitrários.Por exemplo, remover o C -> B borda (removendo B da lista de vizinhos de C) produz a mesma saída, exceto para o terceiro caminho (A -> C -> B -> D), o que não é mais possível.
Sal. É fácil construir gráficos para os quais algoritmos de pesquisa simples como este (e os outros fornecidos neste tópico) apresentam desempenho muito ruim.
Por exemplo, considere a tarefa de encontrar todos os caminhos de A a B em um grafo não direcionado onde o nó inicial A tem dois vizinhos:o nó alvo B (que não tem outros vizinhos além de A) e um nó C que faz parte de um camarilha de nNós +1, assim:
graph = {
"A": ("B", "C"),
"B": ("A"),
"C": ("A", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"D": ("C", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"E": ("C", "D", "F", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"F": ("C", "D", "E", "G", "H", "I", "J", "K", "L", "M", "N", "O"),
"G": ("C", "D", "E", "F", "H", "I", "J", "K", "L", "M", "N", "O"),
"H": ("C", "D", "E", "F", "G", "I", "J", "K", "L", "M", "N", "O"),
"I": ("C", "D", "E", "F", "G", "H", "J", "K", "L", "M", "N", "O"),
"J": ("C", "D", "E", "F", "G", "H", "I", "K", "L", "M", "N", "O"),
"K": ("C", "D", "E", "F", "G", "H", "I", "J", "L", "M", "N", "O"),
"L": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "M", "N", "O"),
"M": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "N", "O"),
"N": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "O"),
"O": ("C", "D", "E", "F", "G", "H", "I", "J", "K", "L", "M", "N"),
}
É fácil ver que o único caminho entre A e B é o direto, mas um DFS ingênuo iniciado a partir do nó A desperdiçará O(n!) tempo explorando inutilmente caminhos dentro do grupo, mesmo que seja óbvio (para um humano) que nenhum desses caminhos pode levar a B.
Também se pode construir DAGs com propriedades semelhantes, por ex.fazendo com que o nó inicial A conecte o nó de destino B e dois outros nós C1 e C2, ambos os quais se conectam aos nós D1 e D2, ambos os quais se conectam a E1 e E2, e assim por diante.Para n camadas de nós dispostas desta forma, uma busca ingênua por todos os caminhos de A a B acabará desperdiçando O(2n) tempo examinando todos os possíveis becos sem saída antes de desistir.
Obviamente, adicionar uma aresta ao nó alvo B de um dos nós da clique (diferente de C) ou da última camada do DAG, seria crie um número exponencialmente grande de caminhos possíveis de A a B, e um algoritmo de busca puramente local não pode dizer com antecedência se encontrará tal aresta ou não.Assim, de certo modo, os pobres sensibilidade de saída dessas pesquisas ingênuas se deve à falta de conhecimento da estrutura global do gráfico.
Embora existam vários métodos de pré-processamento (como eliminação iterativa de nós folha, busca por separadores de vértices de nó único, etc.) que poderiam ser usados para evitar alguns desses "becos sem saída em tempo exponencial", não conheço nenhum método geral truque de pré-processamento que poderia eliminá-los em todos casos.Uma solução geral seria verificar em cada etapa da pesquisa se o nó alvo ainda é alcançável (usando uma subpesquisa) e retroceder antecipadamente se não estiver - mas, infelizmente, isso retardaria significativamente a pesquisa (na pior das hipóteses). , proporcionalmente ao tamanho do gráfico) para muitos gráficos que não contêm esses becos sem saída patológicos.
Aqui está uma versão recursiva logicamente mais bonita em comparação com o segundo andar.
public class Search {
private static final String START = "B";
private static final String END = "E";
public static void main(String[] args) {
// this graph is directional
Graph graph = new Graph();
graph.addEdge("A", "B");
graph.addEdge("A", "C");
graph.addEdge("B", "A");
graph.addEdge("B", "D");
graph.addEdge("B", "E"); // this is the only one-way connection
graph.addEdge("B", "F");
graph.addEdge("C", "A");
graph.addEdge("C", "E");
graph.addEdge("C", "F");
graph.addEdge("D", "B");
graph.addEdge("E", "C");
graph.addEdge("E", "F");
graph.addEdge("F", "B");
graph.addEdge("F", "C");
graph.addEdge("F", "E");
List<ArrayList<String>> paths = new ArrayList<ArrayList<String>>();
String currentNode = START;
List<String> visited = new ArrayList<String>();
visited.add(START);
new Search().findAllPaths(graph, seen, paths, currentNode);
for(ArrayList<String> path : paths){
for (String node : path) {
System.out.print(node);
System.out.print(" ");
}
System.out.println();
}
}
private void findAllPaths(Graph graph, List<String> visited, List<ArrayList<String>> paths, String currentNode) {
if (currentNode.equals(END)) {
paths.add(new ArrayList(Arrays.asList(visited.toArray())));
return;
}
else {
LinkedList<String> nodes = graph.adjacentNodes(currentNode);
for (String node : nodes) {
if (visited.contains(node)) {
continue;
}
List<String> temp = new ArrayList<String>();
temp.addAll(visited);
temp.add(node);
findAllPaths(graph, temp, paths, node);
}
}
}
}
Saída do programa
B A C E
B A C F E
B E
B F C E
B F E
Solução em código C.É baseado em DFS que usa memória mínima.
#include <stdio.h>
#include <stdbool.h>
#define maxN 20
struct nodeLink
{
char node1;
char node2;
};
struct stack
{
int sp;
char node[maxN];
};
void initStk(stk)
struct stack *stk;
{
int i;
for (i = 0; i < maxN; i++)
stk->node[i] = ' ';
stk->sp = -1;
}
void pushIn(stk, node)
struct stack *stk;
char node;
{
stk->sp++;
stk->node[stk->sp] = node;
}
void popOutAll(stk)
struct stack *stk;
{
char node;
int i, stkN = stk->sp;
for (i = 0; i <= stkN; i++)
{
node = stk->node[i];
if (i == 0)
printf("src node : %c", node);
else if (i == stkN)
printf(" => %c : dst node.\n", node);
else
printf(" => %c ", node);
}
}
/* Test whether the node already exists in the stack */
bool InStack(stk, InterN)
struct stack *stk;
char InterN;
{
int i, stkN = stk->sp; /* 0-based */
bool rtn = false;
for (i = 0; i <= stkN; i++)
{
if (stk->node[i] == InterN)
{
rtn = true;
break;
}
}
return rtn;
}
char otherNode(targetNode, lnkNode)
char targetNode;
struct nodeLink *lnkNode;
{
return (lnkNode->node1 == targetNode) ? lnkNode->node2 : lnkNode->node1;
}
int entries = 8;
struct nodeLink topo[maxN] =
{
{'b', 'a'},
{'b', 'e'},
{'b', 'd'},
{'f', 'b'},
{'a', 'c'},
{'c', 'f'},
{'c', 'e'},
{'f', 'e'},
};
char srcNode = 'b', dstN = 'e';
int reachTime;
void InterNode(interN, stk)
char interN;
struct stack *stk;
{
char otherInterN;
int i, numInterN = 0;
static int entryTime = 0;
entryTime++;
for (i = 0; i < entries; i++)
{
if (topo[i].node1 != interN && topo[i].node2 != interN)
{
continue;
}
otherInterN = otherNode(interN, &topo[i]);
numInterN++;
if (otherInterN == stk->node[stk->sp - 1])
{
continue;
}
/* Loop avoidance: abandon the route */
if (InStack(stk, otherInterN) == true)
{
continue;
}
pushIn(stk, otherInterN);
if (otherInterN == dstN)
{
popOutAll(stk);
reachTime++;
stk->sp --; /* back trace one node */
continue;
}
else
InterNode(otherInterN, stk);
}
stk->sp --;
}
int main()
{
struct stack stk;
initStk(&stk);
pushIn(&stk, srcNode);
reachTime = 0;
InterNode(srcNode, &stk);
printf("\nNumber of all possible and unique routes = %d\n", reachTime);
}
Resolvi um problema semelhante a este recentemente, em vez de todas as soluções só estava interessado na mais curta.
Usei uma pesquisa iterativa 'amplitude primeiro' que usou uma fila de status', cada uma contendo um registro contendo um ponto atual no gráfico e o caminho percorrido para chegar lá.
você começa com um único registro na fila, que possui o nó inicial e um caminho vazio.
Cada iteração através do código tira o item do topo da lista e verifica se é uma solução (o nó chegado é o que você deseja, se for, terminamos), caso contrário, ele constrói um novo item da fila com os nós que se conectam ao nó atual e caminhos alterados que são baseados no caminho do nó anterior, com o novo salto anexado no final.
Agora, você poderia usar algo semelhante, mas quando encontrar uma solução, em vez de parar, adicione essa solução à sua ‘lista de encontrados’ e continue.
Você precisa acompanhar uma lista de nós visitados, para nunca voltar atrás, caso contrário terá um loop infinito.
se você quiser um pouco mais de pseudocódigo poste um comentário ou algo assim, e eu irei elaborar.
Acho que você deveria descrever seu verdadeiro problema por trás disso.Digo isso porque você pede algo eficiente em termos de tempo, mas a resposta definida para o problema parece crescer exponencialmente!
Portanto, eu não esperaria um algoritmo melhor do que algo exponencial.
Eu voltaria e passaria por todo o gráfico.Para evitar ciclos, salve todos os nós visitados ao longo do caminho.Quando você voltar, desmarque o nó.
Usando recursão:
static bool[] visited;//all false
Stack<int> currentway; initialize empty
function findnodes(int nextnode)
{
if (nextnode==destnode)
{
print currentway
return;
}
visited[nextnode]=true;
Push nextnode to the end of currentway.
for each node n accesible from nextnode:
findnodes(n);
visited[nextnode]=false;
pop from currenteay
}
Ou isso está errado?
editar:Ah, e esqueci:Você deve eliminar as chamadas recursivas utilizando essa pilha de nós
O princípio básico é que você não precisa se preocupar com gráficos. Este é um problema padrão conhecido como problema de conectividade dinâmica.Existem os seguintes tipos de métodos a partir dos quais você pode fazer com que os nós estejam conectados ou não:
- Busca rápida
- União Rápida
- Algoritmo aprimorado (combinação de ambos)
Aqui está o código C que tentei com complexidade de tempo mínima O (log * n). Isso significa que para uma lista de 65536 arestas, são necessárias 4 pesquisas e para 2 ^ 65536, são necessárias 5 pesquisas.Estou compartilhando minha implementação do algoritmo: Curso de Algoritmo da Universidade de Princeton
DICA:Você pode encontrar a solução Java no link compartilhado acima com explicações adequadas.
/* Checking Connection Between Two Edges */
#include<stdio.h>
#include<stdlib.h>
#define MAX 100
/*
Data structure used
vertex[] - used to Store The vertices
size - No. of vertices
sz[] - size of child's
*/
/*Function Declaration */
void initalize(int *vertex, int *sz, int size);
int root(int *vertex, int i);
void add(int *vertex, int *sz, int p, int q);
int connected(int *vertex, int p, int q);
int main() //Main Function
{
char filename[50], ch, ch1[MAX];
int temp = 0, *vertex, first = 0, node1, node2, size = 0, *sz;
FILE *fp;
printf("Enter the filename - "); //Accept File Name
scanf("%s", filename);
fp = fopen(filename, "r");
if (fp == NULL)
{
printf("File does not exist");
exit(1);
}
while (1)
{
if (first == 0) //getting no. of vertices
{
ch = getc(fp);
if (temp == 0)
{
fseek(fp, -1, 1);
fscanf(fp, "%s", &ch1);
fseek(fp, 1, 1);
temp = 1;
}
if (isdigit(ch))
{
size = atoi(ch1);
vertex = (int*) malloc(size * sizeof(int)); //dynamically allocate size
sz = (int*) malloc(size * sizeof(int));
initalize(vertex, sz, size); //initialization of vertex[] and sz[]
}
if (ch == '\n')
{
first = 1;
temp = 0;
}
}
else
{
ch = fgetc(fp);
if (isdigit(ch))
temp = temp * 10 + (ch - 48); //calculating value from ch
else
{
/* Validating the file */
if (ch != ',' && ch != '\n' && ch != EOF)
{
printf("\n\nUnkwown Character Detected.. Exiting..!");
exit(1);
}
if (ch == ',')
node1 = temp;
else
{
node2 = temp;
printf("\n\n%d\t%d", node1, node2);
if (node1 > node2)
{
temp = node1;
node1 = node2;
node2 = temp;
}
/* Adding the input nodes */
if (!connected(vertex, node1, node2))
add(vertex, sz, node1, node2);
}
temp = 0;
}
if (ch == EOF)
{
fclose(fp);
break;
}
}
}
do
{
printf("\n\n==== check if connected ===");
printf("\nEnter First Vertex:");
scanf("%d", &node1);
printf("\nEnter Second Vertex:");
scanf("%d", &node2);
/* Validating The Input */
if( node1 > size || node2 > size )
{
printf("\n\n Invalid Node Value..");
break;
}
/* Checking the connectivity of nodes */
if (connected(vertex, node1, node2))
printf("Vertex %d and %d are Connected..!", node1, node2);
else
printf("Vertex %d and %d are Not Connected..!", node1, node2);
printf("\n 0/1: ");
scanf("%d", &temp);
} while (temp != 0);
free((void*) vertex);
free((void*) sz);
return 0;
}
void initalize(int *vertex, int *sz, int size) //Initialization of graph
{
int i;
for (i = 0; i < size; i++)
{
vertex[i] = i;
sz[i] = 0;
}
}
int root(int *vertex, int i) //obtaining the root
{
while (i != vertex[i])
{
vertex[i] = vertex[vertex[i]];
i = vertex[i];
}
return i;
}
/* Time Complexity for Add --> logn */
void add(int *vertex, int *sz, int p, int q) //Adding of node
{
int i, j;
i = root(vertex, p);
j = root(vertex, q);
/* Adding small subtree in large subtree */
if (sz[i] < sz[j])
{
vertex[i] = j;
sz[j] += sz[i];
}
else
{
vertex[j] = i;
sz[i] += sz[j];
}
}
/* Time Complexity for Search -->lg* n */
int connected(int *vertex, int p, int q) //Checking of connectivity of nodes
{
/* Checking if root is same */
if (root(vertex, p) == root(vertex, q))
return 1;
return 0;
}
Isso pode ser tarde, mas aqui está a mesma versão C# do algoritmo DFS em Java de Casey para percorrer todos os caminhos entre dois nós usando uma pilha.A legibilidade é melhor com recursividade, como sempre.
void DepthFirstIterative(T start, T endNode)
{
var visited = new LinkedList<T>();
var stack = new Stack<T>();
stack.Push(start);
while (stack.Count != 0)
{
var current = stack.Pop();
if (visited.Contains(current))
continue;
visited.AddLast(current);
var neighbours = AdjacentNodes(current);
foreach (var neighbour in neighbours)
{
if (visited.Contains(neighbour))
continue;
if (neighbour.Equals(endNode))
{
visited.AddLast(neighbour);
printPath(visited));
visited.RemoveLast();
break;
}
}
bool isPushed = false;
foreach (var neighbour in neighbours.Reverse())
{
if (neighbour.Equals(endNode) || visited.Contains(neighbour) || stack.Contains(neighbour))
{
continue;
}
isPushed = true;
stack.Push(neighbour);
}
if (!isPushed)
visited.RemoveLast();
}
}
This is a sample graph to test:
// Sample graph. Numbers are edge ids
// 1 3
// A --- B --- C ----
// | | 2 |
// | 4 ----- D |
// ------------------
encontrar_caminhos[s, t, d, k]
Esta pergunta é antiga e já foi respondida.No entanto, nenhum mostra talvez um algoritmo mais flexível para realizar a mesma coisa.Então vou jogar meu chapéu no ringue.
Eu pessoalmente encontro 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 a serem encontrados
Usando a forma de infinito da sua linguagem de programação para d e k lhe dará todos os caminhos§.
§ obviamente, se você estiver usando um gráfico direcionado e quiser que todos não direcionado caminhos entre s e t você terá que executar isso nos dois sentidos:
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Função auxiliar
Eu pessoalmente gosto de recursão, embora às vezes possa ser difícil, de qualquer forma, primeiro vamos definir nossa função 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 resolvido, a função 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 observar algumas coisas:
- o pseudocódigo acima é um mash-up de linguagens - mas mais parecido com python (já que eu estava apenas codificando nele).Um copiar e colar estrito não funcionará.
[]é uma lista não inicializada, substitua-a pelo equivalente da linguagem de programação de sua escolhapaths_foundé passado referência.É claro que a função de recursão não retorna nada.Lide com isso adequadamente.- aqui
graphestá assumindo alguma forma dehashedestrutura.Existem inúmeras maneiras de implementar um gráfico.De qualquer jeito,graph[vertex]fornece uma lista de vértices adjacentes em um dirigido gráfico - ajuste de acordo. - isso pressupõe que você tenha pré-processado para remover "fivelas" (auto-loops), ciclos e múltiplas arestas
Aqui está um pensamento que veio da minha cabeça:
- Encontre uma conexão.(A pesquisa em profundidade é provavelmente um bom algoritmo para isso, já que o comprimento do caminho não importa.)
- Desative o último segmento.
- Tente encontrar outra conexão do último nó antes da conexão desabilitada anteriormente.
- Vá para 2 até que não haja mais conexões.
Pelo que posso dizer, as soluções dadas por Ryan Fox (58343, cristão (58444), e você mesmo (58461) são tão bons quanto possível.Não acredito que a travessia em largura ajude neste caso, pois você não obterá todos os caminhos.Por exemplo, com bordas (A,B), (A,C), (B,C), (B,D) e (C,D) você obterá caminhos ABD e ACD, mas não ABCD.
Encontrei uma maneira de enumerar todos os caminhos, incluindo os infinitos que contêm loops.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Encontrando caminhos e ciclos atômicos
Definition
O que queremos fazer é encontrar todos os caminhos possíveis que vão do ponto A ao ponto B.Como há ciclos envolvidos, você não pode simplesmente passar por eles e enumerá-los todos.Em vez disso, você terá que encontrar um caminho atômico que não faça loop e os menores ciclos possíveis (você não quer que seu ciclo se repita).
A primeira definição que tomei de caminho atômico é um caminho que não passa duas vezes pelo mesmo nó.Porém, descobri que não estava aproveitando todas as possibilidades.Depois de alguma reflexão, descobri que os nós não são importantes, mas as arestas são!Portanto, um caminho atômico é um caminho que não passa duas vezes pela mesma aresta.
Esta definição é útil, mas também funciona para ciclos:um ciclo atômico do ponto A é um caminho atômico que vai do ponto A e termina no ponto A.
Implementação
Atomic Paths A -> B
Para obter todo o caminho a partir do ponto A, vamos percorrer o gráfico recursivamente a partir do ponto A.Ao passar por um filho, vamos fazer um link filho -> pai para saber todas as arestas que já cruzamos.Antes de irmos para aquele filho, devemos percorrer aquela lista vinculada e ter certeza de que a aresta especificada ainda não foi percorrida.
Quando chegarmos ao ponto de destino, podemos armazenar o caminho que encontramos.
Freeing the list
Ocorre um problema quando você deseja liberar a lista vinculada.É basicamente uma árvore encadeada na ordem inversa.Uma solução seria vincular duas vezes essa lista e quando todos os caminhos atômicos fossem encontrados, liberar a árvore do ponto inicial.
Mas uma solução inteligente é usar uma contagem de referência (inspirada na Coleta de Lixo).Cada vez que você adiciona um link a um pai, você adiciona um à sua contagem de referências.Então, ao chegar ao final de um caminho, você retrocede e se liberta enquanto a contagem de referências é igual a 1.Se for maior, basta remover um e parar.
Atomic Cycle A
Procurar o ciclo atômico de A é o mesmo que procurar o caminho atômico de A até A.No entanto, existem várias otimizações que podemos fazer.Primeiro, quando chegarmos ao ponto de destino, queremos salvar o caminho apenas se a soma dos custos das arestas for negativa:queremos apenas passar por ciclos absorventes.
Como você viu anteriormente, todo o gráfico está sendo percorrido ao procurar um caminho atômico.Em vez disso, podemos limitar a área de busca ao componente fortemente conexo contendo A.Encontrar esses componentes requer uma simples travessia do gráfico com o algoritmo de Tarjan.
Combinando Caminhos e Ciclos Atômicos
Neste ponto, temos todos os caminhos atômicos que vão de A a B e todos os ciclos atômicos de cada nó, cabendo a nós organizar tudo para obter o caminho mais curto.A partir de agora estudaremos como encontrar a melhor combinação de ciclos atômicos em uma trajetória atômica.
Conforme habilmente descrito por alguns dos outros postadores, o problema em poucas palavras é o de usar um algoritmo de busca em profundidade para pesquisar recursivamente no gráfico todas as combinações de caminhos entre os nós finais em comunicação.
O próprio algoritmo começa com o nó inicial que você fornece, examina todos os seus links de saída e progride expandindo o primeiro nó filho da árvore de pesquisa que aparece, pesquisando cada vez mais profundamente até que um nó alvo seja encontrado ou até encontrar um nó. que não tem filhos.
A busca então retrocede, retornando ao nó mais recente que ainda não terminou de explorar.
EU blogado sobre esse tópico recentemente, postando um exemplo de implementação de C++ no processo.
Somando-se à resposta de Casey Watson, aqui está outra implementação Java.Inicializando o nó visitado com o nó inicial.
private void getPaths(Graph graph, LinkedList<String> visitedNodes) {
LinkedList<String> adjacent = graph.getAdjacent(visitedNodes.getLast());
for(String node : adjacent){
if(visitedNodes.contains(node)){
continue;
}
if(node.equals(END)){
visitedNodes.add(node);
printPath(visitedNodes);
visitedNodes.removeLast();
}
visitedNodes.add(node);
getPaths(graph, visitedNodes);
visitedNodes.removeLast();
}
}
