algorithm - varias - representación de una función de tres variables
Algoritmo de gráfico para encontrar todas las conexiones entre dos vértices arbitrarios (16)
Estoy tratando de determinar el mejor algoritmo eficiente de tiempo para llevar a cabo 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 los pares de registros de este conjunto se conectan entre sí. 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 en el conjunto tienen información de conexión (es decir, no hay registros huérfanos, cada registro en el conjunto se conecta a uno o más registros en el conjunto).
Quiero elegir dos registros del conjunto y poder mostrar todas las rutas simples entre los registros elegidos. Por "caminos simples" me refiero a los caminos que no tienen registros repetidos en la ruta (es decir, solo caminos finitos).
Nota: Los dos registros elegidos siempre serán diferentes (es decir, el vértice de inicio y fin nunca será el mismo, no habrá 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, me gustaría encontrar todas las rutas simples a través de las conexiones de registro 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.
find_paths [s, t, d, k]
Esta pregunta es vieja y ya respondida. Sin embargo, ninguno muestra quizás un algoritmo más flexible para lograr lo mismo. Entonces pondré mi sombrero en el ring.
Personalmente encuentro útil un algoritmo de la forma find_paths[s, t, d, k] , 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 para encontrar
Usar la forma de infinito de tu lenguaje de programación para d y k te dará todas las rutas§.
§ Obviamente, si está utilizando un gráfico dirigido y quiere todas las rutas no dirigidas entre s y t , tendrá que ejecutar esto de ambas formas:
find_paths[s, t, d, k] <join> find_paths[t, s, d, k]
Función auxiliar
Personalmente me gusta la recursión, aunque puede ser difícil algunas veces, 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
Con eso fuera del camino, la función central 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, observemos algunas cosas:
- el pseudocódigo anterior es una mezcla de idiomas, pero se asemeja mucho más a Python (ya que solo estaba codificando en él). Un estricto copiar y pegar no funcionará.
-
[]es una lista no inicializada, reemplácela con el equivalente para su lenguaje de programación de elección -
paths_foundse pasa por referencia . Está claro que la función de recursión no devuelve nada. Maneje esto apropiadamente. - aquí el
graphestá asumiendo alguna forma de estructurahashed. Hay una gran cantidad de formas de implementar un gráfico. De cualquier manera, elgraph[vertex]le proporciona una lista de vértices adyacentes en un gráfico dirigido - ajústelo en consecuencia. - esto supone que ha procesado previamente para eliminar "hebillas" (auto-bucles), ciclos y bordes múltiples
Aquí está el pseudocódigo que se me ocurrió. Este no es un dialecto de pseudocódigo particular, pero debe ser lo suficientemente simple como para seguirlo.
Alguien quiere elegir esto.
[p] es una lista de vértices que representan la ruta actual.
[x] es una lista de rutas donde 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 hay una forma eficiente 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
Aquí hay un pensamiento fuera de mi cabeza:
- Encuentra una conexión (La búsqueda en profundidad es probablemente un buen algoritmo para esto, ya que la longitud del camino no importa).
- Deshabilita el último segmento.
- Intente encontrar otra conexión desde el último nodo antes de la conexión previamente deshabilitada.
- Ir a 2 hasta que no haya más conexiones.
Aquí hay una versión recursiva lógicamente mejor 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
Creo que deberías describir tu problema real detrás de esto. Digo esto porque pides algo eficiente en el tiempo, ¡pero la respuesta al problema parece crecer exponencialmente!
Por lo tanto, no esperaría un algoritmo mejor que algo exponencial.
Haría un back-track y revisaré todo el gráfico. Para evitar ciclos, guarde todos los nodos visitados en el camino. Cuando regrese, desmarque el nodo.
Usando recursión:
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 es eso incorrecto?
editar: Ah, y lo olvidé: debería eliminar las llamadas recursivas utilizando esa pila de nodos
Dado que la implementación de DFS no recursiva existente dada en esta respuesta parece estar rota, permítame proporcionar una que realmente funcione.
Escribí esto en Python, porque me parece bastante legible y ordenado por los detalles de la implementación (y porque tiene la palabra clave de yield útil para implementar generators ), pero debería ser bastante fácil de exportar 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: una que contiene los nodos anteriores en la ruta actual y otra que contiene el índice contiguo 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 la recuperamos la pila). También podría haber usado una sola pila de pares (nodo, índice), pero pensé que el método de dos pilas sería más legible y tal vez más fácil de implementar para usuarios de otros idiomas.
Este código también usa un conjunto visited separado, que siempre contiene el nodo actual y los nodos en la pila, para permitirme verificar de manera eficiente si un nodo ya es parte de la ruta actual. Si su idioma tiene una estructura de datos de "conjunto ordenado" que proporciona operaciones push / pop similares a las de una pila eficientes y consultas de membresía eficientes, puede usarlo para la pila de nodos y deshacerse del conjunto visited separado.
Alternativamente, si está utilizando una clase / estructura mutable personalizada para sus nodos, puede simplemente almacenar un indicador booleano en cada nodo para indicar si se ha 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 anterior:
# 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)
Ejecutar este código en el gráfico de ejemplo dado produce el siguiente resultado:
A -> B -> C -> D A -> B -> D A -> C -> B -> D A -> C -> D
Tenga en cuenta que, aunque este gráfico de ejemplo no está dirigido (es decir, todos sus bordes van en ambas direcciones), el algoritmo también funciona para gráficos dirigidos arbitrarios. Por ejemplo, eliminar el borde C -> B (eliminando B de la lista contigua de C ) produce la misma salida excepto para la tercera ruta ( A -> C -> B -> D ), que ya no es posible.
PD. Es fácil construir gráficos para los cuales los algoritmos simples de búsqueda como este (y los otros dados en este hilo) funcionan muy mal.
Por ejemplo, considere la tarea de encontrar todas las rutas de A a B en un gráfico no dirigido donde el nodo de inicio A tiene dos vecinos: el nodo de destino B (que no tiene más vecinos que A) y un nodo C que es parte de una clique de n +1 nodos, como este:
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 ( n !) Tiempo inútilmente explorando caminos dentro de la camarilla, a pesar de que es obvio (para un ser humano) ninguno de esos caminos puede llevar a B.
También se pueden construir DAGs con propiedades similares, por ejemplo, haciendo que el nodo A inicial conecte el nodo objetivo B y con otros dos nodos C 1 y C 2 , que se conectan a los nodos D 1 y D 2 , que se conectan a E 1 y E 2 , y así sucesivamente. Para n capas de nodos dispuestos de esta manera, una búsqueda ingenua de todas las rutas desde A hasta B terminará desperdiciando O (2 n ) 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, crearía un número exponencialmente grande de caminos posibles de A a B, y un El algoritmo de búsqueda puramente local realmente no puede decir de antemano si encontrará tal ventaja o no. Por lo tanto, en cierto sentido, la pobre sensibilidad de salida de tales búsquedas ingenuas se debe a su falta de conocimiento de la estructura global del gráfico.
Si bien hay varios métodos de preprocesamiento (como la eliminación iterativa de nodos hoja, la búsqueda de separadores de vértices de nodo único, etc.) que podrían utilizarse para evitar algunos de estos "callejones sin salida de tiempo exponencial", no sé de ningún tipo truco de preprocesamiento que podría eliminarlos en todos los casos. Una solución general sería verificar en cada paso de la búsqueda si el nodo de destino todavía es alcanzable (utilizando una búsqueda secundaria), y retroceder temprano si no es así, 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 esos callejones sin salida patológicos.
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 senderos simples" y recomienda una búsqueda en profundidad . CLRS suministra los algoritmos relevantes.
Una técnica inteligente usando redes de Petri se encuentra here
El principio básico es que no debe 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 desde los que 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 he probado con una complejidad de tiempo mínima O (log * n) Eso significa que para la lista 65536 de bordes, requiere 4 búsquedas y para 2 ^ 65536, requiere 5 búsquedas. Estoy compartiendo mi implementación del algoritmo: Curso de Algoritmo de la Universidad de Princeton
CONSEJO: Puede encontrar la solución Java desde el enlace compartido arriba 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;
}
Encontré una manera de enumerar todas las rutas incluyendo las infinitas que contienen bucles.
http://blog.vjeux.com/2009/project/project-shortest-path.html
Encontrar rutas y ciclos atómicos
Definition
Lo que queremos hacer es encontrar todos los caminos posibles yendo del punto A al punto B. Como hay ciclos involucrados, no se puede pasar y enumerarlos todos. En su lugar, deberá encontrar una ruta atómica que no circule y los ciclos posibles más pequeños (no desea que su ciclo se repita).
La primera definición que tomé de una ruta atómica es una ruta que no pasa por el mismo nodo dos veces. Sin embargo, descubrí que no estaba tomando todas las posibilidades. Después de una reflexión, descubrí que los nodos no son importantes, ¡sin importar los bordes! Entonces un camino atómico es un camino que no pasa por el mismo borde dos veces.
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 hasta el punto A.
Implementación
Atomic Paths A -> B
Para obtener todo el camino comenzando desde el punto A, vamos a recorrer el gráfico recursivamente desde el punto A. Mientras atravesamos a un niño, vamos a hacer un enlace niño -> padre para conocer todos los bordes que tenemos ya he cruzado. Antes de ir a ese niño, debemos atravesar esa lista vinculada y asegurarnos de que el borde especificado no haya sido recorrido.
Cuando lleguemos al punto de destino, podemos 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 el orden inverso. Una solución sería duplicar esa lista y cuando se hayan encontrado todas las rutas atómicas, libere el árbol del 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 referencia. Luego, cuando llegue al final de un camino, retrocederá y se liberará mientras el recuento de referencias sea igual a 1. Si es más alto, solo debe eliminar uno y detenerse.
Atomic Cycle A
Buscar el ciclo atómico de A es lo mismo que buscar la ruta atómica de A a A. Sin embargo, hay varias optimizaciones que podemos hacer. Primero, cuando llegamos al punto de destino, queremos guardar la ruta solo si la suma del costo de los bordes es negativa: solo queremos pasar por ciclos de absorción.
Como ha visto anteriormente, todo el gráfico se está recorriendo al buscar un camino atómico. En su lugar, podemos limitar el área de búsqueda al componente fuertemente conectado que contiene A. Encontrar estos componentes requiere un recorrido simple del gráfico con el algoritmo de Tarjan.
Combinando rutas y ciclos atómicos
En este punto, tenemos todas las rutas atómicas que van de A a B y todos los ciclos atómicos de cada nodo, dejamos que organicemos 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 un camino atómico.
Esto puede ser tarde, pero esta es la misma versión de C # del algoritmo DFS en Java de Casey para recorrer todas las rutas entre dos nodos que usan 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 | // ------------------
He resuelto un problema similar recientemente, en lugar de todas las soluciones que solo me interesaban en el más breve.
Utilicé una búsqueda iterativa de "amplitud primero" que utilizaba una cola de estado, cada una de las cuales contenía un registro que contenía un punto actual en el gráfico y la ruta que se tomaba para llegar allí.
comienzas con un solo 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 llegó es el que desea, si es así, hemos terminado), de lo contrario, construye un nuevo elemento de 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ía usar algo similar, pero cuando encuentre una solución, en lugar de detenerse, agregue esa solución a su ''lista de búsqueda'' y continúe.
Debe realizar un seguimiento de la lista de nodos visitados, de modo que nunca retroceda en usted mismo, de lo contrario, tendrá un ciclo infinito.
si quieres un poco más de pseudocódigo publica un comentario o algo, y lo elaboraré.
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 la cantidad de memoria que necesita).
Noté que el gráfico que especificó anteriormente tiene solo un borde que es direccional (B, E). ¿Fue esto 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. Sin embargo, espero que puedas traducir este código Java sin demasiados problemas.
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();
}
}
Salida del programa:
B E
B A C E
B A C F E
B F E
B F C E
Por lo que puedo decir, las soluciones dadas por Ryan Fox ( 58343 , Christian ( 58444 ) y usted mismo ( 58461 ) son tan buenas como es posible. No creo que el recorrido transversal amplía la ayuda en este caso, ya que lo hará no obtener todos los caminos. Por ejemplo, con los bordes (A,B) , (A,C) , (B,C) , (B,D) y (C,D) obtendrás los caminos ABD y ACD , pero no ABCD .
Solución en código C. Está basado en DFS que usa 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);
}
As ably described by some of the other posters, the problem in a nutshell is that of using a depth-first search algorithm to recursively search the graph for all combinations of paths between the communicating end nodes.
The algorithm itself commences with the start node you give it, examines all its outgoing links and progresses by expanding the first child node of the search tree that appears, searching progressively deeper and deeper until a target node is found, or until it encounters a node that has no children.
The search then backtracks, returning to the most recent node it hasn''t yet finished exploring.
I blogged about this very topic quite recently, posting an example C++ implementation in the process.
Agregando a la respuesta de Casey Watson, aquí hay otra implementación de Java. Inicializando el nodo visitado con el nodo de inicio.
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();
}
}