Algoritmo gráfico para encontrar todas las conexiones entre dos vértices arbitrarios
https://stackoverflow.com/questions/58306
-
09-06-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Estoy tratando de determinar el algoritmo más eficiente en el tiempo para realizar la tarea que se describe a continuación.
Tengo un conjunto de registros.Para este conjunto de registros tengo datos de conexión que indican cómo se conectan entre sí los pares de registros de este conjunto.Básicamente, esto representa un gráfico no dirigido, donde los registros son los vértices y los datos de conexión son los bordes.
Todos los registros del conjunto tienen información de conexión (es decir,no hay registros huérfanos;cada registro del conjunto se conecta a uno o más registros del conjunto).
Quiero elegir dos registros del conjunto y poder mostrar todas las rutas simples entre los registros elegidos.Por "rutas simples" me refiero a las rutas que no tienen registros repetidos en la ruta (es decir,sólo caminos finitos).
Nota:Los dos registros elegidos siempre serán diferentes (es decir,el vértice inicial y final nunca serán los mismos;sin ciclos).
Por ejemplo:
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]
Si elijo B como mi registro inicial y E como mi registro final, querría encontrar todas las rutas simples a través de las conexiones de registros que conectarían el registro B con el 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 es un ejemplo; en la práctica, puedo tener conjuntos que contienen cientos de miles de registros.
Solución
Parece que esto se puede lograr con una búsqueda en profundidad del gráfico. La búsqueda en profundidad encontrará todas las rutas no cíclicas entre dos nodos. Este algoritmo debe ser muy rápido y escalar a gráficos grandes (la estructura de datos del gráfico es escasa, por lo que solo utiliza tanta memoria como es necesaria).
Noté que el gráfico que especificaste arriba tiene solo un borde que es direccional (B,E).¿Fue un error tipográfico o es realmente un gráfico dirigido?Esta solución funciona independientemente.Lo siento, no pude hacerlo en C, soy un poco débil en esa área.Espero que puedas traducir este código Java sin demasiados 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);
}
}
Buscar.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();
}
}
Salida del programa:
B E
B A C E
B A C F E
B F E
B F C E
Otros consejos
El Diccionario en línea de algoritmos y estructuras de datos del Instituto Nacional de Estándares y Tecnología (NIST) enumera este problema como "todos los caminos simples" y recomienda un búsqueda en profundidad.CLRS proporciona los algoritmos relevantes.
Se descubre una técnica inteligente que utiliza redes de Petri aquí
Aquí está el pseudocódigo que se me ocurrió.Este no es un dialecto de pseudocódigo en particular, pero debería ser lo suficientemente simple de seguir.
Cualquiera quiere separar esto.
[p] es una lista de vértices que representan la ruta actual.
[x] es una lista de rutas donde se cumplen los criterios
[s] es el vértice fuente
[d] es el vértice de destino
[c] es el vértice actual (argumento de la rutina PathFind)
Supongamos que existe una forma eficaz de buscar los vértices adyacentes (línea 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
Dado que la implementación DFS no recursiva existente dada en esta respuesta Parece estar roto, déjame proporcionarte uno que realmente funcione.
He escrito esto en Python porque lo encuentro bastante legible y sin detalles de implementación (y porque tiene la práctica yield palabra clave para implementar generadores), pero debería ser bastante fácil migrar a otros 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 mantiene dos pilas paralelas:uno que contiene los nodos anteriores en la ruta actual y otro que contiene el índice de vecino actual para cada nodo en la pila de nodos (para que podamos reanudar la iteración a través de los vecinos de un nodo cuando lo sacamos de la pila).Podría haber usado igualmente una sola pila de pares (nodo, índice), pero pensé que el método de dos pilas sería más legible y quizás más fácil de implementar para usuarios de otros idiomas.
Este código también utiliza un separado visited set, que siempre contiene el nodo actual y cualquier nodo en la pila, para permitirme verificar de manera eficiente si un nodo ya forma parte de la ruta actual.Si su idioma tiene una estructura de datos de "conjunto ordenado" que proporciona operaciones push/pop eficientes tipo pila y consultas de membresía eficientes, puede usarlas para la pila de nodos y deshacerse de las separadas visited colocar.
Alternativamente, si está utilizando una clase/estructura mutable personalizada para sus nodos, puede simplemente almacenar un indicador booleano en cada nodo para indicar si ha sido visitado como parte de la ruta de búsqueda actual.Por supuesto, este método no le permitirá ejecutar dos búsquedas en el mismo gráfico en paralelo, si por alguna razón desea hacerlo.
Aquí hay un código de prueba que demuestra cómo funciona la función proporcionada anteriormente:
# 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)
La ejecución de este código en el gráfico de ejemplo proporcionado produce el siguiente resultado:
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
Tenga en cuenta que, si bien este gráfico de ejemplo no está dirigido (es decir,todas sus aristas van en ambos sentidos), el algoritmo también funciona para gráficos dirigidos arbitrarios.Por ejemplo, eliminar el C -> B borde (quitando B de la lista de vecinos de C) produce el mismo resultado excepto por la tercera ruta (A -> C -> B -> D), lo cual ya no es posible.
PD. Es fácil construir gráficos para los cuales algoritmos de búsqueda simples como este (y los otros que se dan en este hilo) funcionan muy mal.
Por ejemplo, considere la tarea de encontrar todos los caminos de A a B en un gráfico no dirigido donde el nodo inicial A tiene dos vecinos:el nodo objetivo B (que no tiene más vecinos que A) y un nodo C que es parte de un camarilla de norte+1 nodos, así:
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"),
}
Es fácil ver que el único camino entre A y B es el directo, pero un DFS ingenuo iniciado desde el nodo A desperdiciará O(norte!) tiempo explorando inútilmente caminos dentro de la camarilla, aunque es obvio (para un humano) que ninguno de esos caminos puede conducir a B.
También se puede construir DAG con propiedades similares, p.e.haciendo que el nodo inicial A conecte el nodo objetivo B y otros dos nodos C1 y C2, los cuales se conectan a los nodos D1 y D2, los cuales se conectan a E1 y E2, etcétera.Para norte capas de nodos dispuestos de esta manera, una búsqueda ingenua de todos los caminos de A a B terminará desperdiciando O(2norte) tiempo examinando todos los posibles callejones sin salida antes de darse por vencido.
Por supuesto, agregar un borde al nodo objetivo B desde uno de los nodos en la camarilla (que no sea C), o desde la última capa del DAG, haría crea un número exponencialmente grande de caminos posibles de A a B, y un algoritmo de búsqueda puramente local no puede decir de antemano si encontrará tal borde o no.Así, en cierto sentido, los pobres sensibilidad de salida de búsquedas tan ingenuas se debe a su falta de conocimiento de la estructura global del gráfico.
Si bien existen varios métodos de preprocesamiento (como la eliminación iterativa de nodos hoja, la búsqueda de separadores de vértices de un solo nodo, etc.) que podrían usarse para evitar algunos de estos "callejones sin salida de tiempo exponencial", no conozco ninguno general. truco de preprocesamiento que podría eliminarlos en todo casos.Una solución general sería comprobar en cada paso de la búsqueda si todavía se puede acceder al nodo de destino (mediante una subbúsqueda) y retroceder rápidamente si no lo es, pero, por desgracia, eso ralentizaría significativamente la búsqueda (en el peor de los casos). , proporcionalmente al tamaño del gráfico) para muchos gráficos que no contienen tales callejones sin salida patológicos.
Aquí hay una versión recursiva lógicamente más atractiva en comparación con el segundo piso.
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);
}
}
}
}
Salida del programa
B A C E
B A C F E
B E
B F C E
B F E
Solución en código C.Está basado en DFS que utiliza una memoria 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);
}
Resolví un problema similar a este recientemente, en lugar de todas las soluciones, solo me interesaba la más corta.
Utilicé una búsqueda iterativa de "primero la amplitud" que utilizaba una cola de estados, cada una de las cuales contenía un registro que contenía un punto actual en el gráfico y la ruta tomada para llegar allí.
comienza con un único registro en la cola, que tiene el nodo inicial y una ruta vacía.
Cada iteración a través del código quita el elemento del encabezado de la lista y verifica si es una solución (el nodo al que se llega es el que desea; si lo es, hemos terminado); de lo contrario, construye un nuevo elemento de la cola con los nodos que se conectan al nodo actual y rutas modificadas que se basan en la ruta del nodo anterior, con el nuevo salto adjunto al final.
Ahora, podrías usar algo similar, pero cuando encuentres una solución, en lugar de detenerte, agrega esa solución a tu 'lista encontrada' y continúa.
Debe realizar un seguimiento de la lista de nodos visitados, de modo que nunca retroceda sobre sí mismo, de lo contrario tendrá un bucle infinito.
Si quieres un poco más de pseudocódigo, publica un comentario o algo así y te lo explicaré.
Creo que deberías describir tu verdadero problema detrás de esto.Digo esto porque pides algo que ahorre tiempo, ¡pero la respuesta al problema parece crecer exponencialmente!
Por lo tanto, no esperaría un algoritmo mejor que algo exponencial.
Retrocedería y revisaría todo el gráfico.Para evitar ciclos, guarde todos los nodos visitados a lo largo del camino.Cuando regreses, desmarca el nodo.
Usando recursividad:
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 eso está mal?
editar:Ah, y se me olvidó:Debes eliminar las llamadas recursivas utilizando esa pila de nodos.
El principio básico es que no necesita preocuparse por los gráficos. Este es un problema estándar conocido como problema de conectividad dinámica.Existen los siguientes tipos de métodos mediante los cuales puede lograr que los nodos estén conectados o no:
- Búsqueda rápida
- unión rápida
- Algoritmo mejorado (combinación de ambos)
Aquí está el código C que probé con una complejidad de tiempo mínima O (log*n). Eso significa que para 65536 listas de bordes, requiere 4 búsquedas y para 2 ^ 65536, requiere 5 búsquedas.Estoy compartiendo mi implementación del algoritmo: Curso de algoritmos de la Universidad de Princeton.
CONSEJO:Puede encontrar la solución Java en el enlace compartido anteriormente con las explicaciones adecuadas.
/* 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;
}
Puede que sea tarde, pero aquí está la misma versión C# del algoritmo DFS en Java de Casey para recorrer todas las rutas entre dos nodos usando una pila.La legibilidad es mejor con recursivo como siempre.
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_rutas[s, t, d, k]
Esta pregunta es antigua y ya está respondida.Sin embargo, ninguno muestra quizás un algoritmo más flexible para lograr lo mismo.Así que lanzaré mi sombrero al ring.
Personalmente encuentro un algoritmo de la forma find_paths[s, t, d, k] útil, donde:
- s es el nodo inicial
- t es el nodo objetivo
- d es la profundidad máxima para buscar
- k es el número de caminos a encontrar
Usando la forma de infinito de su lenguaje de programación para d y k te dará todos los caminos§.
§ obviamente si estás usando un gráfico dirigido y quieres todo no dirigido caminos entre s y t Tendrás que ejecutar esto en ambos sentidos:
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Función de ayuda
Personalmente me gusta la recursividad, aunque a veces puede resultar difícil. De todos modos, primero definamos nuestra función 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()
Función principal
Dicho esto, la función principal es trivial:
def find_paths[s, t, d, k]:
paths_found = [] # PASSING THIS BY REFERENCE
find_paths_recursion(s, t, 0, d, k, [], paths_found)
Primero, notemos algunas cosas:
- El pseudocódigo anterior es una combinación de lenguajes, pero se parece mucho a Python (ya que solo estaba codificando en él).Un copiar y pegar estricto no funcionará.
[]es una lista no inicializada, reemplácela con el equivalente para el lenguaje de programación de su elecciónpaths_foundes pasado por referencia.Está claro que la función de recursividad no devuelve nada.Maneje esto apropiadamente.- aquí
graphestá asumiendo alguna forma dehashedestructura.Hay una gran cantidad de formas de implementar un gráfico.De cualquier manera,graph[vertex]te da una lista de vértices adyacentes en un dirigido gráfico: ajuste en consecuencia. - esto supone que ha realizado un procesamiento previo para eliminar "hebillas" (autobucles), ciclos y bordes múltiples
He aquí un pensamiento que se me viene a la cabeza:
- Encuentra una conexión.(La búsqueda en profundidad es probablemente un buen algoritmo para esto, ya que la longitud de la ruta no importa).
- Deshabilita el último segmento.
- Intente encontrar otra conexión desde el último nodo anterior a la conexión previamente deshabilitada.
- Vaya a 2 hasta que no haya más conexiones.
Por lo que puedo decir, las soluciones dadas por Ryan Fox (58343, cristiano (58444), y usted mismo (58461) son tan buenos como parece.No creo que el recorrido en amplitud ayude en este caso, ya que no obtendrá todos los caminos.Por ejemplo, con bordes (A,B), (A,C), (B,C), (B,D) y (C,D) obtendrás caminos ABD y ACD, pero no ABCD.
Encontré una manera de enumerar todos los caminos, incluidos los infinitos que contienen bucles.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Encontrar caminos y ciclos atómicos
Definition
Lo que queremos hacer es encontrar todos los caminos posibles que vayan del punto A al punto B.Dado que hay ciclos involucrados, no puedes simplemente repasarlos y enumerarlos todos.En su lugar, tendrá que encontrar una ruta atómica que no se repita y los ciclos más pequeños posibles (no querrá que su ciclo se repita).
La primera definición que tomé de camino atómico es un camino que no pasa dos veces por el mismo nodo.Sin embargo, descubrí que no estaba aprovechando todas las posibilidades.Después de reflexionar un poco, descubrí que los nodos no son importantes, ¡sino los bordes!Entonces, un camino atómico es un camino que no pasa dos veces por el mismo borde.
Esta definición es útil, también funciona para ciclos:Un ciclo atómico del punto A es un camino atómico que va desde el punto A y termina en el punto A.
Implementación
Atomic Paths A -> B
Para obtener todo el camino a partir del punto A, recorreremos el gráfico de forma recursiva desde el punto A.Mientras pasamos por un hijo, vamos a hacer un enlace hijo -> padre para conocer todos los bordes que ya hemos cruzado.Antes de ir a ese niño, debemos recorrer esa lista vinculada y asegurarnos de que no se haya recorrido el borde especificado.
Cuando lleguemos al punto de destino, podremos almacenar el camino que encontramos.
Freeing the list
Se produce un problema cuando desea liberar la lista vinculada.Básicamente es un árbol encadenado en orden inverso.Una solución sería vincular doblemente esa lista y, cuando se hayan encontrado todas las rutas atómicas, liberar el árbol desde el punto de partida.
Pero una solución inteligente es utilizar un recuento de referencias (inspirado en Garbage Collection).Cada vez que agrega un enlace a un padre, agrega uno a su recuento de referencias.Luego, cuando llegas al final de un camino, retrocedes y te liberas mientras el recuento de referencia es igual a 1.Si es más alto, simplemente quita uno y se detiene.
Atomic Cycle A
Buscar el ciclo atómico de A es lo mismo que buscar el camino atómico de A a A.Sin embargo, hay varias optimizaciones que podemos hacer.Primero, cuando llegamos al punto de destino, queremos guardar el camino solo si la suma del costo de los bordes es negativa:sólo queremos pasar por ciclos absorbentes.
Como has visto anteriormente, se recorre todo el gráfico cuando se busca una ruta atómica.En cambio, podemos limitar el área de búsqueda al componente fuertemente conectado que contiene A.Encontrar estos componentes requiere un simple recorrido del gráfico con el algoritmo de Tarjan.
Combinando rutas y ciclos atómicos
En este punto, tenemos todos los caminos atómicos que van de A a B y todos los ciclos atómicos de cada nodo, y nos queda organizar todo para obtener el camino más corto.A partir de ahora vamos a estudiar cómo encontrar la mejor combinación de ciclos atómicos en una trayectoria atómica.
Como lo describen hábilmente algunos de los otros carteles, el problema en pocas palabras es el de utilizar un algoritmo de búsqueda en profundidad para buscar recursivamente en el gráfico todas las combinaciones de rutas entre los nodos finales en comunicación.
El algoritmo en sí comienza con el nodo de inicio que usted le asigna, examina todos sus enlaces salientes y progresa expandiendo el primer nodo secundario del árbol de búsqueda que aparece, buscando progresivamente más y más profundamente hasta que se encuentra un nodo objetivo, o hasta que encuentra un nodo. que no tiene hijos.
Luego, la búsqueda retrocede y regresa al nodo más reciente que aún no ha terminado de explorar.
I blogueado sobre este mismo tema recientemente, publicando un ejemplo de implementación de C++ en el proceso.
Además de la respuesta de Casey Watson, aquí hay otra implementación de Java.Inicializando el nodo visitado con el nodo 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();
}
}
