Grafico Algoritmo Per Trovare Tutte Le Connessioni Tra I Due Vertici Arbitrario
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianDomanda
Sto cercando di determinare il momento migliore algoritmo efficiente per realizzare le attività descritte di seguito.
Ho una serie di record.Per questo insieme di record ho la connessione dati, che indica le coppie di record da questo set di connettersi l'uno all'altro.Questo rappresenta sostanzialmente un grafico undirected, con il record di essere i vertici e i dati di collegamento i bordi.
Tutti i record nel set sono le informazioni di connessione (es.nessun record orfani sono presenti;ogni record nel set si connette a uno o più record nel set).
Voglio scegliere le due record dal set ed essere in grado di mostrare tutte semplici percorsi tra i rapporti scelti."Più semplice i percorsi di" intendo i percorsi che non hanno ripetuto il record del percorso (cioèfiniti i percorsi).
Nota:I due rapporti scelti saranno sempre diversi (es.di inizio e di fine del vertice non sarà mai più la stessa;non cicli).
Per esempio:
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 ho scelto la B come il mio record di partenza e la e come il mio record del fine, vorrei trovare dei semplici sentieri che attraversano il record di connessioni che collega record B per registrare 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
Questo è un esempio, in pratica mi hanno set contenenti centinaia di migliaia di record.
Soluzione
Sembra che questo può essere realizzato con una ricerca approfondita del grafico. La ricerca prima di profondità trovare tutti i non-ciclici percorsi tra due nodi. Questo algoritmo deve essere molto veloce e scala per i grafici di grandi dimensioni (La struttura di dati del grafico è sparsa in modo che utilizzi solo come quantità di memoria necessaria per).
Ho notato che il grafico che hai specificato sopra è solo un bordo che è direzionale (B,E).Questo era un errore di battitura o è veramente un grafo?Questa soluzione funziona a prescindere.Scusa se sono stata in grado di farlo in C, io sono un po ' debole in quella zona.Mi aspetto che si sarà in grado di tradurre il codice Java senza troppi problemi però.
Graph.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);
}
}
Search.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();
}
}
L'Output Del Programma:
B E
B A C E
B A C F E
B F E
B F C E
Altri suggerimenti
Il National Institute of Standards and Technology (NIST) il Dizionario online di Algoritmi e Strutture di Dati, elenchi di questo problema "tutti semplici percorsi" e raccomanda un depth-first search.CLR fornisce il relativo algoritmi.
Una sapiente tecnica mediante Reti di Petri si trova qui
Qui è lo pseudocodice mi è venuta.Questo non è un qualsiasi particolare pseudocodice dialetto, ma dovrebbe essere abbastanza semplice da seguire.
Nessuno vuole prendere questa a parte.
[p] è una lista di vertici che rappresentano il percorso corrente.
[x] è un elenco di percorsi in cui soddisfano i criteri
[s] è la fonte di vertice
[d] è la destinazione vertice
[c] è la corrente di vertice (argomento per il PathFind di routine)
Supponiamo che vi sia un modo efficace per cercare i vertici adiacenti (linea 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
Dal momento che l'esistente non ricorsiva implementazione DFS dato in questa risposta sembra essere rotto, mi permetta di fornire una che funziona davvero.
Ho scritto in Python, perché la trovo abbastanza leggibile e ordinato da dettagli di implementazione (e perché ha il pratico yield parola chiave per l'implementazione di generatori), ma dovrebbe essere abbastanza facile porta ad altre lingue.
# 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
Questo codice permette di mantenere due stack parallela:uno contenente il precedente nodi nel percorso corrente, e uno contenente la corrente vicino indice per ogni nodo nel stack (in modo che possiamo riprendere a scorrere i vicini di un nodo quando si pop off stack).Ho potuto ugualmente utilizzato una sola pila di (nodo di indice), coppie, ma ho pensato che i due stack metodo sarebbe più leggibile, e forse di più facile attuazione per gli utenti di altre lingue.
Questo codice utilizza anche separata visited set, che contiene sempre il nodo corrente e tutti i nodi sullo stack, per farmi controllare in modo efficiente se un nodo è già parte del percorso corrente.Se la tua lingua succede ad avere un "insieme ordinato" struttura di dati che fornisce sia efficiente stack-come push/pop operazioni e efficiente query di appartenenza, è possibile utilizzare che per il nodo di stack e di sbarazzarsi di separato visited set.
In alternativa, se si sta utilizzando un custom mutevole classe / struttura per i nodi, si può semplicemente memorizzare un flag booleano che in ogni nodo per indicare se è stato visitato come parte del percorso di ricerca corrente.Naturalmente, questo metodo non permette di eseguire due ricerche sullo stesso grafico in parallelo, dovrebbe per qualche motivo non vogliono farlo.
Ecco qualche codice di prova per dimostrare come la funzione di cui sopra funziona:
# 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)
L'esecuzione di questo codice sul grafico di esempio produce il seguente output:
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
Nota che, mentre in questo esempio il grafico è la non diretta (es.tutti i suoi bordi andare in entrambi i modi), l'algoritmo funziona anche per arbitrario diretto grafici.Per esempio, la rimozione di C -> B bordo (rimuovendo B dal prossimo elenco di C) si ottiene lo stesso risultato, salvo che per il terzo percorso (A -> C -> B -> D), che non è più possibile.
Ps. È facile costruire grafici di semplici algoritmi di ricerca come questo (e gli altri dato in questo thread) eseguire molto male.
Per esempio, si consideri il compito di trovare tutti i percorsi da a a B in un grafico undirected dove la base di partenza il nodo ha due vicini di casa:il nodo di destinazione B (che non ha altri vicini di casa di Una) e un nodo C, che è parte di un clique di n+1 nodi, come questo:
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"),
}
È facile vedere che l'unico percorso tra A e B è quella diretta, ma un ingenuo DFS iniziato da nodo rifiuti O(n!) tempo inutilmente esplorare percorsi all'interno del gruppo, anche se è evidente (per gli umani) che nessuno di questi percorsi può eventualmente portare alla B.
Si può anche costruire DAGs con proprietà simili, ad es.avendo il nodo di partenza A collegare il nodo di destinazione e B e di due altri nodi C1 e C2, sia che la connessione ai nodi D1 e D2, sia che la connessione a E1 ed e2, e così via.Per n i livelli di nodi disposti come questo, un ingenuo cercare tutti i percorsi da a a B si finisce per sprecare O(2n) tempo di esaminare tutte le possibili finisce morto prima di rinunciare.
Naturalmente, l'aggiunta di un bordo per il nodo di destinazione B da uno dei nodi della cricca (diversa da C), o da un ultimo strato di DAG, sarebbe creare un esponenziale gran numero di possibili percorsi da a a B, e puramente locali algoritmo di ricerca può dire in anticipo se troveranno un bordo o meno.Così, in un certo senso, i poveri sensibilità di uscita di queste ingenue ricerca è a causa della loro mancanza di consapevolezza della struttura globale del grafico.
Mentre ci sono diversi metodi di pre-elaborazione (ad esempio, in modo iterativo, eliminando i nodi foglia, la ricerca di un singolo nodo vertice separatori, etc.) che potrebbe essere utilizzato per evitare alcuni di questi "esponenziale tempo finisce morto", non so di qualsiasi generale di pre-elaborazione trucco che possa eliminare nel tutti casi.Una soluzione sarebbe quella di controllare in ogni fase della ricerca se il nodo di destinazione è ancora raggiungibile (utilizzando un sub-ricerca), e tornate presto se non lo è — ma, ahimè, che sarebbe rallentare in modo significativo la ricerca (nel peggiore dei casi, proporzionalmente alla dimensione del grafico) per molti grafici che non contengono tali patologico finisce morto.
Qui è logicamente meglio guardare versione ricorsiva rispetto al piano secondo.
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);
}
}
}
}
L'Output Del Programma
B A C E
B A C F E
B E
B F C E
B F E
Soluzione in C codice.Esso è basato su DFS che usa un minimo di memoria.
#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);
}
Io ho risolto un problema simile a questo di recente, invece di tutte le soluzioni ero interessato solo più breve.
Ho usato un 'ampiezza primo' iterativo di ricerca che ha utilizzato una coda di stato' ciascuna delle quali ha tenuto un record contenente un punto sul grafico e la strada per arrivarci.
si inizia con un singolo record in coda, che è il nodo di partenza e un vuoto di percorso.
Ogni iterazione il codice assume l'articolo fuori la testa della lista, e controlla per vedere se si tratta di una soluzione (il nodo è arrivato è quello che si desidera, se lo è, siamo di fatto), in caso contrario, si costruisce un nuovo elemento in coda con i nodi di connessione al nodo corrente, e modificato i percorsi in base al percorso del nodo precedente, con il nuovo salto in allegato alla fine.
Ora, è possibile utilizzare qualcosa di simile, ma quando si trova una soluzione, invece di fermarsi, aggiungere che la soluzione al tuo 'trovare la lista' e continua.
È necessario tenere traccia di un visitata elenco di nodi, in modo che non backtrack su di te, altrimenti hai un ciclo infinito.
se si vuole un po ' di più pseudocodice postare un commento o qualcosa del genere, e mi dilungherò.
Penso che si dovrebbe descrivere il vero problema alla base di questo.Dico questo perché chiedi qualcosa di efficiente, ma la risposta impostato il problema sembra crescere in modo esponenziale!
Quindi non mi aspetto di un algoritmo migliore di qualcosa esponenziale.
Mi piacerebbe fare passi indietro e passare attraverso l'intero grafico.Per evitare cicli di salvare tutti i nodi visitati lungo la strada.Quando si torna, si deseleziona il nodo.
Utilizzando la ricorsione:
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
}
O è sbagliato?
edit:Oh, e ho dimenticato:Si dovrebbe eliminare le chiamate ricorsive utilizzando il nodo stack
Il principio di base è che non è necessario preoccuparsi di grafici.Questo è un problema standard, noto come Dynamic problema di connettività.Esistono i seguenti tipi di metodi da cui è possibile raggiungere i nodi sono collegati o meno:
- Ricerca Rapida
- Rapido Unione
- Migliorato l'Algoritmo (Combinazione di entrambi)
Qui è Il Codice C Che ho provato con un minimo di complessità O(log n), il Che significa per 65536 elenco dei bordi, richiede 4 ricerca e per la 2^65536, richiede 5 ricerca.Sto condividendo la mia implementazione dell'algoritmo: Algoritmo di Corso presso l'università di Princeton
SUGGERIMENTO:È possibile trovare la soluzione Java dal link condivisi sopra con spiegazioni adeguate.
/* 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;
}
Questo può essere in ritardo, ma ecco la stessa versione C# di DFS algoritmo in Java da Casey attraversare per tutti i percorsi tra due nodi utilizzando una pila.La leggibilità è meglio ricorsive come 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 |
// ------------------
find_paths[s, t, d, k]
Questa domanda è vecchia e già risposto.Tuttavia, nessuno mostra forse un modo più flessibile algoritmo per realizzare la stessa cosa.Quindi dovrò buttare il mio cappello sul ring.
Io personalmente trovo che un algoritmo di forma find_paths[s, t, d, k] utile, dove:
- s è il nodo di partenza
- t è il nodo di destinazione
- d è la profondità massima alla ricerca
- k è il numero di percorsi per trovare
Utilizzando il linguaggio di programmazione è la forma dell'infinito d e k vi darà i percorsi§.
§ ovviamente se si utilizza un grafo orientato e si desidera che tutti la non diretta percorsi tra s e t sarà necessario eseguire questo in due modi:
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Funzione Di Supporto
Personalmente mi piace la ricorsione, anche se può difficile alcune volte, comunque in primo luogo permette di definire la nostra funzione di supporto:
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()
Funzione Principale
Con quella di mezzo, la funzione principale è banale:
def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found)
In primo luogo, lascia che si noti qualche cosa:
- il pseudo-codice è un mash-up di lingue - ma più fortemente simile a python (dato che ero appena codificazione in esso).Una stretta di copia-incolla non funziona.
[]è un non inizializzato lista, sostituire questo con l'equivalente per il linguaggio di programmazione a sceltapaths_foundè passato da riferimento.È chiaro che la ricorsione funzione non restituisce nulla.Gestire in modo appropriato in questo.- qui
graphsta assumendo una qualche forma dihashedstruttura.Ci sono una miriade di modi per implementare un grafico.In ogni modo,graph[vertex]si ottiene una lista dei vertici adiacenti in un diretto grafico - regolare di conseguenza. - questo presuppone che si sono pre-trattati per rimuovere "fibbie" (self-loop), cicli e multi-bordi
Ecco un pensiero fuori della parte superiore della mia testa:
- Trovare una connessione.(Depth-first search è probabilmente un buon algoritmo per questo, dal momento che la lunghezza del percorso non importa).
- Disabilitare l'ultimo segmento.
- Prova a trovare un'altra connessione, l'ultimo nodo prima di precedenza connessione disattivata.
- Goto 2 fino a quando non ci sono più connessioni.
Per quanto posso dire le soluzioni date da Ryan Fox (58343, Christian (58444) e te (58461) sono circa buono come si arriva.Non credo che breadth-first attraversamento aiuta in questo caso, come non sarà possibile ottenere tutti i percorsi.Per esempio, con bordi (A,B), (A,C), (B,C), (B,D) e (C,D) vi saranno mostrati percorsi ABD e ACD, ma non ABCD.
Ho trovato un modo per enumerare tutti i percorsi, compresi quelli infiniti contenenti loop.
http://blog.vjeux.com/2009/project/project-shortest-path.html
La Ricerca Atomica Percorsi & Cicli
Definition
Quello che vogliamo fare è di trovare tutti i possibili percorsi di andare dal punto a al punto B.Dato che ci sono cicli coinvolti, non si può semplicemente passare attraverso e enumerarli tutti.Invece, si dovrà trovare atomica percorso che non loop e il più piccolo possibile cicli (non vuoi che il tuo ciclo di ripetere la stessa).
La prima definizione che ho preso un atomic percorso è un percorso che non passano attraverso lo stesso nodo due volte.Tuttavia, ho scoperto che non stava prendendo tutte le possibilità.Dopo qualche riflessione, ho capito che i nodi non sono importanti, ma i bordi sono!In modo atomico percorso è un percorso che non passano attraverso lo stesso bordo due volte.
Questa definizione è utile, funziona anche per cicli:atomico ciclo di punto di Una atomica percorso che va dal punto A fino al punto A.
Attuazione
Atomic Paths A -> B
Per ottenere tutto il percorso a partire da Un punto di vista, stiamo per attraversare il grafico in modo ricorsivo dal punto A.Mentre si passa attraverso un bambino, stiamo andando a fare un link bambino -> padre per conoscere tutti i bordi abbiamo già attraversato.Prima andiamo a quel bambino, si deve attraversare quella legata elenco e assicurarsi che il specificato edge non è stato già camminato attraverso.
Quando si arriva al punto di destinazione, siamo in grado di memorizzare il percorso che abbiamo trovato.
Freeing the list
Un problema si verifica quando si desidera liberare la lista collegata.Si tratta fondamentalmente di un albero incatenato in ordine inverso.Una soluzione potrebbe essere di fare doppio link che la lista e quando tutti atomica percorsi stati trovati gratuito, la struttura dal punto di partenza.
Ma una soluzione intelligente è quello di utilizzare un conteggio di riferimento (ispirato dalla Raccolta dei rifiuti).Ogni volta che si aggiunge un collegamento a un genitore si aggiunge uno per il conteggio dei riferimenti.Poi, quando si arriva alla fine di un percorso, si va indietro e gratuito, mentre il conteggio di riferimento pari a 1.Se è più alto, è sufficiente rimuovere uno e stop.
Atomic Cycle A
Cercando atomica ciclo è lo stesso cercando atomica percorso da a a A.Tuttavia ci sono diverse ottimizzazioni si può fare.In primo luogo, quando si arriva al punto di destinazione, vogliamo salvare il percorso solo se la somma dei bordi costo è negativo:vogliamo solo passare attraverso cicli di assorbimento.
Come si è visto in precedenza, il grafico viene attraversato quando alla ricerca di un atomica percorso.Invece, siamo in grado di limitare l'area di ricerca per la forte componente collegato contenente A.La ricerca di questi componenti richiede una semplice traslazione del grafico con Tarjan dell'algoritmo.
Combinando Atomica Percorsi e Cicli
A questo punto, abbiamo tutti i atomica sentieri che va da a a B e a tutti i atomica cicli di ogni nodo, che hanno lasciato a noi per organizzare il tutto per ottenere il percorso più breve.Ora stiamo andando a studiare il modo di trovare la migliore combinazione di atomic cicli atomica percorso.
Come abilmente descritto da alcuni degli altri manifesti, il problema in sintesi è quella di utilizzare una ricerca prima di profondità algoritmo ricorsivo di ricerca grafico per tutte le combinazioni di percorsi tra la comunicazione di fine dei nodi.
L'algoritmo inizia con il nodo di partenza si dà, esamina tutti i suoi link in uscita e continua in espandendo il primo nodo figlio di ricerca albero che appare, cercando progressivamente più profondo e più profondo fino a un nodo di destinazione è trovato, o fino a quando non incontra un nodo che non ha figli.
La ricerca poi ritorna, tornando per l'ultima nodo che non ha ancora finito di esplorare.
Io bloggato su questo argomento molto abbastanza recentemente, la pubblicazione di un esempio di implementazione di C++ nel processo.
L'aggiunta di Casey Watson risposta, qui è un'altra implementazione Java,.Inizializzazione visitato il nodo con il nodo di partenza.
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();
}
}
