representations for explained dummies book algorithms algorithm graph-theory

algorithm - for - Encuentra todas las rutas entre dos nodos gráficos



graph theory for dummies (10)

find_paths [s, t, d, k]

Esta pregunta ahora es un poco vieja ... pero voy a lanzar mi sombrero al 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_found se pasa por referencia . Está claro que la función de recursión no devuelve nada. Maneje esto apropiadamente.
  • aquí el graph está asumiendo alguna forma de estructura hashed . Hay una gran cantidad de formas de implementar un gráfico. De cualquier manera, el graph[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

Estoy trabajando en la implementación del Algoritmo de Dijkstras para recuperar el camino más corto entre los nodos interconectados en una red de rutas. Tengo la implementación funcionando. Devuelve todas las rutas más cortas a todos los nodos cuando paso el nodo de inicio al algoritmo.

Mi pregunta: ¿Cómo se puede recuperar todos los caminos posibles desde el Nodo A para decir Nodo G o incluso todos los caminos posibles desde el Nodo A y volver al Nodo A

Encontrar todos los caminos posibles es un problema difícil, ya que hay un número exponencial de caminos simples. Incluso encontrar el kth camino más corto [o el camino más largo] es NP-Hard .

Una posible solución para encontrar todas las rutas [o todas las rutas hasta una determinada longitud] desde s hasta t es BFS , sin guardar un conjunto visited , o para la versión ponderada; es posible que desee utilizar la búsqueda de costo uniforme.

Tenga en cuenta que también en cada gráfico que tiene ciclos [no es un DAG ] puede haber un número infinito de caminos entre s a t .

Implementé una versión donde básicamente encuentra todas las rutas posibles de un nodo a otro, pero no cuenta ningún posible ''ciclo'' (el gráfico que estoy usando es cíclico). Entonces, básicamente, ningún nodo aparecerá dos veces dentro de la misma ruta. Y si el gráfico fuera acíclico, supongo que podría decir que parece encontrar todos los caminos posibles entre los dos nodos. Parece estar funcionando bien, y para mi tamaño de gráfico de ~ 150, se ejecuta casi instantáneamente en mi máquina, aunque estoy seguro de que el tiempo de ejecución debe ser algo así como exponencial, por lo que comenzará a ralentizarse rápidamente como el el gráfico se hace más grande

Aquí hay algunos códigos Java que demuestran lo que implementé. Estoy seguro de que debe haber formas más eficientes o elegantes de hacerlo también.

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

Por lo general, no desea, porque hay un número exponencial de ellos en gráficos no triviales; si realmente desea obtener todas las rutas (simples) o todos los ciclos (simples), solo encuentra uno (recorriendo el gráfico), luego retrocede a otro.

Supongo que quieres encontrar rutas ''simples'' (una ruta es simple si no aparece ningún nodo más de una vez, excepto tal vez la primera y la última).

Dado que el problema es NP-hard, es posible que desee hacer una variante de la búsqueda en profundidad.

Básicamente, genera todos los caminos posibles desde A y comprueba si terminan en G.

Te daré una versión (algo pequeña) (aunque comprensible, creo) de una prueba científica de que no puedes hacer esto en un tiempo factible.

Lo que voy a probar es que la complejidad del tiempo para enumerar todas las rutas simples entre dos nodos seleccionados y distintos (por ejemplo, s y t ) en un gráfico arbitrario G no es polinomial. Tenga en cuenta que, dado que solo nos preocupa la cantidad de rutas entre estos nodos, los costos de los bordes no son importantes.

Seguro que si el gráfico tiene algunas propiedades bien seleccionadas, esto puede ser fácil. Estoy considerando el caso general sin embargo.

Supongamos que tenemos un algoritmo polinomial que enumera todas las rutas simples entre s y t .

Si G está conectado, la lista no está vacía. Si G no es y s y t están en componentes diferentes, es realmente fácil enumerar todas las rutas entre ellos, ¡porque no hay ninguno! Si están en el mismo componente, podemos pretender que el gráfico completo consiste solo en ese componente. Asumamos que G está efectivamente conectado.

El número de rutas listadas debe ser polinomial; de lo contrario, el algoritmo no podría devolverlas todas. Si los enumera a todos, debe darme el más largo, entonces está allí. Al tener la lista de rutas, se puede aplicar un procedimiento simple para señalarme cuál es la ruta más larga.

Podemos mostrar (aunque no puedo pensar en una forma cohesiva de decirlo) que este camino más largo tiene que atravesar todos los vértices de G Por lo tanto, ¡acabamos de encontrar un camino hamiltoniano con un procedimiento polinomial! Pero este es un problema bien conocido de NP-hard.

Entonces podemos concluir que este algoritmo polinomial que pensamos que tenemos es muy poco probable que exista, a menos que P = NP .

Here hay un algoritmo que busca e imprime todas las rutas desde s hasta t usando la modificación de DFS. También se puede usar la programación dinámica para encontrar el recuento de todos los caminos posibles. El pseudo código se verá así:

AllPaths(G(V,E),s,t) C[1...n] //array of integers for storing path count from ''s'' to i TopologicallySort(G(V,E)) //here suppose ''s'' is at i0 and ''t'' is at i1 index for i<-0 to n if i<i0 C[i]<-0 //there is no path from vertex ordered on the left from ''s'' after the topological sort if i==i0 C[i]<-1 for j<-0 to Adj(i) C[i]<- C[i]+C[j] return C[i1]

Si realmente te importa ordenar tus rutas desde la ruta más corta al más larga, sería mucho mejor usar un algoritmo A * o Dijkstra modificado . Con una ligera modificación, el algoritmo devolverá la mayor cantidad posible de rutas posibles en el orden de la ruta más corta. Entonces, si lo que realmente quieres son todos los caminos posibles ordenados de menor a mayor, entonces este es el camino a seguir.

Si desea una implementación basada en A * capaz de devolver todas las rutas ordenadas de la más corta a la más larga, lo siguiente lo logrará. Tiene varias ventajas. En primer lugar, es eficiente para clasificar desde el más corto hasta el más largo. Además, calcula cada ruta adicional solo cuando es necesario, por lo que si se detiene antes porque no necesita todas las rutas, ahorrará tiempo de procesamiento. También reutiliza datos para rutas posteriores cada vez que calcula la siguiente ruta, por lo que es más eficiente. Finalmente, si encuentra un camino deseado, puede abortar anticipadamente, ahorrando tiempo de cálculo. En general, este debería ser el algoritmo más eficiente si le interesa ordenar por longitud de ruta.

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

El resultado del código anterior es el siguiente:

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

Tenga en cuenta que cada vez que llame a nextShortestPath() genera la siguiente ruta más corta para usted a pedido. Solo calcula los pasos adicionales necesarios y no atraviesa ningún camino viejo dos veces. Además, si decides que no necesitas todas las rutas y finalizas la ejecución anticipadamente, te has ahorrado un considerable tiempo de cálculo. Solo computa hasta la cantidad de rutas que necesita y nada más.

Finalmente, debe tenerse en cuenta que los algoritmos A * y Dijkstra tienen algunas limitaciones menores, aunque no creo que te afecten. Es decir, no funcionará correctamente en un gráfico que tenga ponderaciones negativas.

Aquí hay un enlace a JDoodle donde puede ejecutar el código usted mismo en el navegador y verlo funcionar. También puede cambiar alrededor del gráfico para mostrar que también funciona en otros gráficos: http://jdoodle.com/a/ukx